Vector greedy algorithms (Q652444)

A dictionary is a subset \(\mathcal D\) of a Hilbert space \((H,\langle\cdot,\cdot\rangle)\) such that \(\|g\|=1\) for all \(g\in \mathcal D\) and cl-span\((\mathcal D)=H.\) The objective of greedy algorithms is to construct a sequence \(\{g_k\}\) in \(\mathcal D\) and a sequence of approximants \(G_k\in\mathcal D_k=\) span\(\{g_1,\dots,g_k\}\) such that \(\lim_{k\to\infty}\|f-G_k\|=0.\) With the dictionary \(\mathcal D\) one associates a norm defined by \(\|f\|_{\mathcal D}=\sup_{g\in \mathcal D}|\langle f,g\rangle|.\) The construction proceeds inductively by adding to existing \(g_1,\dots,g_n\) an element \(g_{n+1}\in\mathcal D.\) The specific optimization criterium used for constructing \(G_k\) will define specific greedy algorithms. The first two algorithms considered by the authors, the pure greedy algorithm (PGA) and the orthogonal greedy algorithm (OGA), are based on the hypothesis that there exists a selection \(S:H\to\mathcal D\) such that \(\langle f,S(f)\rangle ==\|f\|_{\mathcal D}\). In this case one defines \(G(f)=\langle f,S(f)\rangle S(f)\) and \(R(f)=f-G(f)\). The PGA is based on the recurrence formulae \(G_m(f)=G_{m-1}(f)+G(R_{m-1}(f)),\, R_m(f):=f-G_m(f)= G(R_{m-1}(f))\). The OGA is defined in a similar way taking \[ H_m(f)=\text{ span}\{G(R^o_0(f)),\dots,G(R^o_{m-1}(f))\},\, G_m^o(f)=P_{H_m}(f) \] (the metric (= orthogonal) projection on \(H_m=H_m(f)\)), and \(R^o(f)=f-G_m^o(f)\). The authors consider also four greedy algorithms of weak type, where instead of the selection \(S\) one uses elements \(\varphi\in \mathcal D\) such that \(|\langle f,\varphi\rangle|\geq t\|f\|_{\mathcal D},\) for some \(t\in (0,1),\) where \(t\) can be different at each step. They give some necessary and sufficient conditions for the convergence of these algorithms as well as evaluations of the rates of convergence. The obtained results extend some previous results of the second author, see [Adv. Comput. Math. 12, 213--227 (2000; Zbl 0964.65009)], the survey [Acta Numerica 17, 235--409 (2008; Zbl 1178.65050) and the recent book [\textit{V. Temlyakov}, Greedy approximation. Cambridge Monographs on Applied and Computational Mathematics 20. Cambridge: Cambridge University Press. (2011; Zbl 1279.41001)].