A survey on sampling recovery by greedy algorithms and $\ell_p$-minimization
Russian Mathematical Surveys · 2026 · 81 (4) · 671-725
DOI: 10.4213/rm10308e ↗Kurz gefasst
Fachartikel in der Zeitschrift Russian Mathematical Surveys, online erschienen am 10.11.2026. Verfasst von Feng Dai und 1 weiteren Autor:innen. Die Arbeit nennt 64 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, Ministry of Science and Higher Education of the Russian Federation.
Abstract (Originalsprache)
The recovery of unknown functions from a finite number of samples is a fundamental challenge in pure and applied mathematics. This survey provides a comprehensive overview of recent developments in sampling recovery, focusing on the accuracy of various algorithms and the relationship between optimal recovery errors, nonlinear approximation, and the Kolmogorov widths of classes of functions. A central theme is the synergy between the theory of universal sampling discretization and Lebesgue-type inequalities for greedy algorithms. We discuss three primary algorithmic frameworks: weighted least squares and $\ell_p$ minimization; sparse approximation methods; and greedy algorithms such as the Weak Orthogonal Matching Pursuit (WOMP) in Hilbert spaces and the Weak Chebyshev Greedy Algorithm (WCGA) in Banach spaces. These methods are applied to classes of functions defined by structural conditions, like the $\mathbf{A}_\beta^r$ and Wiener-type classes, as well as classical Sobolev-type classes with dominated mixed derivatives. Notably, we highlight recent findings showing that nonlinear sampling recovery can provide superior error guarantees in comparison to linear methods for certain multivariate classes of functions. Bibliography: 63 titles.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- Ministry of Science and Higher Education of the Russian Federation
Zitieren
APA
Dai, F., & Temlyakov, V. N. (2026). A survey on sampling recovery by greedy algorithms and $\ell_p$-minimization. Russian Mathematical Surveys, 81(4), 671-725. https://doi.org/10.4213/rm10308e
Vancouver
Dai F, Temlyakov VN. A survey on sampling recovery by greedy algorithms and $\ell_p$-minimization. Russian Mathematical Surveys. 2026;81(4):671-725. doi:10.4213/rm10308e
BibTeX
@article{Dai2026,
author = {Dai, Feng and Temlyakov, Vladimir Nikolaevich},
title = {A survey on sampling recovery by greedy algorithms and $\ell_p$-minimization},
journal = {Russian Mathematical Surveys},
year = {2026},
volume = {81},
number = {4},
pages = {671--725},
doi = {10.4213/rm10308e}
}
EUVIMED