The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Abstract
This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with$m$nonzero entries in dimension$d$given$ {\rm O}(m \ln d)$random linear measurements of that signal. This is a massive improvement over previous results, which require${\rm O}(m^{2})$measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
Matching pursuits with time-frequency dictionaries
Mallat, S. G., & Zhang, Z. (1993) · IEEE Transactions on Signal Processing · doi:10.1109/78.258082 · Cited by 9,112
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
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (2001) · SIAM Review · doi:10.1137/s003614450037906x · Cited by 5,085
Research works printed but not linked: 8
- fernique, 1974, Ecole D'Et� de Probabilit�s de Saint-Flour IV, 480, 1
- 10.1109/ICASSP.2005.1416408 · DOI
- kim, 2007, ?A method for large-scale -regularized least-squares problems with applications in signal processing and statistics ?
- lugosi, 2005, Concentration of Measure Inequalities
- ball, 2002, Handbook of Banach Space Geometry, 161
- 10.1155/IMRN.2005.4019 · doi:10.1155/imrn.2005.4019
- 10.1007/s10208-007-9005-x · DOI
- tropp, 2007, ?Signal recovery from random measurements via orthogonal matching pursuit The Gaussian case ?
Cited by
Items 101–157 of 157
DR2-Net: Deep Residual Reconstruction Network for image compressive sensing
Yao, H., Dai, F., Zhang, S., Zhang, Y., Tian, Q., & Xu, C. (2019) · Neurocomputing · doi:10.1016/j.neucom.2019.05.006 · Cited by 356
Compressed Sensing for Wireless Communications: Useful Tips and Tricks
Choi, J. W., Shim, B., Ding, Y., Rao, B., & Kim, D. I. (2017) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2664421 · Cited by 351
Distributed Compressive Sensing
Baron, D., Duarte, M. F., Wakin, M. B., Sarvotham, S., & Baraniuk, R. G. (2009) · doi:10.21236/ada521228 · Cited by 346
Bayesian sparse representation for hyperspectral image super resolution
Akhtar, N., Shafait, F., & Mian, A. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298986 · Cited by 339
Compressive sensing based channel feedback protocols for spatially-correlated massive antenna arrays
Kuo, P.-H., Kung, H. T., & Ting, P.-A. (2012) · 2012 IEEE Wireless Communications and Networking Conference (WCNC) · doi:10.1109/wcnc.2012.6214417 · Cited by 333
Review of noise removal techniques in ECG signals
Chatterjee, S., Thakur, R. S., Yadav, R. N., Gupta, L., & Raghuvanshi, D. K. (2020) · IET Signal Processing · doi:10.1049/iet-spr.2020.0104 · Cited by 333
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
RF Sensor Networks for Device-Free Localization: Measurements, Models, and Algorithms
Patwari, N., & Wilson, J. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2052010 · Cited by 331
Compressed sensing reconstruction for magnetic resonance parameter mapping
Doneva, M., Börnert, P., Eggers, H., Stehning, C., Sénégas, J., & Mertins, A. (2010) · Magnetic Resonance in Medicine · doi:10.1002/mrm.22483 · Cited by 326
Secure and Robust Iris Recognition Using Random Projections and Sparse Representations
Pillai, J. K., Patel, V. M., Chellappa, R., & Ratha, N. K. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.34 · Cited by 324
An Architecture for Compressive Imaging
Wakin, M. B., Laska, J. N., Duarte, M. F., Baron, D., Sarvotham, S., Takhar, D., Kelly, K. F., & Baraniuk, R. G. (2006) · 2006 International Conference on Image Processing · doi:10.1109/icip.2006.312577 · Cited by 323
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
Sparse Modeling for Image and Vision Processing
Mairal, J. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781680830095 · Cited by 322
Channel Estimation for RIS-Aided mmWave MIMO Systems via Atomic Norm Minimization
He, J., Wymeersch, H., & Juntti, M. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2021.3070064 · Cited by 319
Zhang, L., Xing, M., Qiu, C.-W., Li, J., Sheng, J., Li, Y., & Bao, Z. (2010) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2010.2048575 · Cited by 317
Compressed Sensing System Considerations for ECG and EMG Wireless Biosensors
Dixon, A. M. R., Allstot, E. G., Gangopadhyay, D., & Allstot, D. J. (2012) · IEEE Transactions on Biomedical Circuits and Systems · doi:10.1109/tbcas.2012.2193668 · Cited by 311
AMP-Net: Denoising-Based Deep Unfolding for Compressive Image Sensing
Zhang, Z., Liu, Y., Liu, J., Wen, F., & Zhu, C. (2021) · IEEE Transactions on Image Processing · doi:10.1109/tip.2020.3044472 · Cited by 311
Image super-resolution: A comprehensive review, recent trends, challenges and applications
Lepcha, D. C., Goyal, B., Dogra, A., & Goyal, V. (2023) · Information Fusion · doi:10.1016/j.inffus.2022.10.007 · Cited by 305
A survey of dimensionality reduction techniques
Sorzano, C. Ó. S., Vargas, J., & Pascual-Montano, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1403.2877 · Cited by 305
Li, X., Shen, H., Zhang, L., Zhang, H., Yuan, Q., & Yang, G. (2014) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2014.2307354 · Cited by 299
Real-time visual tracking using compressive sensing
Li, H., Shen, C., & Shi, Q. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995483 · Cited by 297
Reconstructing 3D Human Pose from 2D Image Landmarks
Ramakrishna, V., Kanade, T., & Sheikh, Y. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33765-9_41 · Cited by 296
Active Deep Learning for Classification of Hyperspectral Images
Liu, P., Zhang, H., & Eom, K. B. (2017) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2016.2598859 · Cited by 290
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
Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ Minimization
Chen, X., Xu, F., & Ye, Y. (2010) · SIAM Journal on Scientific Computing · doi:10.1137/090761471 · Cited by 288
Millimeter Wave Beam-Selection Using Out-of-Band Spatial Information
Ali, A., González-Prelcic, N., & Heath, R. W. (2018) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2017.2773532 · Cited by 285
Low-Rank and Sparse Representation for Hyperspectral Image Processing: A review
Peng, J., Sun, W., Li, H.-C., Li, W., Meng, X., Ge, C., & Du, Q. (2022) · IEEE Geoscience and Remote Sensing Magazine · doi:10.1109/mgrs.2021.3075491 · Cited by 285
A Nonlocal Weighted Joint Sparse Representation Classification Method for Hyperspectral Imagery
Zhang, H., Li, J., Huang, Y., & Zhang, L. (2014) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2013.2264720 · Cited by 284
Sparse Spatio-spectral Representation for Hyperspectral Image Super-resolution
Akhtar, N., Shafait, F., & Mian, A. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-10584-0_5 · Cited by 284
Sparse Learning via Iterative Minimization With Application to MIMO Radar Imaging
Tan, X., Roberts, W., Li, J., & Stoica, P. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2096218 · Cited by 284
Channel Estimation for Extremely Large-Scale Massive MIMO Systems
Han, Y., Jin, S., Wen, C.-K., & Ma, X. (2020) · IEEE Wireless Communications Letters · doi:10.1109/lwc.2019.2963877 · Cited by 282
Is face recognition really a Compressive Sensing problem?
Shi, Q., Eriksson, A., van den Hengel, A., & Shen, C. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995556 · Cited by 277
Learning with Structured Sparsity
Huang, J., Zhang, T., & Metaxas, D. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0903.3002 · Cited by 275
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-citationCompressed 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
Bouwmans, T., Sobral, A., Javed, S., Jung, S. K., & Zahzah, E.-H. (2017) · Computer Science Review · doi:10.1016/j.cosrev.2016.11.001 · Cited by 267
Gao, X., Dai, L., Han, S., I, C.-L., & Wang, X. (2017) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2017.2718502 · Cited by 266
Random Filters for Compressive Sampling and Reconstruction
Tropp, J. A., Wakin, M. B., Duarte, M. F., Baron, D., & Baraniuk, R. G. (2006) · 2006 IEEE International Conference on Acoustics Speed and Signal Processing Proceedings · doi:10.1109/icassp.2006.1660793 · Cited by 264
Self-citationTime-Frequency Energy Distributions Meet Compressed Sensing
Flandrin, P., & Borgnat, P. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2044839 · Cited by 264
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
“Another type of solution is to use a greedy algorithm, such as OMP [19], to find a local optimum in each iteration.”
MethodNewtonized Orthogonal Matching Pursuit: Frequency Estimation Over the Continuum
Mamandipoor, B., Ramasamy, D., & Madhow, U. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2580523 · Cited by 262
Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark
Lüthen, N., Marelli, S., & Sudret, B. (2021) · SIAM/ASA Journal on Uncertainty Quantification · doi:10.1137/20m1315774 · Cited by 256
Sparse Signal Reconstruction via Iterative Support Detection
Wang, Y., & Yin, W. (2010) · SIAM Journal on Imaging Sciences · doi:10.1137/090772447 · Cited by 253
Deep Learning for Distributed Channel Feedback and Multiuser Precoding in FDD Massive MIMO
Sohrabi, F., Attiah, K. M., & Yu, W. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2021.3055202 · Cited by 169
Harmless interpolation of noisy data in regression
Muthukumar, V., Vodrahalli, K., & Sahai, A. (2019) · 2019 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849614 · Cited by 162
Hu, L.-L., Chen, M.-X., Wang, M.-M., & Zhou, N.-R. (2024) · Chaos, Solitons & Fractals · doi:10.1016/j.chaos.2024.115521 · Cited by 110
HIERARCHICAL SPARSE BAYESIAN LEARNING FOR STRUCUTRAL HEALTH MONITORING WITH INCOMPLETE MODAL DATA
Huang, Y., & Beck, J. L. (2015) · International Journal for Uncertainty Quantification · doi:10.1615/int.j.uncertaintyquantification.2015011808 · Cited by 87
Multitask Sparse Bayesian Learning with Applications in Structural Health Monitoring
Huang, Y., Beck, J. L., & Li, H. (2019) · Computer-Aided Civil and Infrastructure Engineering · doi:10.1111/mice.12408 · Cited by 79
“This basic framework in Equation (2) is the starting point for many sparse inversion algorithms, including linear programming (Tibshirani, 1996; Cand`es, 2006) and greedy algorithms (Tropp and Gilbert, 2007).”
BackgroundFakePolisher: Making DeepFakes More Detection-Evasive by Shallow Reconstruction
Huang, Y., Juefei-Xu, F., Wang, R., Guo, Q., Ma, L., Xie, X., Li, J., Miao, W., Liu, Y., & Pu, G. (2020) · Proceedings of the 28th ACM International Conference on Multimedia · doi:10.1145/3394171.3413732 · Cited by 71
Chaos and compressive sensing based novel image encryption scheme
Khan, J. S., & Kayhan, S. K. (2021) · Journal of Information Security and Applications · doi:10.1016/j.jisa.2020.102711 · Cited by 65
Adaptive Multivariate Data Compression in Smart Metering Internet of Things
Chowdhury, M. R., Tripathi, S., & De, S. (2021) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2020.2981382 · Cited by 62
Emerging data technology in structural health monitoring: compressive sensing technology
Bao, Y., Li, H., & Ou, J. (2014) · Journal of Civil Structural Health Monitoring · doi:10.1007/s13349-013-0064-1 · Cited by 43
Optimization Beyond Prediction: Prescriptive Price Optimization
Ito, S., & Fujimaki, R. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098188 · Cited by 39
“For the learning algorithm, in principle, any standard algorithm, such as least square regression, ridge regression (L2 regularized), Lasso (L1regularized) [19], or orthogonal matching pursuit (OMP, L0 regularized) [21] would be applicable with our methodology.”
MethodDecomposition Methods for Machine Learning with Small, Incomplete or Noisy Datasets
Caiafa, C. F., Solé-Casals, J., Marti-Puig, P., Zhe, S., & Tanaka, T. (2020) · Applied Sciences · doi:10.3390/app10238481 · Cited by 33
“TK (Tucker) and CP (CANDECOMP/PARAFAC) indicate the decomposition model used by the algorithms.”
MethodInfluentialA closed-loop compressive-sensing-based neural recording system
Zhang, J., Mitra, S., Suo, Y., Cheng, A., Xiong, T., Michon, F., Welkenhuysen, M., Kloosterman, F., Chin, P. S., Hsiao, S., et al. (2015) · Journal of Neural Engineering · doi:10.1088/1741-2560/12/3/036005 · Cited by 33
Fastfood dictionary learning for periocular-based full face hallucination
Juefei-Xu, F., & Savvides, M. (2016) · 2016 IEEE 8th International Conference on Biometrics Theory, Applications and Systems (BTAS) · doi:10.1109/btas.2016.7791174 · Cited by 19
Blind Deconvolution with Non-local Similarity and $l_0$ Sparsity for Noisy Image
Ren, W., Tian, J., & Tang, Y. (2016) · IEEE Signal Processing Letters · doi:10.1109/lsp.2016.2530855 · Cited by 2
Metadata
- Authors
- Tropp, J. A., & Gilbert, A. C.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2007-12
- Volume
- 53
- Issue
- 12
- Pages
- 4655-4666
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2127271355
- Cited by
- 9,653
- References
- 42
- FWCI
- 198.70
- Type
- journal article
- Language
- en
- Open access
- closed
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.