The author studies sparse solutions to underdetermined linear systems where is a given vector and is a given matrix with .
In the last years, a large body of research has focused on the use of overcomplete signal representations. If we have more atoms than observation dimensions, , then there are many possible representations for a given and . The sparse representation problem is then to find the representation with the fewest possible non-zero components,
where is the norm of a vector , 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 () with the ‘relaxed’ problem
where is the norm of a vector . Problem (), 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 () is sparse, it can be the same as the answer to ().
The equivalence breakdown point of a matrix , , is the maximal number such that, for every with fewer than nonzeros, the corresponding vector generates a linear system for which problems () and () have identical unique solutions, both equal to .
The main result of the paper is: For each , there exists a constant so that for every sequence ) with ,
In other words, for the overwhelming majority of matrices , the sparsest possible solution and the minimal -solution of coincide whenever a solution with at most 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 -minimization, which are poorly performed in the setting of the paper.