  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.
