EUVIMEDEUVIMED entdecken
Crossref

A survey on sampling recovery by greedy algorithms and $\ell_p$-minimization

Feng Dai, Vladimir Nikolaevich Temlyakov

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →