On Convergence of Weak Greedy Algorithms

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$.