Premium
For most large underdetermined systems of linear equations the minimal 𝓁 1 ‐norm solution is also the sparsest solution
Author(s) -
Donoho David L.
Publication year - 2006
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.20132
Subject(s) - mathematics , underdetermined system , eigenvalues and eigenvectors , combinatorics , banach space , wishart distribution , coefficient matrix , norm (philosophy) , random matrix , compressed sensing , discrete mathematics , algorithm , statistics , physics , quantum mechanics , multivariate statistics , political science , law
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$${\rm min} \|x\|_{1} \;\;{subject \; to}\;\; \Phi x = y$$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.