Greedy Approximation
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
This first book on greedy approximation gives a systematic presentation of the fundamental results. It also contains an introduction to two hot topics in numerical mathematics: learning theory and compressed sensing. Nonlinear approximation is becoming increasingly important, especially since two types are frequently employed in applications: adaptive methods are used in PDE solvers, while m-term approximation is used in image/signal/data processing, as well as in the design of neural networks. The fundamental question of nonlinear approximation is how to devise good constructive methods (algorithms) and recent results have established that greedy type algorithms may be the solution. The author has drawn on his own teaching experience to write a book ideally suited to graduate courses. The reader does not require a broad background to understand the material. Important open problems are included to give students and professionals alike ideas for further research.
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
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
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
Ideal spatial adaptation by wavelet shrinkage
Donoho, D. L., & Johnstone, I. M. (1994) · Biometrika · doi:10.1093/biomet/81.3.425 · Cited by 8,760
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
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
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
Entropy-based algorithms for best basis selection
Coifman, R. R., & Wickerhauser, M. V. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119732 · Cited by 3,188
Universal approximation bounds for superpositions of a sigmoidal function
Barron, A. R. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256500 · Cited by 2,804
DeVore, R. A., & Lorentz, G. G. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-02888-9 · Cited by 2,352
Friedman, J. H., & Stuetzle, W. (1981) · Journal of the American Statistical Association · doi:10.1080/01621459.1981.10477729 · Cited by 2,216
Stable 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-citationOn the mathematical foundations of learning
Cucker, F., & Smale, S. (2001) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-01-00923-5 · Cited by 1,545
Weyl, H. (1912) · Mathematische Annalen · doi:10.1007/bf01456804 · Cited by 1,288
Huber, P. J. (1985) · The Annals of Statistics · doi:10.1214/aos/1176349519 · Cited by 1,277
Approximation of Functions of Several Variables and Imbedding Theorems
Nikol’skii, S. M. (1975) · Springer eBooks · doi:10.1007/978-3-642-65711-5 · Cited by 1,197
Adaptive greedy approximations
Davis, G., Mallat, S., & Avellaneda, M. (1997) · Constructive Approximation · doi:10.1007/bf02678430 · Cited by 1,166
Schmidt, E. (1907) · Mathematische Annalen · doi:10.1007/bf01449770 · Cited by 973
Grassmannian frames with applications to coding and communication
Strohmer, T., & Heath, R. W. (2003) · Applied and Computational Harmonic Analysis · doi:10.1016/s1063-5203(03)00023-x · Cited by 955
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
Some remarks on greedy algorithms
DeVore, R., & Temlyakov, V. N. (1996) · Advances in Computational Mathematics · doi:10.1007/bf02124742 · Cited by 646
Self-citationJones, L. K. (1992) · The Annals of Statistics · doi:10.1214/aos/1176348546 · Cited by 474
Unconditional Bases Are Optimal Bases for Data Compression and for Statistical Estimation
Donoho, D. L. (1993) · Applied and Computational Harmonic Analysis · doi:10.1006/acha.1993.1008 · Cited by 421
Irregularities of Distribution
Beck, J., & Chen, W. (1987) · Cambridge University Press eBooks · doi:10.1017/cbo9780511565984 · Cited by 387
Nonlinear Methods of Approximation
Temlyakov, V. N. (2003) · Foundations of Computational Mathematics · doi:10.1007/s102080010029 · Cited by 309
Self-citationSparse Components of Images and Optimal Atomic Decompositions
Donoho, D. L. (2001) · Constructive Approximation · doi:10.1007/s003650010032 · Cited by 230
CART and best-ortho-basis: a connection
Donoho, D. L. (1997) · The Annals of Statistics · doi:10.1214/aos/1069362377 · Cited by 210
Entropy numbers, s-numbers, and eigenvalue problems
Carl, B. (1981) · Journal of Functional Analysis · doi:10.1016/0022-1236(81)90076-8 · Cited by 196
On a Conjecture of Huber Concerning the Convergence of Projection Pursuit Regression
Jones, L. K. (1987) · The Annals of Statistics · doi:10.1214/aos/1176350382 · Cited by 193
Greedy Algorithm for General Biorthogonal Systems
Wojtaszczyk, P. (2000) · Journal of Approximation Theory · doi:10.1006/jath.2000.3512 · Cited by 175
Efficient agnostic learning of neural networks with bounded fan-in
Lee, W. S., Bartlett, P. L., & Williamson, R. C. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556601 · Cited by 165
Hyperbolic Wavelet Approximation
DeVore, R., Konyagin, S. V., & Temlyakov, V. N. (1997) · Constructive Approximation · doi:10.1007/s003659900060 · Cited by 135
Self-citationGreedy Algorithms andM-Term Approximation with Regard to Redundant Dictionaries
Temlyakov, V. N. (1999) · Journal of Approximation Theory · doi:10.1006/jath.1998.3265 · Cited by 86
Self-citationSimultaneous approximation by greedy algorithms
Leviatan, D., & Temlyakov, V. N. (2006) · Advances in Computational Mathematics · doi:10.1007/s10444-004-7613-4 · Cited by 63
Self-citationLutoborski, A., & Temlyakov, V. N. (2003) · Journal of Complexity · doi:10.1016/s0885-064x(03)00026-8 · Cited by 30
Self-citationConvergence of the weak dual greedy algorithm in L-spaces
Ganichev, M., & Kalton, N. J. (2003) · Journal of Approximation Theory · doi:10.1016/s0021-9045(03)00133-3 · Cited by 22
Metadata
- Authors
- Temlyakov, V.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2011-09-08
- Volume
- 17
- Pages
- 235-409
- OpenAlex
- W2913975905
- Cited by
- 409
- References
- 36
- FWCI
- 1.97
- Type
- book
- 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.