March 23, 2006Communications on Pure and Applied Mathematics
For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
Authors
Discussion
Loading...
Member takes
Overview
Theoretical analysis demonstrates exact recovery of sparse vectors via l1-norm minimization in underdetermined linear systems, highlighting convex optimization over heuristics.
Key Points
- Determine whether l1-norm minimization uniquely identifies the sparsest coefficient vector in large underdetermined systems of linear equations.
- Analyzed underdetermined systems y = Φx with n × m matrices (n < m ≤ τn) whose columns have normalized unit l2-norm under uniform measure.
- Utilized Banach space theory—specifically random proportional embeddings and almost-spherical sections—and eigenvalue deviation bounds for random Wishart matrices.
- Proved that for large n and almost all Φ, l1-minimization uniquely and exactly reconstructs any vector x0 having fewer than ρ · n non-zero entries.
- Demonstrated that traditional heuristic methods, such as greedy algorithms and thresholding, perform poorly and fail to guarantee recovery under identical conditions.
Cite This Study
David L. Donoho (2006) studied this question.