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 ∼…

• MU
  Multidisciplinary University Research Initiative