For most large underdetermined systems of equations, the minimal l1-norm near-solution approximates the sparsest near-solution

We consider inexact linear equations y ≈ Φα where y is a given vector in R n, Φ is a given n by m matrix, and we wish to find an α0,ɛ which is sparse and gives an approximate solution, obeying �y − Φα0,ɛ�2 ≤ ɛ. In general this requires combinatorial optimization and so is considered intractable. On the other hand, the ℓ 1 minimization problem min �α�1 subject to �y − Φα�2 ≤ ɛ, is convex, and is considered tractable. We show that for most Φ the solution ˆα1,ɛ = ˆα1,ɛ(y, Φ) of this problem is quite generally a good approximation for ˆα0,ɛ. We suppose that the columns of Φ are normalized to unit ℓ 2 norm 1 and we place uniform measure on such Φ. We study the underdetermined case where m ∼ An, A> 1 and prove the existence of ρ = ρ(A) and C> 0 so that for large n, and for all Φ’s except a negligible fraction, the following approximate sparse solution property of Φ holds: For every y having an approximation �y − Φα0�2 ≤ ɛ by a coefficient vector α0 ∈ R m with fewer than ρ · n nonzeros, we have �ˆα1,ɛ − α0�2 ≤ C · ɛ. This has two implications. First: for most Φ, whenever the combinatorial optimization result α0,ɛ would be very sparse, ˆα1,ɛ is a good approximation to α0,ɛ. Second: suppose we are given noisy data obeying y = Φα0 + z where the unknown α0 is known to be sparse and the noise �z�2 ≤ ɛ. For most Φ, noise-tolerant ℓ 1-minimization will stably recover α0 from y in the presence of noise z. We study also the barely-determined case m = n and reach parallel conclusions by slightly different arguments. The techniques include the use of almost-spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices