A counter-example to the general convergence of partially greedy algorithms (Q5944137)

Greedy algorithms in a separable Hilbert space \({\mathcal H}\) for approximating a given vector \(R_1\) with a complete dictionary \({\mathcal D}\) are iterative processes of constructing an expansion of \(R_1\): NEWLINE\[NEWLINE R_1=\langle R_1,g_1\rangle g_1+\langle R_2,g_2\rangle g_2+\cdots+\langle R_m,g_m\rangle g_m+R_{m+1}.NEWLINE\]NEWLINE Here \(R_m\in{\mathcal H}\), and \(g_m\in{\mathcal D}\) are chosen such that NEWLINE\[NEWLINE R_m=\langle R_m,g_m\rangle g_m +R_{m+1}\quad \text{with} \quad |\langle R_m,g_m\rangle|=\sup_{g\in{\mathcal D}}|\langle R_m,g\rangle|. NEWLINE\]NEWLINE If the dictionary \({\mathcal D}\) is large, computation of \(g_m\) can be too costly. Partially greedy algorithms search for \(g^*_m\) in a compelte subdictionary \({\mathcal D}^*\) of \({\mathcal D}\) and further improve it with a ``locally optimal'' \(g_m\in {\mathcal D}\) such that NEWLINE\[NEWLINE |\langle R_m,g_m\rangle|\geq |\langle R_m,g_m^*\rangle|=\sup_{g\in{\mathcal D}^*}|\langle R_m,g\rangle|. NEWLINE\]NEWLINE A natural conjecture is that if \({\mathcal D}^*\subset {\mathcal D}\) are two complete disctionaries, then the residual \(\|R_m\|\) should converge to zero. This paper disproves this conjecture with a counter example and discusses its implications.