Partially Greedy Algorithms
Résumé
In a separable Hilbert space $\cal H$, greedy algorithms iteratively define $m$-term approximants to a given vector $f$ from a complete redundant dictionary $\cal D$. With very large dictionaries, the pure greedy algorithm cannot be implemented and must be replaced with a weak greedy algorithm which is defined through a weakness sequence $t_m \in [0,1], m \ge 0$. The strong convergence of weak greedy algorithms is known as soon as $\sum_m t_m/m = \infty$ and $\cal D$ is complete (\ewordi.e. $\overlinespan(\cal D) = \cal H$). However in some practical implementations it is hard to control $\t_m\$. It is easier to find a smaller complete dictionary $\cal D^\star \subset \cal D$ such that $$ |\langle f_m-1,g_m\rangle| \ge \sup_g \in \cal D^\star |\langle f_m-1,g\rangle|. $$ Such \ewordpartially greedy algorithms are ``better'' at each step than the pure greedy algorithms in the complete dictionary $\cal D^\star$, which is known to converge strongly. It is natural to conjecture their strong convergence, which is observed in some numerical experiments. We prove their convergence in a slightly stronger sense than the weak sense. However, by giving a counter-example, we disprove the natural conjecture about their strong convergence.