Greedy Algorithms with Restricted Depth Search

V. N. Temlyakov

Informatics and Automation, Studies on function theory and differential equations, Tome 248 (2005), pp. 262-274.

Résumé

We continue to study the efficiency of approximation and the convergence of greedy-type algorithms in uniformly smooth Banach spaces. This paper is a development of the author's two recent papers on making practical algorithms out of theoretical approximation methods. The weak Chebyshev greedy algorithm (WCGA) has been introduced and studied in previous works. The WCGA is a general approximation method that works well in an arbitrary uniformly smooth Banach space $X$ for any dictionary $\mathcal D$. It is an inductive procedure with each step of implementation consisting of several substeps. We describe the first substep of a particular case of the WCGA. Let $t\in (0,1]$. Then, at the first substep of the $m$th step, we look for an element $\varphi _m$ from a given symmetric dictionary $\mathcal D$ that satisfies $F_{f_{m-1}}(\varphi _m)\ge t\sup _{g\in \mathcal D} F_{f_{m-1}}(g)$, where $f_{m-1}$ is a residual after the $(m-1)$th step and $F_{f_{m-1}}$ is a norming functional of $f_{m-1}$. This is a greedy step of the WCGA. It is clear that in the case of an infinite dictionary $\mathcal D$, there is no direct computationally feasible way of evaluating $\sup _{g\in \mathcal D}F_{f_{m-1}}(g)$. This is the main issue that we address in the paper. We consider countable dictionaries $\mathcal D=\{\pm \psi _j\}_{j=1}^\infty$ and replace the inequality used above by $F_{f_{m-1}}(\varphi _m)\ge t\sup _{1\le j\le N_m}|F_{f_{m-1}}(\psi _j)|$, $\varphi _m\in \{\pm \psi _j\}_{j=1}^{N_m}$. The restriction $j\le N_m$ is known in the literature as the depth search condition. We prove convergence and rate-of-convergence results for such a modification of the WCGA.

Bibliographie

[1] DeVore R.A., “Nonlinear approximation”, Acta numer., 7 (1998), 51–150 | DOI | MR | Zbl

[2] Donoho D.L., “Sparse components of images and optimal atomic decompositions”, Construct. Approx., 17 (2001), 353–382 | DOI | MR | Zbl

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

[4] Schmidt E., “Zur Theorie der linearen und nichtlinearen Integralgleichungen. I”, Math. Ann., 63 (1906/1907), 433–476 | DOI | MR

[5] Temlyakov V.N., “Greedy algorithms in Banach spaces”, Adv. Comput. Math., 14 (2001), 277–292 | DOI | MR | Zbl

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

[7] Temlyakov V.N., “Greedy algorithms and $m$-term approximation with regard to redundant dictionaries”, J. Approx. Theory, 98 (1999), 117–145 | DOI | MR | Zbl

[8] Temlyakov V.N., “Nonlinear methods of approximation”, Found. comput. math., 3 (2003), 33–107 | DOI | MR | Zbl

[9] Temlyakov V.N., Greedy type algorithms in Banach spaces and applications, Industr. Math. Inst. Res. Repts. N 18, Univ. South Carolina, Columbia, 2002, 36 pp. | Zbl