For most large underdetermined systems of equations, the minimal š1ānorm nearāsolution approximates the sparsest nearāsolution
Top Cited Papers
- 21 March 2006
- journal article
- research article
- Published byĀ WileyĀ inĀ Communications on Pure and Applied Mathematics
- Vol.Ā 59 Ā (7) , 907-934
- https://doi.org/10.1002/cpa.20131
Abstract
We consider inexact linear equationsyā Ī¦xwhereyis a given vector in ān, Ī¦ is a givennĆmmatrix, and we wish to findx0,Ļµas sparse as possible while obeying āyā Ī¦x0,Ļµā2ā¤ Ļµ. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the š1āminimization problemis convex and is considered tractable. We show that for most Ī¦, if the optimally sparse approximationx0,Ļµis sufficiently sparse, then the solutionx1,Ļµof the š1āminimization problem is a good approximation tox0,Ļµ.We suppose that the columns of Ī¦ are normalized to the unit š2ānorm, and we place uniform measure on such Ī¦. We study theunderdeterminedcase wheremā¼ Ļnand Ļ > 1, and prove the existence of Ļ = Ļ(Ļ) > 0 andC=C(Ļ, Ļ) so that for largenand for all Ī¦'s except a negligible fraction, the followingapproximate sparse solutionproperty of Ī¦ holds:for every y having an approximationāyā Ī¦x0ā2ā¤ Ļµby a coefficient vector x0ā āmwith fewer than Ļ Ā· n nonzeros,This has two implications. First, for most Ī¦, whenever the combinatorial optimization resultx0,Ļµwould be very sparse,x1,Ļµis a good approximation tox0,Ļµ. Second, suppose we are given noisy data obeyingy= Ī¦x0+zwhere the unknownx0is known to be sparse and the noise āzā2ā¤ Ļµ. For most Ī¦, noiseātolerant š1āminimization will stably recoverx0fromyin the presence of noisez.We also study the barely determined casem=nand 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.Keywords
This publication has 19 references indexed in Scilit:
- Stable recovery of sparse overcomplete representations in the presence of noiseIEEE Transactions on Information Theory, 2005
- On Sparse Representations in Arbitrary Redundant BasesIEEE Transactions on Information Theory, 2004
- Least angle regressionThe Annals of Statistics, 2004
- Optimally sparse representation in general (nonorthogonal) dictionaries via ā 1 minimizationProceedings of the National Academy of Sciences, 2003
- A generalized uncertainty principle and sparse representation in pairs of basesIEEE Transactions on Information Theory, 2002
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001
- Local Operator Theory, Random Matrices and Banach SpacesPublished by Elsevier ,2001
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Eigenvalues and Condition Numbers of Random MatricesSIAM Journal on Matrix Analysis and Applications, 1988
- The dimension of almost spherical sections of convex bodiesActa Mathematica, 1977