On the rate of convergence of a pure greedy algorithm. (Q556558)

Let \(H\) be a real Hilbert space, and let \(D\) be a normalized subset of \(H\) whose linear hull is everywhere dense. It is assumed that for each \(f\in H\) there exists a \(g(f)\in {\mathcal D}\) maximizing \(|\langle f,g\rangle|\). Given an initial vector \(f_0\in H\), the pure greedy algorithm with respect to \(\mathcal D\) generates two sequences \(\{g_n\}^\infty_{n=1}\) and \(\{f_n\}^\infty_{n=1}\) by means of the formulas \(g_n:= g(f_{n-1})\) and \(f_n:=f_{n-1}-\langle f_{n-1},g_n\rangle g_n\). \textit{L. K. Jones} [Ann. Statist. 15, 880--882 (1987)] proved that the sequence \(\{G_m(f_0,{\mathcal D})\}^\infty_{m=1}\) converges to \(f_0\), where \[ G_m(f_0,{\mathcal D}):=\sum^m_{n=1}\langle f_{n-1},g_n\rangle g_n. \] In order to estimate the rate of convergence the author additionally assumes that there are constants \(\alpha>0\), \(\beta\geq 0\), \(M_\alpha>1\), \(M_\beta>1\) such that for each positive integer \(m\) there exist \(\widetilde g_1,\dots,\widetilde g_m\in{\mathcal D}\) and \(c_1,\dots,c_m\in\mathbb R\) satisfying \[ \| f_0-\sum^m_{n=1} c_n\widetilde g_n\|\leq \frac {M_\alpha}{m^\alpha}\text{ and }\sum^m_{n=1}|c_n|\leq M_\beta m^\beta. \] Under this assumption the following estimates are proved: (1) if \(\alpha<1/6\) and \(\alpha+\beta<1/2\), then there exists for each \(\varepsilon>0\) a \(C>0\) such that \[ \| f_0-G_m(f_0,{\mathcal D})\| \leq C_m^{-\alpha/(1+2\alpha)+\varepsilon} \] for all positive integers \(m\); (2) if \(\alpha<1/6\), \(0<\beta<1/2\) and \(\alpha/(1+2\alpha)+\beta\geq 1/2\), then there exists for each \(\varepsilon >0\) a \(C>0\) such that \[ \| f_0-G_m(f_0,{\mathcal D}\|\leq C_m-(1/2-\beta)+\varepsilon \] for all positive integers \(m\).