For most large underdetermined systems of equations, the minimal l1-norm near-solution approximates the sparsest near-solution

We consider inexact linear equations y approximate to Phi x where y is a given vector in R-n, Phi is a given n x m matrix, and we wish to find x(0,epsilon) as sparse as possible while obeying parallel to y - Phi x(0,epsilon)parallel to(2) <= epsilon. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the l(1)-minimization problem min parallel to x parallel to(1) subject to parallel to y - Phi x parallel to(2) <= epsilon is convex and is considered tractable. We show that for most Phi, if the optimally sparse approximation x(0,epsilon) is sufficiently sparse, then the solution x(1,epsilon) of the l(1)-minimization problem is a good approximation to x(0,epsilon). We suppose that the columns of Phi are normalized to the unit l(2)-norm, and we place uniform measure on such Phi. We study the underdetermined case where m similar to 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 parallel to y - Phi x(0)parallel to(2) < epsilon by a coefficient vector x(0) is an element of R-m with fewer than rho . n nonzeros, parallel to x(1,epsilon) - x(0)parallel to(2) <= C. epsilon. This has two implications. First, for most Phi, whenever the combinatorial optimization result x(0,epsilon) would be very sparse, x(1,epsilon) is a good approximation to x(0,epsilon). 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 parallel to z parallel to(2) <= epsilon. For most Phi, noise-tolerant l(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. (c) 2006 Wiley Periodicals, Inc.