Geodesic
Lower bounds for the rate of convergence of greedy algorithms
Izvestiya. Mathematics , Tome 73 (2009) no. 6, pp. 1197-1215.

Voir la notice de l'article provenant de la source Math-Net.Ru

We obtain a lower bound for the rate of convergence of a pure greedy algorithm in the spaces $\mathcal A_0(\mathcal D)$ and $\mathcal A_1(\mathcal D)$, and this bound turns out to be very close to the best known upper bound. We also obtain a precise lower bound for the rate of convergence of the orthogonal greedy algorithm in the space $\mathcal A_0(\mathcal D)$.
Keywords: pure greedy algorithm, best $n$-term approximation, rate of convergence.
Mots-clés : interpolation classes 
@article{IM2_2009_73_6_a5,
     author = {E. D. Livshits},
     title = {Lower bounds for the rate of convergence of greedy algorithms},
     journal = {Izvestiya. Mathematics },
     pages = {1197--1215},
     publisher = {mathdoc},
     volume = {73},
     number = {6},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2009_73_6_a5/}
}
TY  - JOUR
AU  - E. D. Livshits
TI  - Lower bounds for the rate of convergence of greedy algorithms
JO  - Izvestiya. Mathematics 
PY  - 2009
SP  - 1197
EP  - 1215
VL  - 73
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2009_73_6_a5/
LA  - en
ID  - IM2_2009_73_6_a5
ER  - 
%0 Journal Article
%A E. D. Livshits
%T Lower bounds for the rate of convergence of greedy algorithms
%J Izvestiya. Mathematics 
%D 2009
%P 1197-1215
%V 73
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2009_73_6_a5/
%G en
%F IM2_2009_73_6_a5
E. D. Livshits. Lower bounds for the rate of convergence of greedy algorithms. Izvestiya. Mathematics , Tome 73 (2009) no. 6, pp. 1197-1215. http://geodesic.mathdoc.fr/item/IM2_2009_73_6_a5/

[1] V. V. Galatenko, E. D. Livshits, “Generalized approximate weak greedy algorithms”, Math. Notes, 78:1–2 (2005), 170–184 | DOI | MR | Zbl

[2] V. N. Temlyakov, “Nonlinear methods of approximation”, Found. Comput. Math., 3:1 (2003), 33–107 | DOI | MR | Zbl

[3] R. A. DeVore, V. N. Temlyakov, “Some remarks on greedy algorithms”, Adv. Comput. Math., 5:1 (1996), 173–187 | DOI | MR | Zbl

[4] V. N. Temlyakov, “Weak greedy algorithms”, Adv. Comput. Math., 12:2–3 (2000), 213–227 | DOI | MR | Zbl

[5] V. V. Galatenko, “Ob odnoi modifikatsii zhadnykh razlozhenii”, Sovremennye metody teorii funktsii i smezhnye problemy. Materialy Voronezhskoi zimnei matematicheskoi shkoly (VGU, Voronezh, 2005), Izd-vo VGU, Voronezh, 2005, 65–66

[6] V. N. Temlyakov, “Greedy algorithms with restricted depth search”, Proc. Steklov Inst. Math., 248:1 (2005), 255–267 | MR | Zbl

[7] 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 | DOI | MR | Zbl

[8] E. D. Livshits, “Rate of convergence of pure greedy algorithms”, Math. Notes, 76:3–4 (2004), 497–510 | DOI | MR | Zbl

[9] S. B. Stechkin, “Ob absolyutnoi skhodimosti ortogonalnykh ryadov”, Dokl. AN SSSR, 102:1 (1955), 37–40 | MR | Zbl

[10] A. R. Barron, “Universal approximation bounds for superpositions of a sigmoidal function”, IEEE Trans. Inform. Theory, 39:3 (1993), 930–945 | DOI | MR | Zbl

[11] S. V. Konyagin, V. N. Temlyakov, “Rate of convergence of pure greedy algorithm”, East J. Approx., 5:4 (1999), 493–499 | MR | Zbl

[12] A. V. Sil'nichenko, “Rate of convergence of greedy algorithms”, Math. Notes, 76:3–4 (2004), 582–586 | DOI | MR | Zbl

[13] E. D. Livshits, “Optimality of the greedy algorithm for some function classes”, Sb. Math., 198:5 (2007), 691–709 | DOI | MR | Zbl

[14] A. R. Barron, A. Cohen, W. Dahmen, R. A. DeVore, “Approximation and learning by greedy algorithms”, Ann. Statist., 36:1 (2008), 64–94 | DOI | MR | Zbl

[15] E. D. Livshitz, V. N. Temlyakov, “Two lower estimates in greedy approximation”, Constr. Approx., 19:4 (2003), 509–523 | DOI | MR | Zbl

[16] J. Bergh, J. Löfström, Interpolation spaces. An introduction, Grundlehren der Mathematischen Wissenschaften, 223, Springer-Verlag, Berlin–Heidelberg–New York, 1976 | MR | MR | Zbl