For most large underdetermined systems of linear equations the minimal \(\ell_{1}\)-norm solution is also the sparsest solution. (English) Zbl 1113.15004

The author studies sparse solutions to underdetermined linear systems \(y = \Phi x\) where \(y \in \mathbb{R}^n\) is a given vector and \(\Phi\) is a given \(n \times m\) matrix with \(n < m\leq \tau n\).
In the last years, a large body of research has focused on the use of overcomplete signal representations. If we have more atoms \(\phi_i \in \Phi\) than observation dimensions, \(m > n\), then there are many possible representations \(\Phi x = y\) for a given \(\Phi\) and \(y\). The sparse representation problem is then to find the representation \(x\) with the fewest possible non-zero components,
\[ \min \| x \|_0\text{ subject to }\Phi x = y,\tag{\(\text{P}_0\)} \]
where \(\| \;\|_0\) is the \(l_0\) norm of a vector \(x\), i.e., the number of its non-zero coefficients. This is well known to be a NP-hard problem [cf. B. K. Natarajan, SIAM J. Comput. 24, No. 2, 227–234 (1995; Zbl 0827.68054)].
In the signal processing community, S. S. Chen, D. L. Donoho and M. A. Saunders [SIAM J. Sci. Comput. 20, No. 1, 33–61 (1999; Zbl 0919.94002)] proposed to approximate (\(\text{P}_0\)) with the ‘relaxed’ \(l_1\) problem \[ \min \| x \|_1\text{ subject to }\Phi x = y,\tag{P}\(_1\) \] where \(\| \;\|_1=\sum_{i=1}^{m} | x_i |\) is the \(l_1\) norm of a vector \(x\). Problem (\(\text{P}_1\)), which they called basis pursuit (BP), can be formulated as a linear programming (LP) problem, which can be solved using well known optimization methods such as the simplex method or interior point methods [cf. M. H. Wright, Bull. Am. Math. Soc., New Ser. 42, No. 1, 39–56 (2005; Zbl 1114.90153)]. Surprisingly, when the answer to (\(\text{P}_0\)) is sparse, it can be the same as the answer to (\(\text{P}_1\)).
The equivalence breakdown point of a matrix \(\Phi\), \(\text{EBP}(\Phi)\), is the maximal number \(N\) such that, for every \(x_0\) with fewer than \(N\) nonzeros, the corresponding vector \(y = \Phi x_0\) generates a linear system \(y = \Phi x\) for which problems (\(\text{P}_0\)) and (\(\text{P}_1\)) have identical unique solutions, both equal to \(x_0\).
The main result of the paper is: For each \(\tau > 1\), there exists a constant \(\rho^*(\tau) > 0\) so that for every sequence \((m_n\)) with \(m_n\leq \tau n\), \[ \text{Prob} \{n^{-1} \text{EBP}(\Phi_{n,m_n})\geq \rho^*(\tau)\}\to 1, \quad n \to \infty. \] In other words, for the overwhelming majority of \(n \times m\) matrices \(\Phi\), the sparsest possible solution and the minimal \(l_1\)-solution of \(y = \Phi x\) coincide whenever a solution with at most \(\rho^*n\) nonzeros exists.
The author uses techniques from Banach space theory, in particular quantitative extensions of the almost spherical sections theorem [cf. A. Dvoretsky, Proc. Int. Symp. Linear Spaces, Jerusalem 1960, 123–160 (1961; Zbl 0119.31803)], and other related tools exploiting randomness in highdimensional spaces, including properties of the minimum eigenvalue of Wishart matrices.
The paper finishes showing as two standard approaches, simple thresholding and greedy subset selection algorithms, in contrast to the \(l_1\)-minimization, which are poorly performed in the setting of the paper.


15A06 Linear equations (linear algebraic aspects)
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
60D05 Geometric probability and stochastic geometry
41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
52A41 Convex functions and convex programs in convex geometry
90C20 Quadratic programming


Full Text: DOI


[1] Bauschke, SIAM Review 38 pp 367– (1996)
[2] Candès, IEEE Trans Inform Theory
[3] Chen, SIAM J Sci Comput 20 pp 33– (1998)
[4] ; ; ; Signal processing and compression with wavelet packets. Progress in wavelet analysis and applications (Toulouse, 1992), 77–93. Frontières, Gif-sur-Yvette, 1993.
[5] Coifman, IEEE Trans Inform Theory 38 pp 713– (1992)
[6] ; 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
[7] Donoho, IEEE Trans Inform Theory
[8] Donoho, Proc Natl Acad Sci USA 100 pp 2197– (2003)
[9] Donoho, IEEE Trans Inform Theory 52 pp 6– (2006)
[10] Donoho, IEEE Trans Inform Theory 47 pp 2845– (2001)
[11] Donoho, J Roy Statist Soc Ser B 54 pp 41– (1992)
[12] Some results on convex bodies and Banach spaces. Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), 123–160. Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961.
[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 50 pp 1341– (2004)
[17] Gribonval, IEEE Trans Inform Theory 49 pp 3320– (2003)
[18] Johnson, Acta Math 149 pp 71– (1982)
[19] ; ; Extremes and related properties of random sequences and processes. Springer, New York-Berlin, 1983. · Zbl 0518.60021
[20] The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, R.I., 2001.
[21] Mallat, IEEE Trans Signal Process 41 pp 3397– (1993)
[22] ; Asymptotic theory of finite-dimensional normed spaces. Lecture Notes in Mathematics, 1200. Springer, Berlin, 1986.
[23] Natarajan, SIAM J Comput 24 pp 227– (1995)
[24] The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics, 94. Cambridge University Press, Cambridge, 1989.
[25] Empirical processes: theory and applications. NSF-CBMS Regional Conference Series in Probability and Statistics, 2. Institute of Mathematical Statistics, Hayward, Calif.; American Statistical Association, Alexandria, Va., 1990.
[26] Schechtman, Israel J Math 40 pp 187– (1981)
[27] Szarek, Amer J Math 112 pp 899– (1990)
[28] Tropp, IEEE Trans Inform Theory 50 pp 2231– (2004)
[29] Tropp, IEEE Trans Inform Theory
[30] Tsaig, European J Appl Signal Process
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.