Обзор восстановления по выборке с помощью жадных алгоритмов и $\ell_p$-минимизации
Успехи математических наук · 2026 · 81 (4(490)) · 91-150
DOI: 10.4213/rm10308 ↗Kurz gefasst
Fachartikel in der Zeitschrift Успехи математических наук, online erschienen am 31.07.2026. Verfasst von Feng Dai und 1 weiteren Autor:innen. Die Arbeit nennt 79 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, Ministry of Science and Higher Education of the Russian Federation.
Abstract (Originalsprache)
Восстановление неизвестных функций по конечному числу значений функций в точках (узлах) является фундаментальной задачей чистой и прикладной математики. В данной статье представлен всесторонний обзор последних достижений в области восстановления по выборкам с упором на точность различных алгоритмов и взаимосвязь между оптимальными ошибками восстановления, нелинейной аппроксимацией и поперечниками Колмогорова для классов функций. Центральной темой является синергия между теорией универсальной дискретизации и неравенствами типа Лебега для жадных алгоритмов. Мы обсуждаем три основные алгоритмические структуры: взвешенный метод наименьших квадратов и $\ell_p$-минимизацию; методы разреженной аппроксимации; жадные алгоритмы, такие как слабый ортогональный алгоритм преследования (Weak Orthogonal Matching Pursuit, WOMP) в гильбертовых пространствах и слабый чебышeвский жадный алгоритм (Weak Сhebychev Greedy Algorithm, WCGA) в банаховых пространствах. Эти методы применяются к классам функций, определяемым структурными условиями, таким как $A_\beta^r$ и классы типа Винера, а также к классическим классам типа Соболева с доминирующими смешанными производными. В частности, мы выделяем недавние результаты, показывающие, что нелинейное восстановление по выборкам может обеспечивать более высокие гарантии точности по сравнению с линейными методами для определенных классов многомерных функций. Библиография: 63 названия.
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). Обзор восстановления по выборке с помощью жадных алгоритмов и $\ell_p$-минимизации. Успехи математических наук, 81(4(490)), 91-150. https://doi.org/10.4213/rm10308
Vancouver
Dai F, Temlyakov VN. Обзор восстановления по выборке с помощью жадных алгоритмов и $\ell_p$-минимизации. Успехи математических наук. 2026;81(4(490)):91-150. doi:10.4213/rm10308
BibTeX
@article{Dai2026,
author = {Dai, Feng and Temlyakov, Vladimir Nikolaevich},
title = {Обзор восстановления по выборке с помощью жадных алгоритмов и $\ell_p$-минимизации},
journal = {Успехи математических наук},
year = {2026},
volume = {81},
number = {4(490)},
pages = {91--150},
doi = {10.4213/rm10308}
}
EUVIMED