For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution

We consider linear equations y = phi x where y is a given vector in R-n and phi is a given n x m matrix with n < m <= tau n, and we wish to solve for x epsilon R-m. We suppose that the columns of phi are normalized to the unit l(2)-norm, and we place uniform measure on such phi. We prove the existence of rho = rho(tau) > 0 so that for large n and for all Vs except a negligible fraction, the following property holds: For every y having a representation y = phi x(0) by a coefficient vector x(0) epsilon R-m. with fewer than rho center dot n nonzeros, the solution x(1) of the l(1)-minimization problem min parallel to x parallel to(1) subject to phi x = y is unique and equal to x(0). In contrast, heuristic attempts to sparsely solve such systems-greedy algorithms and thresholding-perform poorly ill this challenging setting. The techniques include the use of random proportional embeddings and almost-spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices. (c) 2006 Wiley Periodicals, Inc.