On sparse reconstruction from Fourier and Gaussian measurements |
| |
Authors: | Mark Rudelson Roman Vershynin |
| |
Institution: | 1. University of Missouri‐Columbia, Department of Mathematics, Columbia, MO 65211;2. University of California, Davis, Department of Mathematics, Davis, CA 95616 |
| |
Abstract: | 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 Ω such that one can exactly reconstruct every r‐sparse signal f of length n from its frequencies in Ω, using the convex relaxation, and Ω has size A random set Ω satisfies this with high probability. This estimate is optimal within the log logn and log3r factors. We also give a relatively short argument for a similar problem with k(r, n) ≈ r12 + 8 log(n/r)] Gaussian measurements. We use methods of geometric functional analysis and probability theory in Banach spaces, which makes our arguments quite short. © 2007 Wiley Periodicals, Inc. |
| |
Keywords: | |
|
|