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

Top Cited Papers
Publisher Website
Google Scholar
Abstract
We consider linear equationsy= Φxwhereyis a given vector in ℝnand Φ is a givenn×mmatrix withn<m≤ τn, and we wish to solve forx∈ ℝ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 largenand for all Φ's except a negligible fraction, the following property holds:For every y having a representation y= Φx0by a coefficient vector x0∈ ℝmwith fewer than ρ · n nonzeros, the solution x1of the𝓁1‐minimization problemis unique and equal to x0. 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.

This publication has 21 references indexed in Scilit: