The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution
Abstract
We consider inexact linear equations y≈ Φ x where y is a given vector in ℝn, Φ is a given n×m matrix, and we wish to find x0,ϵ as sparse as possible while obeying ‖y− Φ x0,ϵ‖2≤ ϵ. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the 𝓁 1‐minimization problem is convex and is considered tractable. We show that for most Φ, if the optimally sparse approximation x0,ϵ is sufficiently sparse, then the solution x1,ϵ of the 𝓁 1‐minimization problem is a good approximation to x0,ϵ. We suppose that the columns of Φ are normalized to the unit 𝓁 2‐norm, and we place uniform measure on such Φ. We study the underdetermined case where m∼ τ n and τ > 1, and prove the existence of ρ = ρ(τ) > 0 and C=C(ρ, τ) so that for large n and for all Φ's except a negligible fraction, the following approximate sparse solution property of Φ holds:for every y having an approximation‖y− Φ x0‖2≤ ϵ by a coefficient vector x0∈ ℝmwith fewer than ρ · n nonzeros, This has two implications. First, for most Φ, whenever the combinatorial optimization result x0,ϵ would be very sparse,x1,ϵ is a good approximation to x0,ϵ. Second, suppose we are given noisy data obeying y= Φ x0+z where the unknown x0 is known to be sparse and the noise ‖z‖2≤ ϵ. For most Φ, noise‐tolerant 𝓁 1‐minimization will stably recover x0 from y in the presence of noise z. We also study the barely determined case m=n and reach parallel conclusions by slightly different arguments. Proof techniques include the use of almost‐spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices. © 2006 Wiley Periodicals, Inc.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Self-citationGreed 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
The Symmetric Eigenvalue Problem
Parlett, B. N. (1998) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971163 · Cited by 3,192
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-citationSparse Approximate Solutions to Linear Systems
Natarajan, B. K. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792240406 · Cited by 2,783
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
Self-citationStable recovery of sparse overcomplete representations in the presence of noise
Donoho, D. L., Elad, M., & Temlyakov, V. N. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.860430 · Cited by 2,183
Self-citationUncertainty principles and ideal atomic decomposition
Donoho, D. L., & Huo, X. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.959265 · Cited by 1,949
Self-citationThe Concentration of Measure Phenomenon
Ledoux, M. (2005) · Mathematical Surveys and Monographs · doi:10.1090/surv/089 · Cited by 1,700
Eigenvalues and Condition Numbers of Random Matrices
Edelman, A. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609045 · Cited by 1,284
The Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 967
Sparse representations in unions of bases
Gribonval, R., & Nielsen, M. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.820031 · Cited by 960
Asymptotic Theory of Finite Dimensional Normed Spaces
(1986) · Lecture Notes in Mathematics · doi:10.1007/bfb0075912 · Cited by 778
A generalized uncertainty principle and sparse representation in pairs of bases
Elad, M., & Bruckstein, A. M. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.801410 · Cited by 673
On Sparse Representations in Arbitrary Redundant Bases
Fuchs, J.-J. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.828141 · Cited by 563
Local Operator Theory, Random Matrices and Banach Spaces
(2001) · Handbook of the Geometry of Banach Spaces · doi:10.1016/s1874-5849(01)80010-3 · Cited by 432
The dimension of almost spherical sections of convex bodies
Figiel, T., Lindenstrauss, J., & Milman, V. D. (1977) · Acta Mathematica · doi:10.1007/bf02392234 · Cited by 401
Maximum Entropy and the Nearly Black Object
Donoho, D. L., Johnstone, I. M., Hoch, J. C., & Stern, A. S. (1992) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1992.tb01864.x · Cited by 393
Self-citationRecovery 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
Signal processing and compression with wavelet packets
Coifman, R. R., Meyer, Y., Quake, S., & Wickerhauser, M. V. (1994) · Wavelets and Their Applications · doi:10.1007/978-94-011-1028-0_18 · Cited by 276
Condition numbers of random matrices
Szarek, S. J. (1991) · Journal of Complexity · doi:10.1016/0885-064x(91)90002-f · Cited by 165
Just relax: Convex programming methods for subset selection and sparse approximation
Tropp, J. A. (2004) · Cited by 77
Spaces with Large Distance to ℓ n ∞ and Random Matrices
Szarek, S. J. (1990) · American Journal of Mathematics · doi:10.2307/2374731 · Cited by 73
Cited by
$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
Robust Face Recognition via Sparse Representation
Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., & Ma, Y. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.79 · Cited by 9,388
Image Super-Resolution Via Sparse Representation
Yang, J., Wright, J., Huang, T. S., & Ma, Y. (2010) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2050625 · Cited by 5,217
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-citationConvex multi-task feature learning
Argyriou, A., Evgeniou, T., & Pontil, M. (2008) · Machine Learning · doi:10.1007/s10994-007-5040-8 · Cited by 1,528
Metadata
- Authors
- Donoho, D. L.
- Venue
- Communications on Pure and Applied Mathematics
- Publisher
- Wiley
- Published
- 2006-03-21
- Volume
- 59
- Issue
- 7
- Pages
- 907-934
- ISSN
- 0010-3640 (ISSN-L)
- 1097-0312
- OpenAlex
- W2114147096
- Cited by
- 634
- References
- 28
- FWCI
- 49.40
- 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.