On Convergence of Weak Greedy Algorithms

E. D. Livshits ; V. N. Temlyakov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Function spaces, harmonic analysis, and differential equations, Tome 232 (2001), pp. 236-247

Résumé

We study the convergence, in a Hilbert space, of a Weak Greedy Algorithm (WGA) which is a modification of a Pure Greedy Algorithm (PGA). At the $m$th step of a WGA, we choose an approximating element from a given dictionary $\mathcal D$ satisfying the relation $|\langle f^\tau _{m-1},\varphi ^\tau _m\rangle | \ge t_m \sup _{g\in \mathcal D}|\langle f^\tau _{m-1},g\rangle |$ with $0\le t_m\le 1$, which is weaker than the corresponding condition in a PGA. It is known that a WGA converges if $\sum _{k=1}^\infty \frac {t_k}{k} = \infty$. The main result of this paper is the following theorem. Let $t_1\ge t_2\ge \dots \ge 0$ and the corresponding WGA converges for all elements of any separable Hilbert space and any dictionary. Then, $\sum _{k=1}^\infty\frac {t_k}{k} = \infty$.