The restricted isometry property and its implications for compressed sensing
Open accessThe DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
It is now well-known that one can reconstruct sparse or compressible signals accurately from a very limited number of measurements, possibly contaminated with noise. This technique known as “compressed sensing” or “compressive sampling” relies on properties of the sensing matrix such as the restricted isometry property . In this Note, we establish new results about the accuracy of the reconstruction from undersampled measurements which improve on earlier estimates, and have the advantage of being more elegant.
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
Cites
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Stable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036
Self-citation
Cited by
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
(2015) · Cited by 2,857
Subspace Pursuit for Compressive Sensing Signal Reconstruction
Dai, W., & Milenkovic, O. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016006 · Cited by 2,388
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
Eldar, Y. C., Kuppinger, P., & Bolcskei, H. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2044837 · Cited by 1,313
Model-Based Compressive Sensing
Baraniuk, R. G., Cevher, V., Duarte, M. F., & Hegde, C. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2040894 · Cited by 1,308
Elhamifar, E., & Vidal, R. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206547 · Cited by 1,243
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
Mishali, M., & Eldar, Y. C. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042414 · Cited by 1,168
Compressed Channel Sensing: A New Approach to Estimating Sparse Multipath Channels
Bajwa, W. U., Haupt, J., Sayeed, A. M., & Nowak, R. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2042415 · Cited by 1,152
Robust Recovery of Signals From a Structured Union of Subspaces
Eldar, Y. C., & Mishali, M. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2030471 · Cited by 1,044
Sensitivity to Basis Mismatch in Compressed Sensing
Chi, Y., Scharf, L. L., Pezeshki, A., & Calderbank, A. R. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2112650 · Cited by 920
Compressed sensing with coherent and redundant dictionaries
Candès, E. J., Eldar, Y. C., Needell, D., & Randall, P. (2011) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2010.10.002 · Cited by 898
Self-citationNeedell, D., & Vershynin, R. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042412 · Cited by 850
Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0<q⩽1
Foucart, S., & Lai, M.-J. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2008.09.001 · Cited by 715
Best subset selection via a modern optimization lens
Bertsimas, D., King, A., & Mazumder, R. (2016) · The Annals of Statistics · doi:10.1214/15-aos1388 · Cited by 655
Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
Jacques, L., Laska, J. N., Boufounos, P. T., & Baraniuk, R. G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2012.2234823 · Cited by 653
Signal Processing With Compressive Measurements
Davenport, M. A., Boufounos, P. T., Wakin, M. B., & Baraniuk, R. G. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039178 · Cited by 623
Metamaterial Apertures for Computational Imaging
Hunt, J., Driscoll, T., Mrozack, A., Lipworth, G., Reynolds, M., Brady, D., & Smith, D. R. (2013) · Science · doi:10.1126/science.1230054 · Cited by 620
A Probabilistic and RIPless Theory of Compressed Sensing
Candes, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2161794 · Cited by 598
Deep Learning Techniques for Inverse Problems in Imaging
Ongie, G., Jalal, A., Metzler, C. A., Baraniuk, R. G., Dimakis, A. G., & Willett, R. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.2991563 · Cited by 577
Duarte, M. F., & Baraniuk, R. G. (2012) · IEEE Transactions on Image Processing · doi:10.1109/tip.2011.2165289 · Cited by 546
A Systematic Review of Compressive Sensing: Concepts, Implementations and Applications
Rani, M., Dhok, S. B., & Deshmukh, R. B. (2018) · IEEE Access · doi:10.1109/access.2018.2793851 · Cited by 530
Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property
Davenport, M. A., & Wakin, M. B. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2054653 · Cited by 519
Modified-CS: Modifying Compressive Sensing for Problems With Partially Known Support
Vaswani, N., & Lu, W. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2051150 · Cited by 517
Collaborative Sparse Regression for Hyperspectral Unmixing
Iordache, M.-D., Bioucas-Dias, J. M., & Plaza, A. (2014) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2013.2240001 · Cited by 485
Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance
Blumensath, T., & Davies, M. E. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042411 · Cited by 485
Compressive Sensing by Random Convolution
Romberg, J. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/08072975x · Cited by 458
Compressive sensing: From theory to applications, a survey
Qaisar, S., Bilal, R. M., Iqbal, W., Naureen, M., & Lee, S. (2013) · Journal of Communications and Networks · doi:10.1109/jcn.2013.000083 · Cited by 457
Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
Haupt, J., Bajwa, W. U., Raz, G., & Nowak, R. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2070191 · Cited by 424
Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling
Zhu, H., Leus, G., & Giannakis, G. B. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2109956 · Cited by 410
Deep Networks for Direction-of-Arrival Estimation in Low SNR
Papageorgiou, G., Sellathurai, M., & Eldar, Y. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3089927 · Cited by 400
Tillmann, A. M., & Pfetsch, M. E. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2290112 · Cited by 389
Non-convex Optimization for Machine Learning
Jain, P., & Kar, P. (2017) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000058 · Cited by 364
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
Eldar, Y. C., & Rauhut, H. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2034789 · Cited by 356
Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
Vaswani, N., Bouwmans, T., Javed, S., & Narayanamurthy, P. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2826566 · Cited by 356
A deep learning approach to structured signal recovery
Mousavi, A., Patel, A. B., & Baraniuk, R. G. (2015) · 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2015.7447163 · Cited by 355
Koltchinskii, V. (2011) · Lecture Notes in Mathematics · doi:10.1007/978-3-642-22147-7 · Cited by 346
Sparse methods for direction-of-arrival estimation
Yang, Z., Li, J., Stoica, P., & Xie, L. (2018) · Academic Press Library in Signal Processing, Volume 7 · doi:10.1016/b978-0-12-811887-0.00011-0 · Cited by 332
Xenaki, A., Gerstoft, P., & Mosegaard, K. (2014) · The Journal of the Acoustical Society of America · doi:10.1121/1.4883360 · Cited by 326
Distributed Compressed Sensing
Coluccia, G., Ravazzi, C., & Magli, E. (2015) · SpringerBriefs in Electrical and Computer Engineering · doi:10.1007/978-981-287-390-3_2 · Cited by 323
Compressed-Sensing MRI With Random Encoding
Haldar, J. P., Hernando, D., & Liang, Z.-P. (2011) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2010.2085084 · Cited by 308
Saving phase: Injectivity and stability for phase retrieval
Bandeira, A. S., Cahill, J., Mixon, D. G., & Nelson, A. A. (2014) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2013.10.002 · Cited by 301
Non-asymptotic Theory of Random Matrices: Extreme Singular Values
Rudelson, M., & Vershynin, R. (2011) · Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) · doi:10.1142/9789814324359_0111 · Cited by 296
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
Maleki, A., & Donoho, D. L. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039176 · Cited by 289
Hyperspectral Anomaly Detection by the Use of Background Joint Sparse Representation
Li, J., Zhang, H., Zhang, L., & Ma, L. (2015) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2015.2437073 · Cited by 289
Spectral imaging with deep learning
Huang, L., Luo, R., Liu, X., & Hao, X. (2022) · Light: Science & Applications · doi:10.1038/s41377-022-00743-6 · Cited by 283
Overview of Deep Learning-Based CSI Feedback in Massive MIMO Systems
Guo, J., Wen, C.-K., Jin, S., & Li, G. Y. (2022) · IEEE Transactions on Communications · doi:10.1109/tcomm.2022.3217777 · Cited by 278
Zhou, N., Li, H., Wang, D., Pan, S., & Zhou, Z. (2015) · Optics Communications · doi:10.1016/j.optcom.2014.12.084 · Cited by 270
Compressed sensing imaging techniques for radio interferometry
Wiaux, Y., Jacques, L., Puy, G., Scaife, A. M. M., & Vandergheynst, P. (2009) · Monthly Notices of the Royal Astronomical Society · doi:10.1111/j.1365-2966.2009.14665.x · Cited by 269
Compressed Sensing in Astronomy
Bobin, J., Starck, J.-L., & Ottensamer, R. (2008) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2008.2005337 · Cited by 268
ADMiRA: Atomic Decomposition for Minimum Rank Approximation
Lee, K., & Bresler, Y. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2054251 · Cited by 267
Sparse Representation for Wireless Communications: A Compressive Sensing Approach
Qin, Z., Fan, J., Liu, Y., Gao, Y., & Li, G. Y. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2789521 · Cited by 247
“It has been proved that (cid:96) 1 norm results in the same solution as (cid:96) 0 norm when RIP is satisfied with the constant δ 2 k √ 2 − 1 [18].”
BackgroundRecovering Compressively Sampled Signals Using Partial Support Information
Friedlander, M. P., Mansour, H., Saab, R., & Yilmaz, Ö. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2167214 · Cited by 261
Taubock, 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
Stable Image Reconstruction Using Total Variation Minimization
Needell, D., & Ward, R. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120868281 · Cited by 259
Estimation of many-body quantum Hamiltonians via compressive sensing
Shabani, A., Mohseni, M., Lloyd, S., Kosut, R. L., & Rabitz, H. (2011) · Physical Review A · doi:10.1103/physreva.84.012107 · Cited by 78
Representer Theorems for Sparsity-Promoting $\ell _{1}$ Regularization
Unser, M., Fageot, J., & Gupta, H. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2590421 · Cited by 36
“The theory of compressed sensing also provides some guarantees of recovery for K -sparse signals under strict assumptions on the system matrix [6], [29], [30].”
BackgroundSecure and Lightweight Compressive Sensing Using Stream Cipher
Pudi, V., Chattopadhyay, A., & Lam, K.-Y. (2018) · IEEE Transactions on Circuits and Systems II: Express Briefs · doi:10.1109/tcsii.2017.2715659 · Cited by 31
Liu, X., Li, T., Fan, X., & Chen, Z. (2019) · Sensors · doi:10.3390/s19061477 · Cited by 8
Metadata
- Authors
- Candès, E. J.
- Venue
- Comptes Rendus. Mathématique
- Publisher
- MathDoc/Centre Mersenne
- Published
- 2008-04-11
- Volume
- 346
- Issue
- 9-10
- Pages
- 589-592
- ISSN
- 1631-073X (ISSN-L)
- 1778-3569
- OpenAlex
- W2015418199
- Cited by
- 3,686
- References
- 2
- FWCI
- 161.39
- Type
- journal article
- Language
- en
- Open access
- bronze
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.