Projection greedy algorithm (Q2049278)

Let \(H\) be a Hilbert space, \(S(H)\) its unit sphere and \(D\subset H\) a dictionary in \(H\), that is, a set of unit vectors whose linear span is dense in \(H\). One denotes by \(P_Y\) the orthogonal projection on a subspace \(Y\) of \(H\) and by \(A^\perp\) the orthogonal complement of a subset \(A\) of \(H\). The notation \([y_1,y_2,\dots,y_n]\) is used for the linear span of a subset \(\{y_1,y_2,\dots,y_n\}\) of \(H\). For a given sequence \(t_n\in(0,1],\, n=0,1,\dots\) and \(x_0\in H\) several greedy algorithms are used to obtain good \(n\)-term approximations by elements of \(D\) (see [\textit{V. Temlyakov}, Greedy approximation. Cambridge: Cambridge University Press (2011; Zbl 1279.41001)]). I mention the weak greedy algorithm (WGA) which works as follows: given \(x_0\in H\) one considers the sequence \(x_{n+1}=x_n-\langle x_n,g_n\rangle P_{[g_n]^\perp}x_n,\, n=0,1,\dots\), where \(g_n\in D\) satisfies \(|\langle x_n,g_n\rangle|\ge t_n\sup\{|\langle x_n,g\rangle|: g\in D\}\). The authors propose a modification of WGA, called the projection weak greedy algorithm (PrWGA) with respect to a dictionary \(D \) which, for each element \(x_0\in H\), produces the sequence \(x_{n+1}=x_n-\langle x_n,g_n\rangle P_{[g_n]^\perp}x_n,\, n=0,1,\dots\), where \(g_n\in D_n\) is such that \(|\langle x_n,g_n\rangle|\ge t_n\sup\{|\langle x_n,g\rangle|: g\in D_n\}\). Here \(D_n\) is the dictionary consisting of normalized projections of elements of the dictionary \(D\) on the subspace \([g_0,g_1,\dots, g_n]^\perp\). The difference with respect to WGA is that PrWGA changes the dictionary at each step. From the abstract: ``We prove that these algorithms converge and estimate the rate of convergence for initial elements from the convex hull of the dictionary. Several specific examples of dictionaries are used to compare the introduced algorithms with orthogonal greedy algorithms.''