On greedy approximation in complex Banach spaces

Cover Page

Cite item

Full Text

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

Abstract

The general theory of greedy approximation with respect to arbitrary dictionaries is well developed in the case of real Banach spaces. Recently some results proved for the Weak Chebyshev Greedy Algorithm (WCGA) in the case of real Banach spaces were extended to the case of complex Banach spaces. In this paper we extend some of the results known in the real case for greedy algorithms other than the WCGA to the case of complex Banach spaces.Bibliography: 25 titles.

About the authors

Alexander Vladimirovich Gasnikov

Ivannikov Institute for System Programming of the RAS; Steklov Mathematical Institute of Russian Academy of Sciences; Innopolis University

Author for correspondence.
Email: gasnikov@yandex.ru
ORCID iD: 0000-0002-7386-039X
Scopus Author ID: 15762551000
ResearcherId: L-6371-2013
Doctor of physico-mathematical sciences, Associate professor

Vladimir Nikolaevich Temlyakov

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

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

References

  1. A. R. Barron, “Universal approximation bounds for superposition of a sigmoidal functions”, IEEE Trans. Inform. Theory, 39:3 (1993), 930–945
  2. A. R. Barron, A. Cohen, W. Dahmen, R. DeVore, “Approximation and learning by greedy algorithms”, Ann. Statist., 36:1 (2008), 64–94
  3. K. L. Clarkson, “Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm”, ACM Trans. Algorithms, 6:4 (2010), 63, 30 pp.
  4. G. Davis, S. Mallat, M. Avellaneda, “Adaptive greedy approximations”, Constr. Approx., 13:1 (1997), 57–98
  5. A. V. Dereventsov, V. N. Temlyakov, “A unified way of analyzing some greedy algorithms”, J. Funct. Anal., 277:12 (2019), 108286, 30 pp.
  6. A. Dereventsov, V. Temlyakov, “Biorthogonal greedy algorithms in convex optimization”, Appl. Comput. Harmon. Anal., 60 (2022), 489–511
  7. R. A. DeVore, V. N. Temlyakov, “Some remarks on greedy algorithms”, Adv. Comput. Math., 5:2-3 (1996), 173–187
  8. R. A. DeVore, V. N. Temlyakov, “Convex optimization on Banach spaces”, Found. Comput. Math., 16:2 (2016), 369–394
  9. 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.
  10. M. J. Donahue, L. Gurvits, C. Darken, E. Sontag, “Rate of convex approximation in non-Hilbert spaces”, Constr. Approx., 13:2 (1997), 187–220
  11. 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. Top. Signal Process., 1:4 (2007), 586–597
  12. J. H. Friedman, W. Stuetzle, “Projection pursuit regression”, J. Amer. Statist. Assoc., 76:376 (1981), 817–823
  13. M. Ganichev, N. J. Kalton, “Convergence of the weak dual greedy algorithm in $L_p$-spaces”, J. Approx. Theory, 124:1 (2003), 89–95
  14. Zheming Gao, G. Petrova, “Rescaled pure greedy algorithm for convex optimization”, Calcolo, 56:2 (2019), 15, 14 pp.
  15. P. J. Huber, “Projection pursuit”, Ann. Statist., 13:2 (1985), 435–475
  16. M. Jaggi, “Revisiting Frank–Wolfe: projection-free sparse convex optimization”, Proceedings of the 30th international conference on machine learning, Proceedings of Machine Learning Research (PMLR), 28, no. 1, 2013, 427–435
  17. L. K. Jones, “On a conjecture of Huber concerning the convergence of projection pursuit regression”, Ann. Statist., 15:2 (1987), 880–882
  18. 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
  19. 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
  20. V. N. Temlyakov, “Greedy algorithms in Banach spaces”, Adv. Comput. Math., 14:3 (2001), 277–292
  21. V. N. Temlyakov, “Greedy-type approximation in Banach spaces and applications”, Constr. Approx., 21:2 (2005), 257–292
  22. V. Temlyakov, Greedy approximation, Cambridge Monogr. Appl. Comput. Math., 20, Cambridge Univ. Press, Cambridge, 2011, xiv+418 pp.
  23. V. Temlyakov, Multivariate approximation, Cambridge Monogr. Appl. Comput. Math., 32, Cambridge Univ. Press, Cambridge, 2018, xvi+534 pp.
  24. A. Tewari, P. K. Ravikumar, I. S. Dhillon, “Greedy algorithms for structurally constrained high dimensional problems”, Adv. Neural Inf. Process. Syst., 24, NIPS 2011, MIT Press, Cambridge, MA, 2011, 882–890
  25. Tong Zhang, “Sequential greedy approximation for certain convex optimization problems”, IEEE Trans. Inform. Theory, 49:3 (2003), 682–691

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Гасников А.V., Темляков В.N.

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

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») на элемент с текстом «Принять и продолжить».