Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements

Details Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements

2006-02-24

arxiv.org/abs/math/0602559v2

Mathematics

Numerical Analysis

References to related work added

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224182