Thresholds for the Recovery of Sparse Solutions via L1 Minimization

1 March 2006

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 202-206
https://doi.org/10.1109/ciss.2006.286462

Abstract

The ubiquitous least squares method for systems of linear equations returns solutions which typically have all non-zero entries. However, solutions with the least number of non-zeros allow for greater insight. An exhaustive search for the sparsest solution is intractable, NP-hard. Recently, a great deal of research showed that linear programming can find the sparsest solution for certain 'typical' systems of equations, provided the solution is sufficiently sparse. In this note we report recent progress determining conditions under which the sparsest solution to large systems is available by linear programming. Our work shows that there are sharp thresholds on sparsity below which these methods will succeed and above which they fail; it evaluates those thresholds precisely and hints at several interesting applications.

Keywords

This publication has 12 references indexed in Scilit:

Compressed sensing
IEEE Transactions on Information Theory, 2006
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
IEEE Transactions on Information Theory, 2006
Neighborliness of randomly projected simplices in high dimensions
Proceedings of the National Academy of Sciences, 2005
Greed is Good: Algorithmic Results for Sparse Approximation
IEEE Transactions on Information Theory, 2004
On Sparse Representations in Arbitrary Redundant Bases
IEEE Transactions on Information Theory, 2004
Sparse representations in unions of bases
IEEE Transactions on Information Theory, 2003
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
Proceedings of the National Academy of Sciences, 2003
A generalized uncertainty principle and sparse representation in pairs of bases
IEEE Transactions on Information Theory, 2002
Atomic Decomposition by Basis Pursuit
SIAM Review, 2001
Regular simplices and Gaussian samples
Discrete & Computational Geometry, 1994