For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution

Abstract

Abstract We consider linear equations y = Φ x where y is a given vector in ℝ n and Φ is a given n × m matrix with n < m ≤ τ n , and we wish to solve for x ∈ ℝ m . We suppose that the columns of Φ are normalized to the unit 𝓁 2 ‐norm, and we place uniform measure on such Φ. We prove the existence of ρ = ρ(τ) > 0 so that for large n and for all Φ's except a negligible fraction, the following property holds: For every y having a representation y = Φ x 0 by a coefficient vector x 0 ∈ ℝ m with fewer than ρ · n nonzeros, the solution x 1 of the 𝓁 1 ‐minimization problem is unique and equal to x 0 . In contrast, heuristic attempts to sparsely solve such systems—greedy algorithms and thresholding—perform poorly in this challenging setting. The techniques include the use of random proportional embeddings and almost‐spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices. © 2006 Wiley Periodicals, Inc.

Keywords

MathematicsUnderdetermined systemEigenvalues and eigenvectorsCombinatoricsBanach spaceWishart distributionCoefficient matrixNorm (philosophy)Random matrixCompressed sensingApplied mathematicsDiscrete mathematicsAlgorithmStatistics

Affiliated Institutions

Stanford University US

Related Publications

Decoding by Linear Programming

Emmanuel J. Candès , Terence Tao

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e....

2005 IEEE Transactions on Information Theory 7166 citations

Stable signal recovery from incomplete and inaccurate measurements

Emmanuel J. Candès , Justin Romberg , Terence Tao

Abstract Suppose we wish to recover a vector x 0 ∈ ℝ 𝓂 (e.g., a digital signal or image) from incomplete and contaminated observations y = A x 0 + e ; A is an 𝓃 × 𝓂 matrix wi...

2006 Communications on Pure and Applied Ma... 7037 citations

Eigenvalues and Condition Numbers of Random Matrices

Alan Edelman

Given a random matrix, what condition number should be expected? This paper presents a proof that for real or complex $n \times n$ matrices with elements from a standard normal ...

1988 SIAM Journal on Matrix Analysis and A... 1294 citations

Compressed sensing

David L. Donoho

Suppose x is an unknown vector in Ropf m (a digital image or signal); we pla...

2006 IEEE Transactions on Information Theory 22524 citations

Sparsity and incoherence in compressive sampling

Emmanuel J. Candès , Justin Romberg

We consider the problem of reconstructing a sparse signal x^0\\in{\\bb R}^n from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an...

2007 Inverse Problems 2068 citations

Publication Info

Year: 2006
Type: article
Volume: 59
Issue: 6
Pages: 797-829
Citations: 2507
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

2507

OpenAlex

Cite This

APA Style

                            
                                    David L. Donoho
                                
                            (2006). 
                            For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution. 
                            Communications on Pure and Applied Mathematics
                            , 59
                            (6)
                            , 797-829.
                            https://doi.org/10.1002/cpa.20132

Identifiers

DOI: 10.1002/cpa.20132