Answers are grounded in this paper and cite their sources.
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.
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: