The DOI matches its Crossref record.
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
Open accessAbstract
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (random sample of frequencies of f) and random Gaussian measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly non-convex problem to a convex problem, and then solve it as a linear program. What are best guarantees for the reconstruction problem to be equivalent to its convex relaxation is an open question. Recent work shows that the number of measurements k(r,n) needed to exactly reconstruct any r-sparse signal f of length n from its linear measurements with convex relaxation is usually O(r poly log (n)). However, known guarantees involve huge constants, in spite of very good performance of the algorithms in practice. In attempt to reconcile theory with practice, we prove the first guarantees for universal measurements (i.e. which work for all sparse functions) with reasonable constants. For Gaussian measurements, k(r,n) lsim 11.7 r [1.5 + 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) middot log2(r) log(r log n)), which is optimal within the log log n and log3r factors. Our arguments are based on the technique of geometric functional analysis and probability in Banach spaces.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
An Introduction To Compressive Sampling
Candes, E. J., & Wakin, M. B. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914731 · Cited by 10,017
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candes, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,839
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Needell, D., & Tropp, J. A. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2008.07.002 · Cited by 4,326
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Iterative hard thresholding for compressed sensing
Blumensath, T., & Davies, M. E. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2009.04.002 · Cited by 2,275
Sparsity and incoherence in compressive sampling
Candès, E., & Romberg, J. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/008 · Cited by 2,075
Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
Tropp, J. A., Laska, J. N., Duarte, M. F., Romberg, J. K., & Baraniuk, R. G. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2034811 · Cited by 1,089
Imaging via Compressive Sampling
Romberg, J. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914729 · Cited by 1,014
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit
Needell, D., & Vershynin, R. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-008-9031-3 · Cited by 952
Self-citationOn sparse reconstruction from Fourier and Gaussian measurements
Rudelson, M., & Vershynin, R. (2008) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20227 · Cited by 847
Self-citationCompressed Sensing and Redundant Dictionaries
Rauhut, H., Schnass, K., & Vandergheynst, P. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.920190 · Cited by 541
Highly Undersampled Magnetic Resonance Image Reconstruction via Homotopic $\ell_{0}$-Minimization
Trzasko, J., & Manduca, A. (2009) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2008.927346 · Cited by 490
One sketch for all: fast algorithms for compressed sensing
Gilbert, A. C., Strauss, M. J., Tropp, J. A., & Vershynin, R. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250824 · Cited by 270
Self-citationTaubock, G., Hlawatsch, F., Eiwen, D., & Rauhut, H. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042410 · Cited by 260
Metadata
- Authors
- Rudelson, M., & Vershynin, R.
- Venue
- 2006 40th Annual Conference on Information Sciences and Systems
- Publisher
- IEEE
- Published
- 2006-03
- Pages
- 207-212
- OpenAlex
- W2097476744
- Cited by
- 248
- References
- 0
- FWCI
- 55.21
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.