Brief introduction in greedy approximation

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

Sparse approximation is important in many applications because of the concise form of an approximant and good accuracy guarantees. The theory of compressed sensing, which proved to be very useful in the image processing and data sciences, is based on the concept of sparsity. A fundamental issue of sparse approximation is the problem of the construction of efficient algorithms, which provide good approximation. It turns out that greedy algorithms with respect to dictionaries are very good from this point of view. They are simple in implementation, and there are well-developed theoretical guarantees of their efficiency. This survey/tutorial paper contains a brief description of different kinds of greedy algorithms and results on their convergence and rate of convergence. Also, in Sections 14 and 15 we give some typical proofs of convergence and rate of convergence results for important greedy algorithms and in Section 16 we list some open problems.

作者简介

Vladimir Temlyakov

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia; Lomonosov Moscow State University, Moscow, Russia; Moscow Center for Fundamental and Applied Mathematics, Moscow, Russia; University of South Carolina, Columbia, USA

Email: temlyakovv@gmail.com
Doctor of physico-mathematical sciences, Professor

参考

  1. F. Albiac, J. L. Ansorena, V. Temlyakov, “Twenty-five years of greedy bases”, J. Approx. Theory, 307 (2025), 106141, 23 pp.
  2. S. Bahmani, B. Raj, P. T. Boufounos, “Greedy sparsity-constrained optimization”, J. Mach. Learn. Res., 14 (2013), 807–841
  3. A. R. Barron, “Universal approximation bounds for superpositions of a sigmoidal function”, IEEE Trans. Inform. Theory, 39:3 (1993), 930–945
  4. A. R. Barron, A. Cohen, W. Dahmen, R. A. DeVore, “Approximation and learning by greedy algorithms”, Ann. Statist., 36:1 (2008), 64–94
  5. D. Bazarkhanov, V. Temlyakov, “Nonlinear tensor product approximation of functions”, J. Complexity, 31:6 (2015), 867–884
  6. K. L. Clarkson, “Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm”, ACM Trans. Algorithms, 6:4 (2010), 63, 30 pp.
  7. J. A. Cochran, “Composite integral operators and nuclearity”, Ark. Mat., 15:1-2 (1977), 215–222
  8. G. Davis, S. Mallat, M. Avellaneda, “Adaptive greedy approximations”, Constr. Approx., 13:1 (1997), 57–98
  9. A. V. Dereventsov, “On the approximate weak Chebyshev greedy algorithm in uniformly smooth Banach spaces”, J. Math. Anal. Appl., 436:1 (2016), 288–304
  10. A. Dereventsov, Convergence and rate of convergence of approximate greedy-type algorithms, Thesis (Ph. D.), Univ. of South Carolina, 2017, 88 pp.
  11. A. V. Dereventsov, V. N. Temlyakov, “A unified way of analyzing some greedy algorithms”, J. Funct. Anal., 277:12 (2019), 108286, 30 pp.
  12. A. V. Dereventsov, V. N. Temlyakov, “Biorthogonal greedy algorithms in convex optimization”, Appl. Comput. Harmon. Anal., 60:3 (2022), 489–511
  13. R. A. DeVore, V. N. Temlyakov, “Some remarks on greedy algorithms”, Adv. Comput. Math., 5:2-3 (1996), 173–187
  14. R. A. DeVore, V. N. Temlyakov, “Convex optimization on Banach spaces”, Found. Comput. Math., 16:2 (2016), 369–394
  15. S. Dilworth, G. Garrigos, E. Hernandez, D. Kutzarova, V. Temlyakov, “Lebesgue-type inequalities in greedy approximation”, J. Funct. Anal., 280:5 (2021), 108885, 37 pp.
  16. M. J. Donahue, L. Gurvits, C. Darken, E. Sontag, “Rate of convex approximation in non-Hilbert spaces”, Constr. Approx., 13:2 (1997), 187–220
  17. Dinh Dũng, V. Temlyakov, T. Ullrich, Hyperbolic cross approximation, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer, Cham, 2018, xi+218 pp.
  18. M. A. T. Figueiredo, R. D. Nowak, S. J. Wright, “Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems”, IEEE J. Sel. Topics Signal Process, 1:4 (2007), 586–597
  19. S. Foucart, H. Rauhut, A mathematical introduction to compressive sensing, Appl. Numer. Harmon. Anal., Birkhäuser/Springer, New York, 2013, xviii+625 pp.
  20. I. Fredholm, “Sur une classe d'equations fonctionnelles”, Acta Math., 27:1 (1903), 365–390
  21. J. H. Friedman, W. Stuetzle, “Projection pursuit regression”, J. Amer. Statist. Assoc., 76:376 (1981), 817–823
  22. M. Ganichev, N. J. Kalton, “Convergence of the weak dual greedy algorithm in $L_p$-spaces”, J. Approx. Theory, 124:1 (2003), 89–95
  23. Zheming Gao, G. Petrova, “Rescaled pure greedy algorithm for convex optimization”, Calcolo, 56:2 (2019), 15, 14 pp.
  24. A. V. Gasnikov, V. N. Temlyakov, “On greedy approximation in complex Banach spaces”, УМН, 79:6(480) (2024), 39–56
  25. A. C. Gilbert, S. Muthukrishnan, M. J. Strauss, “Approximation of functions over redundant dictionaries using coherence”, Proceedings of the fourteenth annual ACM–SIAM symposium on discrete algorithms (Baltimore, MD, 2003), ACM, New York, 2003, 243–252
  26. E. Hille, J. D. Tamarkin, “On the characteristic values of linear integral equations”, Acta Math., 57:1 (1931), 1–76
  27. P. J. Huber, “Projection pursuit”, Ann. Statist., 13:2 (1985), 435–475
  28. G. Ivanov, “Approximate Caratheodory's theorem in uniformly smooth Banach spaces”, Discrete Comput. Geom., 66:1 (2021), 273–280
  29. M. Jaggi, “Revisiting Frank–Wolfe: projection-free sparse convex optimization”, Proceedings of the 30th international conference on machine learning (Atlanta, GA, 2013), Proc. Mach. Learn. Res. (PMLR), 28, no. 1, 2013, 427–435
  30. L. K. Jones, “On a conjecture of Huber concerning the convergence of projection pursuit regression”, Ann. Statist., 15:2 (1987), 880–882
  31. L. K. Jones, “A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training”, Ann. Statist., 20:1 (1992), 608–613
  32. J. M. Klusowskii, J. W. Siegel, Sharp convergence rates for matching pursuit, 2024 (v1 – 2023), 26 pp.
  33. S. V. Konyagin, V. N. Temlyakov, “A remark on greedy approximation in Banach spaces”, East J. Approx., 5:3 (1999), 365–379
  34. S. V. Konyagin, V. N. Temlyakov, “Rate of convergence of pure greedy algorithm”, East J. Approx., 5:4 (1999), 493–499
  35. E. D. Livshitz, V. N. Temlyakov, “Two lower estimates in greedy approximation”, Constr. Approx., 19:4 (2003), 509–523
  36. E. D. Livshitz, V. N. Temlyakov, “Sparse approximation and recovery by greedy algorithms”, IEEE Trans. Inform. Theory, 60:7 (2014), 3989–4000
  37. Yu. Malykhin, “Matrix and tensor rigidity and $L_p$-approximation”, J. Complexity, 72 (2022), 101651, 13 pp.
  38. G. Petrova, “Rescaled pure greedy algorithm for Hilbert and Banach spaces”, Appl. Comput. Harmon. Anal., 41:3 (2016), 852–866
  39. D. Savu, Sparse approximation in Banach spaces, Thesis (Ph. D.), Univ. of South Carolina, 2009, 67 pp.
  40. D. Savu, V. N. Temlyakov, “Lebesgue-type inequalities for greedy approximation in Banach spaces”, IEEE Trans. Inform. Theory, 59:2 (2013), 1098–1106
  41. E. Schmidt, “Zur Theorie der linearen und nichtlinearen Integralgleichungen. I”, Math. Ann., 63:4 (1907), 433–476
  42. S. Shalev-Shwartz, N. Srebro, Tong Zhang, “Trading accuracy for sparsity in optimization problems with sparsity constraints”, SIAM J. Optim., 20:6 (2010), 2807–2832
  43. F. Smithies, “The eigen-values and singular values of integral equations”, Proc. London Math. Soc. (2), 43:4 (1937), 255–279
  44. V. N. Temlyakov, “Greedy algorithms and $M$-term approximation with regard to redundant dictionaries”, J. Approx. Theory, 98:1 (1999), 117–145
  45. V. N. Temlyakov, “Weak greedy algorithms”, Adv. Comput. Math., 12:2-3 (2000), 213–227
  46. V. N. Temlyakov, “Greedy algorithms in Banach spaces”, Adv. Comput. Math., 14:3 (2001), 277–292
  47. V. N. Temlyakov, “A criterion for convergence of weak greedy algorithms”, Adv. Comput. Math., 17:3 (2002), 269–280
  48. V. N. Temlyakov, “Nonlinear methods of approximation”, Found. Comput. Math., 3:1 (2003), 33–107
  49. V. N. Temlyakov, “Greedy-type approximation in Banach spaces and applications”, Constr. Approx., 21:2 (2005), 257–292
  50. V. N. Temlyakov, “Greedy approximations”, Foundations of computational mathematics (Santander, 2005), London Math. Soc. Lecture Note Ser., 331, Cambridge Univ. Press, Cambridge, 2006, 371–394
  51. V. N. Temlyakov, “Greedy expansions in Banach spaces”, Adv. Comput. Math., 26:4 (2007), 431–449
  52. V. Temlyakov, “Greedy approximation in Banach spaces”, Banach spaces and their applications in analysis, Walter de Gruyter GmbH & Co. KG, Berlin, 2007, 193–208
  53. V. Temlyakov, “Greedy algorithms with prescribed coefficients”, J. Fourier Anal. Appl., 13:1 (2007), 71–86
  54. V. N. Temlyakov, “Relaxation in greedy approximation”, Constr. Approx., 28:2 (2008), 1–25
  55. V. Temlyakov, Greedy approximation, Cambridge Monogr. Appl. Comput. Math., 20, Cambridge Univ. Press, Cambridge, 2011, xiv+418 pp.
  56. V. N. Temlyakov, “Sparse approximation and recovery by greedy algorithms in Banach spaces”, Forum Math. Sigma, 2 (2014), e12, 26 pp.
  57. V. N. Temlyakov, “Greedy approximation in convex optimization”, Constr. Approx., 41:2 (2015), 269–296
  58. V. Temlyakov, Sparse approximation with bases, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer, Basel, 2015, xii+261 pp.
  59. V. Temlyakov, Multivariate approximation, Cambridge Monogr. Appl. Comput. Math., 32, Cambridge Univ. Press, Cambridge, 2018, xvi+534 pp.
  60. V. Temlyakov, “On the rate of convergence of greedy algorithms”, Mathematics, 11:11 (2023), 2559, 15 pp.
  61. A. Tewari, P. K. Ravikumar, I. S. Dhillon, “Greedy algorithms for structurally constrained high dimensional problems”, NIPS {'}11: Proceedings of the 25th international conference on neural information processing systems, Adv. Neural Inf. Process. Syst., 24, MIT Press, Cambridge, MA, 2011, 882–890
  62. H. Weyl, “Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung)”, Math. Ann., 71:4 (1912), 441–479
  63. Tong Zhang, “Sequential greedy approximation for certain convex optimization problems”, IEEE Trans. Inform. Theory, 49:3 (2003), 682–691
  64. P. A. Borodin, E. Kopecka, “Alternating projections, remotest projections, and greedy approximation”, J. Approx. Theory, 260 (2020), 105486, 16 pp.
  65. P. A. Borodin, E. Kopecka, “Convergence of remote projections onto convex sets”, Pure Appl. Funct. Anal., 8:6 (2023), 1603–1620
  66. Ar. R. Valiullin, Al. R. Valiullin, “Sharp conditions for the convergence of greedy expansions with prescribed coefficients”, Open Math., 19:1 (2021), 1–10
  67. Ar. R. Valiullin, Al. R. Valiullin, V. V. Galatenko, “Greedy expansions with prescribed coefficients in Hilbert spaces”, Int. J. Math. Math. Sci., 2018 (2018), 4867091, 6 pp.
  68. Ar. R. Valiullin, Al. R. Valiullin, A. P. Solodov, “Sharp sufficient condition for the convergence of greedy expansions with errors in coefficient computation”, Demonstr. Math., 55:1 (2022), 254–264

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Temlyakov V.N., 2025

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».