Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata
Contributor : Rémi Gribonval Connect in order to contact the contributor
Submitted on : Tuesday, March 15, 2011 - 9:46:56 AM
Last modification on : Wednesday, October 20, 2021 - 12:17:25 AM


  • HAL Id : inria-00576650, version 1


Rémi Gribonval. Partially Greedy Algorithms. Trends in Approximation Theory, May 2000, Nashville, TN, United States. pp.143-148. ⟨inria-00576650⟩



Record views