For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution

Abstract We consider inexact linear equations y ≈ Φ x where y is a given vector in ℝ n , Φ is a given n × m matrix, and we wish to find x 0,ϵ as sparse as possible while obeying ‖ y − Φ x 0,ϵ ‖ 2 ≤ ϵ. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the 𝓁 1 ‐minimization problem is convex and is considered tractable. We show that for most Φ, if the optimally sparse approximation x 0,ϵ is sufficiently sparse, then the solution x 1,ϵ of the 𝓁 1 ‐minimization problem is a good approximation to x 0,ϵ . We suppose that the columns of Φ are normalized to the unit 𝓁 2 ‐norm, and we place uniform measure on such Φ. We study the underdetermined case where m ∼ τ n and τ > 1, and prove the existence of ρ = ρ(τ) > 0 and C = C (ρ, τ) 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 − Φ x 0 ‖ 2 ≤ ϵ by a coefficient vector x 0 ∈ ℝ m with fewer than ρ · n nonzeros , This has two implications. First, for most Φ, whenever the combinatorial optimization result x 0,ϵ would be very sparse, x 1,ϵ is a good approximation to x 0,ϵ . Second, suppose we are given noisy data obeying y = Φ x 0 + z where the unknown x 0 is known to be sparse and the noise ‖ z ‖ 2 ≤ ϵ. For most Φ, noise‐tolerant 𝓁 1 ‐minimization will stably recover x 0 from y in the presence of noise z . We also study the barely determined case m = n and reach parallel conclusions by slightly different arguments. Proof techniques include the use of almost‐spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices. © 2006 Wiley Periodicals, Inc.