Answers are grounded in this paper and cite their sources.
Theoretical analysis demonstrates exact recovery of sparse vectors via l1-norm minimization in underdetermined linear systems, highlighting convex optimization over heuristics.
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.
No takes yet. Share an insight, caveat, or question.
David L. Donoho (2006) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: