Brief introduction in greedy approximation

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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.

About the authors

Vladimir Nikolaevich 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

References

  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

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Temlyakov V.N.

Согласие на обработку персональных данных

 

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