The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Stable recovery of sparse overcomplete representations in the presence of noise
Abstract
Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.
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
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
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
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
Self-citationPati, Y. C., Rezaiifar, R., & Krishnaprasad, P. S. (2002) · Proceedings of 27th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.1993.342465 · Cited by 4,323
Sparse coding with an overcomplete basis set: A strategy employed by V1?
Olshausen, B. A., & Field, D. J. (1997) · Vision Research · doi:10.1016/s0042-6989(97)00169-7 · Cited by 3,642
Greed is Good: Algorithmic Results for Sparse Approximation
Tropp, J. A. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834793 · Cited by 3,635
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
Donoho, D. L., & Elad, M. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0437847100 · Cited by 2,898
Self-citation
Cited by
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Self-citation$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
Aharon, M., Elad, M., & Bruckstein, A. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.881199 · Cited by 9,451
Self-citationStable 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
Sparse MRI: The application of compressed sensing for rapid MR imaging
Lustig, M., Donoho, D., & Pauly, J. M. (2007) · Magnetic Resonance in Medicine · doi:10.1002/mrm.21391 · Cited by 6,952
Self-citationImage Denoising Via Sparse and Redundant Representations Over Learned Dictionaries
Elad, M., & Aharon, M. (2006) · IEEE Transactions on Image Processing · doi:10.1109/tip.2006.881969 · Cited by 5,321
Self-citationRegression Shrinkage and Selection via The Lasso: A Retrospective
Tibshirani, R. (2011) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2011.00771.x · Cited by 3,589
Figueiredo, M. A. T., Nowak, R. D., & Wright, S. J. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910281 · Cited by 3,524
A sparse signal reconstruction perspective for source localization with sensor arrays
Malioutov, D., Cetin, M., & Willsky, A. S. (2005) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.850882 · Cited by 2,638
“For the latter two, it has been shown recently that if is “sparse enough” with respect to , then these approximations in fact lead to exact solutions (see [18], [20]–[24] for precise definitions of these notions).2 In addition, [ 26 ] and [27] showed that with sufficient sparsity and a favorable structure of the overc…”
BackgroundResultDonoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
Self-citationSimultaneous analysis of Lasso and Dantzig selector
Bickel, P. J., Ritov, Y., & Tsybakov, A. B. (2009) · The Annals of Statistics · doi:10.1214/08-aos620 · Cited by 2,396
From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
Bruckstein, A. M., Donoho, D. L., & Elad, M. (2009) · SIAM Review · doi:10.1137/060657704 · Cited by 2,183
Self-citationAn Interior-Point Method for Large-Scale -Regularized Least Squares
Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910971 · Cited by 2,083
Sparse Reconstruction by Separable Approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016892 · Cited by 1,854
Just relax: convex programming methods for identifying sparse signals in noise
Tropp, J. A. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.864420 · Cited by 1,407
Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit
Tropp, J. A., Gilbert, A. C., & Strauss, M. J. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.030 · Cited by 1,347
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
Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise
Cai, T. T., & Wang, L. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2146090 · Cited by 1,265
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016018 · Cited by 1,198
Structured Compressed Sensing: From Theory to Applications
Duarte, M. F., & Eldar, Y. C. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2161982 · Cited by 1,128
A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm
Mohimani, H., Babaie-Zadeh, M., & Jutten, C. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2007606 · Cited by 1,091
MR Image Reconstruction From Highly Undersampled k-Space Data by Dictionary Learning
Ravishankar, S., & Bresler, Y. (2011) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2010.2090538 · Cited by 1,059
Sparse Unmixing of Hyperspectral Data
Iordache, M.-D., Bioucas-Dias, J. M., & Plaza, A. (2011) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2010.2098413 · Cited by 1,056
Computational Methods for Sparse Solution of Linear Inverse Problems
Tropp, J. A., & Wright, S. J. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044010 · Cited by 1,046
A Constrained ℓ1Minimization Approach to Sparse Precision Matrix Estimation
Cai, T., Liu, W., & Luo, X. (2011) · Journal of the American Statistical Association · doi:10.1198/jasa.2011.tm10155 · Cited by 973
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
Extensions of compressed sensing
Tsaig, Y., & Donoho, D. L. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.029 · Cited by 947
Self-citationSimultaneous cartoon and texture image inpainting using morphological component analysis (MCA)
Elad, M., Starck, J.-L., Querre, P., & Donoho, D. L. (2005) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2005.03.005 · Cited by 904
Self-citationNeedell, D., & Vershynin, R. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042412 · Cited by 850
Roth, S., & Black, M. J. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0197-6 · Cited by 847
On 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
Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
Donoho, D. L., & Tsaig, Y. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.929958 · Cited by 829
Self-citationTheoretical Results on Sparse Representations of Multiple-Measurement Vectors
Chen, J., & Huo, X. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.881263 · Cited by 810
Comparing Measures of Sparsity
Hurley, N., & Rickard, S. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2027527 · Cited by 757
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
Analysis versus synthesis in signal priors
Elad, M., Milanfar, P., & Rubinstein, R. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/007 · Cited by 698
Self-citationAlgorithms for simultaneous sparse approximation. Part II: Convex relaxation
Tropp, J. A. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.031 · Cited by 691
Least Squares After Model Selection in High-Dimensional Sparse Models
Belloni, A., & Chernozhukov, V. (2009) · SSRN Electronic Journal · doi:10.2139/ssrn.1582594 · Cited by 683
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20131 · Cited by 634
Self-citationKim, S.-J., Koh, K., Boyd, S., & Gorinevsky, D. (2009) · SIAM Review · doi:10.1137/070690274 · Cited by 615
Compressive data gathering for large-scale wireless sensor networks
Luo, C., Wu, F., Sun, J., & Chen, C. W. (2009) · Proceedings of the 15th annual international conference on Mobile computing and networking · doi:10.1145/1614320.1614337 · Cited by 578
Graph Regularized Sparse Coding for Image Representation
Zheng, M., Bu, J., Chen, C., Wang, C., Zhang, L., Qiu, G., & Cai, D. (2011) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2090535 · Cited by 562
Compressed 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
Lasso-type recovery of sparse representations for high-dimensional data
Meinshausen, N., & Yu, B. (2009) · The Annals of Statistics · doi:10.1214/07-aos582 · Cited by 489
Learning Multiscale Sparse Representations for Image and Video Restoration
Mairal, J., Sapiro, G., & Elad, M. (2008) · Multiscale Modeling & Simulation · doi:10.1137/070697653 · Cited by 460
Self-citationMinimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
Raskutti, G., Wainwright, M. J., & Yu, B. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2165799 · Cited by 455
Robust PCA via Outlier Pursuit
Xu, H., Caramanis, C., & Sanghavi, S. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2173156 · Cited by 445
Redundant Multiscale Transforms and Their Application for Morphological Component Separation
Starck, J.-L., Elad, M., & Donoho, D. (2004) · Advances in Imaging and Electron Physics · doi:10.1016/s1076-5670(04)32006-9 · Cited by 443
Self-citationCompressed Synthetic Aperture Radar
Patel, V. M., Easley, G. R., Healy, D. M., & Chellappa, R. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039181 · Cited by 440
A non-adapted sparse approximation of PDEs with stochastic inputs
Doostan, A., & Owhadi, H. (2011) · Journal of Computational Physics · doi:10.1016/j.jcp.2011.01.002 · Cited by 436
Modern regularization methods for inverse problems
Benning, M., & Burger, M. (2018) · Acta Numerica · doi:10.1017/s0962492918000016 · Cited by 412
Temlyakov, V. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511762291 · Cited by 409
Self-citationImage Denoising Via Learned Dictionaries and Sparse representation
Elad, M., & Aharon, M. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06) · doi:10.1109/cvpr.2006.142 · Cited by 378
Self-citationA unified Bayesian framework for MEG/EEG source imaging
Wipf, D., & Nagarajan, S. (2009) · NeuroImage · doi:10.1016/j.neuroimage.2008.02.059 · Cited by 350
Koltchinskii, V. (2011) · Lecture Notes in Mathematics · doi:10.1007/978-3-642-22147-7 · Cited by 346
Oracle inequalities and optimal inference under group sparsity
Lounici, K., Pontil, M., van de Geer, S., & Tsybakov, A. B. (2011) · The Annals of Statistics · doi:10.1214/11-aos896 · Cited by 341
Direction-of-Arrival Estimation Using a Mixed $\ell _{2,0}$ Norm Approximation
Hyder, M. M., & Mahata, K. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2050477 · Cited by 325
Image Sequence Denoising via Sparse and Redundant Representations
Protter, M., & Elad, M. (2009) · IEEE Transactions on Image Processing · doi:10.1109/tip.2008.2008065 · Cited by 323
Self-citationDistributed 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
Recovery of Exact Sparse Representations in the Presence of Bounded Noise
Fuchs, J. J. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.855614 · Cited by 314
Compression of facial images using the K-SVD algorithm
Bryt, O., & Elad, M. (2008) · Journal of Visual Communication and Image Representation · doi:10.1016/j.jvcir.2008.03.001 · Cited by 311
Self-citationCompressed-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
A Compressive Sensing Data Acquisition and Imaging Method for Stepped Frequency GPRs
Gurbuz, A. C., McClellan, J. H., & Scott, W. R. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016270 · Cited by 306
Near-ideal model selection by ℓ1 minimization
Candès, E. J., & Plan, Y. (2009) · The Annals of Statistics · doi:10.1214/08-aos653 · Cited by 302
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
Self-citationOn the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
Bruckstein, A. M., Elad, M., & Zibulevsky, M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.929920 · Cited by 285
Self-citationBayesian linear regression with sparse priors
Castillo, I., Schmidt-Hieber, J., & van der Vaart, A. (2015) · The Annals of Statistics · doi:10.1214/15-aos1334 · Cited by 277
Time-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
Sparsity oracle inequalities for the Lasso
Bunea, F., Tsybakov, A., & Wegkamp, M. (2007) · Electronic Journal of Statistics · doi:10.1214/07-ejs008 · Cited by 253
A Direct Estimation Approach to Sparse Linear Discriminant Analysis
Cai, T., & Liu, W. (2011) · Journal of the American Statistical Association · doi:10.1198/jasa.2011.tm11199 · Cited by 253
A unified approach to model selection and sparse recovery using regularized least squares
Lv, J., & Fan, Y. (2009) · The Annals of Statistics · doi:10.1214/09-aos683 · Cited by 252
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
Metadata
- Authors
- Donoho, D. L., Elad, M., & Temlyakov, V. N.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2006-01
- Volume
- 52
- Issue
- 1
- Pages
- 6-18
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2097323375
- Cited by
- 2,183
- References
- 35
- FWCI
- 80.06
- 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.