Matrix sparsification and the sparse null space problem

DOI10.1007/s00453-015-0042-6zbMath1347.68369arXiv1008.1498OpenAlexW2184179978MaRDI QIDQ329287

Tyler Neylon, Lee-Ad J. Gottlieb

Publication date: 21 October 2016

Published in: Algorithmica, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.1498

zbMATH Keywords

sparse approximationmatrix sparsificationsparse null space

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation ⋮ A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem

Uses Software

• mctoolbox
• CoSaMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm to compute a sparse basis of the null space
• Understanding and using linear programming
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A hierarchical algorithm for making sparse matrices sparser
• The densest hemisphere problem
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Nonlinear methods of approximation
• Approximating CVP to within almost-polynomial factors is NP-hard
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
• On Sparse Representations in Arbitrary Redundant Bases
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Decoding by Linear Programming
• Greed is Good: Algorithmic Results for Sparse Approximation
• Just relax: convex programming methods for identifying sparse signals in noise
• Designing structured tight frames via an alternating projection method
• Near-optimal sparse fourier representations via sampling
• The Null Space Problem I. Complexity
• Computing a Sparse Basis for the Null Space
• The Sparse Basis Problem and Multilinear Algebra
• A Simple Proof of Descartes's Rule of Signs
• Accuracy and Stability of Numerical Algorithms
• Sparse Approximate Solutions to Linear Systems
• Entropy-based algorithms for best basis selection
• Dense Error Correction Via $\ell^1$-Minimization
• Automata, Languages and Programming
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution

This page was built for publication: Matrix sparsification and the sparse null space problem