https://hal.inria.fr/inria-00576650Gribonval, RémiRémiGribonvalDepartment of Mathematics [Columbia] - University of South Carolina [Columbia]Partially Greedy AlgorithmsHAL CCSD2001greedy[INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing[SPI.SIGNAL] Engineering Sciences [physics]/Signal and Image processingGribonval, RémiKopotun, K. and Lyche, T. and Neamtu, M.2011-03-15 09:46:562021-10-20 00:17:252011-03-15 09:46:56enConference papers1In 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.