Partially Greedy Algorithms

Abstract : 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.
keyword : greedy
Type de document :
Communication dans un congrès
Kopotun, K. and Lyche, T. and Neamtu, M. Trends in Approximation Theory, May 2000, Nashville, TN, United States. Vanderbilt University Press, pp.143-148, 2001
Liste complète des métadonnées

https://hal.inria.fr/inria-00576650
Contributeur : Rémi Gribonval <>
Soumis le : mardi 15 mars 2011 - 09:46:56
Dernière modification le : mercredi 21 mars 2018 - 09:28:10

Identifiants

  • HAL Id : inria-00576650, version 1

Citation

Rémi Gribonval. Partially Greedy Algorithms. Kopotun, K. and Lyche, T. and Neamtu, M. Trends in Approximation Theory, May 2000, Nashville, TN, United States. Vanderbilt University Press, pp.143-148, 2001. 〈inria-00576650〉

Partager

Métriques

Consultations de la notice

29