zbMATH — the first resource for mathematics

For most large underdetermined systems of equations, the minimal \(\ell_1\)-norm near-solution approximates the sparsest near-solution. (English) Zbl 1105.90068
Summary: We consider inexact linear equations \(y\approx\Phi x\) where \(y\) is a given vector in \(\mathbb{R}^n\), \(\Phi\) is a given \(n\times m\) matrix, and we wish to find \(x_{0,\varepsilon}\) as sparse as possible while obeying \(\|y-\Phi x_{0, \varepsilon}\}_2\leq\varepsilon\). In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the \(\ell_1\)-minimization problem \[ \min\|x\|_1\quad\text{ subject to }\quad\|y-\Phi x\|_2 \leq\varepsilon \] is convex and is considered tractable. We show that for most \(\Phi\), if the optimally sparse approximation \(x_{0,\varepsilon}\) is sufficiently sparse, then the solution \(x_{1,\varepsilon}\) of the \(\ell_1\)-minimization problem is a good approximation to \(x_{0,\varepsilon}\). We suppose that the columns of \(\Phi\) are normalized to the unit \(\ell_2\)-norm, and we place uniform measure on such \(\Phi\). We study the underdetermined case where \(m\sim\tau n\) and \(\tau>1\), and prove the existence of \(\rho=\rho (\tau)>0\) and \(C=C(\rho,\tau)\) so that for large \(n\) and for all \(\Phi\)’s except a negligible fraction, the following approximate sparse solution property of \(\Phi\) holds: for every \(y\) having an approximation \(\|y-\Phi x_0\|_2\leq\varepsilon\) by a coefficient vector \(x_0\in\mathbb{R}^m\) with fewer than \(\rho\cdot n\) nonzeros, \[ \|x_{1,\varepsilon}-x_0\|_2\leq C \cdot\varepsilon. \] This has two implications. First, for most \(\Phi\), whenever the combinatorial optimization result \(x_{0, \varepsilon}\) would be very sparse, \(x_{1,\varepsilon}\) is a good approximation to \(x_{0,\varepsilon}\). Second, suppose we are given noisy data obeying \(y=\Phi x_0+z\) where the unknown \(x_0\) is known to be sparse and the noise \(\|z\|\leq \varepsilon\). For most \(\Phi\), noise-tolerant \(\ell_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.

90C27 Combinatorial optimization
Full Text: DOI
[1] Candès, IEEE Trans Inform Theory
[2] Chen, SIAM J Sci Comput 20 pp 33– (1998)
[3] ; ; ; Signal processing and compression with wavelet packets. Progress in wavelet analysis and applications (Toulouse, 1992), 77–93. Frontières, Gif-sur-Yvette, 1993.
[4] ; Local operator theory, random matrices and Banach spaces. Handbook of the geometry of Banach spaces, Vol. 1, 317–366. North-Holland, Amsterdam, 2001. · Zbl 1067.46008
[5] Donoho, Comm Pure Appl Math
[6] Donoho, Proc Natl Acad Sci USA 100 pp 2197– (2003)
[7] Donoho, IEEE Trans Inform Theory 52 pp 6– (2006)
[8] Donoho, IEEE Trans Inform Theory 47 pp 2845– (2001)
[9] Donoho, J Roy Statist Soc Ser B 54 pp 41– (1992)
[10] Some results on convex bodies and Banach spaces. Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), 123–160. Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961.
[11] Edelman, SIAM J Matrix Anal Appl 9 pp 543– (1988)
[12] Efron, Ann Statist 32 pp 407– (2004)
[13] New results about random covariance matrices and statistical applications. Doctoral dissertation, Stanford University, 2004.
[14] Elad, IEEE Trans Inform Theory 48 pp 2558– (2002)
[15] Figiel, Acta Math 139 pp 53– (1977)
[16] Fuchs, IEEE Trans Inform Theory
[17] Fuchs, IEEE Trans Inform Theory 50 pp 1341– (2004)
[18] ; Matrix computations. Johns Hopkins, Baltimore, 1989.
[19] Gribonval, IEEE Trans Inform Theory 49 pp 3320– (2003)
[20] Kashin, Izv Akad Nauk SSSR Ser Mat 41 pp 334– (1977)
[21] The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, R.I., 2001.
[22] Mallat, IEEE Trans Signal Process 41 pp 3397– (1993)
[23] ; Asymptotic theory of finite-dimensional normed spaces. Lecture Notes in Mathematics, 1200. Springer, Berlin, 1986.
[24] Natarajan, SIAM J Comput 24 pp 227– (1995)
[25] The symmetric eigenvalue problem. Prentice-Hall Series in Computational Mathematics. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980.
[26] The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics, 94. Cambridge University Press, Cambridge, 1989. · doi:10.1017/CBO9780511662454
[27] Szarek, Bull Acad Polon Sci Sér Sci Math Astronom Phys 26 pp 691– (1978)
[28] Szarek, Amer J Math 112 pp 899– (1990)
[29] Szarek, J Complexity 7 pp 131– (1991)
[30] Tibshirani, J Roy Statist Soc Ser B 58 pp 267– (1996)
[31] Tropp, IEEE Trans Inform Theory 50 pp 2231– (2004)
[32] Tropp, IEEE Trans Inform Theory
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.