On sparse reconstruction from Fourier and Gaussian measurements

This paper improves upon best-known guarantees for exact reconstruction of a sparse signal f from a small universal sample of Fourier measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly nonconvex problem to a convex problem and then solve it as a linear program. We show that there exists a set of frequencies Omega such that one can exactly reconstruct every r-sparse signal f of length n from its frequencies in Omega, using the convex relaxation, and Omega has size [GRAPHICS] A random set Omega satisfies this with high probability. This estimate is optimal within the log log n and log(3) r factors. We also give a relatively short argument for a similar problem with k(r,n) approximate to r[12 + 8log(n/r)] Gaussian measurements. We use methods of geometric functional analysis and probability theory in Banach spaces, which makes our arguments quite short. (c) 2007 Wiley Periodicals, Inc.