Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements

Abstract

We want to exactly reconstruct a sparse signal f (a vector in R^n of small support) from few linear measurements of f (inner products with some fixed vectors). A nice and intuitive reconstruction by Linear Programming has been advocated since 80-ies by Dave Donoho and his collaborators. Namely, one can relax the reconstruction problem, which is highly nonconvex, to a convex problem -- and, moreover, to a linear program. However, when is exactly the reconstruction problem equivalent to its convex relaxation is an open question. Recent work of many authors shows that the number of measurements k(r,n) needed to exactly reconstruct any r-sparse signal f of length n (a vector in R^n of support r) from its linear measurements with the convex relaxation method is usually O(r polylog(n)). However, known estimates of the number of measurements k(r,n) involve huge constants, in spite of very good performance of the algorithms in practice. In this paper, we consider random Gaussian measurements and random Fourier measurements (a frequency sample of f). For Gaussian measurements, we prove the first guarantees with reasonable constants: k(r,n) < 12 r (2 + log(n/r)), which is optimal up to constants. For Fourier measurements, we prove the best known bound k(r,n) = O(r log(n) . log^2(r) log(r log n)), which is optimal within the log log n and log^3 r factors. Our arguments are based on the technique of Geometric Functional Analysis and Probability in Banach spaces.

References to related work added

References in corpus (3)

• Near Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Decoding by Linear Programming
• Reconstruction and subgaussian operators

Cited by in corpus (19)

• Sparsity and Incoherence in Compressive Sampling
• Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
• Compressed Sensing and Redundant Dictionaries
• Multi-Label Prediction via Compressed Sensing
• On risk bounds in isotonic and other shape restricted regression problems
• Image formation in synthetic aperture radio telescopes
• Uncertainty Principles and Vector Quantization
• Highly robust error correction by convex programming
• Reconstruction from anisotropic random measurements
• The Gaussian min-max theorem in the Presence of Convexity
• Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit
• Stability results for random sampling of sparse trigonometric polynomials
• Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries
• An Efficient Greedy Algorithm for Sparse Recovery in Noisy Environment
• New Bounds for Restricted Isometry Constants
• Rapidly Computing Sparse Legendre Expansions via Sparse Fourier Transforms
• Compressive Spectral Estimation for Nonstationary Random Processes
• Freedom through Imperfection: Exploiting the flexibility offered by redundancy in signal processing
• Compressed Sensing with Cross Validation