On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries (Q420768)

A subset \(\mathcal D\) of a Hilbert space \(H\) is called a dictionary if \(\|\phi\|=1,\, \phi\in\mathcal D,\) and the closed linear space generated by \(\mathcal D\) is \(H.\) The coherence of the dictionary \(\mathcal D\) is defined by \(\mu:=\sup\{|\langle \phi,\psi\rangle| : \phi,\psi\in \mathcal D, \, \phi\neq \psi\}.\) The paper is concerned with dictionaries of small coherence. The Orthogonal Greedy Algorithm (OGA) is defined in the following way: for \(f\in H\) one puts \(f_0:=f\) and \(G_0^{OGA}(f,\mathcal D):=0\). Then one finds inductively \(g_{m+1}\in \mathcal D,\, m\geq 0,\) such that \(|\langle f_m,g_{m+1}\rangle|=\sup\{|\langle f_m,g\rangle| : g\in\mathcal D\},\) and one defines \(G_{m+1}^{OGA}(f,\mathcal D):=\text{Proj}_{Z_{m+1}}(f)\) and \(f_{m+1}:=f-G_{m+1}^{OGA}(f,\mathcal D),\) where \(Z_{m+1}=\text{span}\{g_1,\dots,g_{m+1}\}\). The main result of the paper (Theorem 2) is the following Lebesgue-type inequality: \(\| f-G_{2m}^{OGA}(f,\mathcal D)\leq 2.7 \sigma_m(f,\mathcal D),\) for all \(1\leq m\leq 1/(20\mu),\) where \(\sigma_m(f,\mathcal D):= \inf\{\| f-\sum_{i=1}^mc_i\phi_i\| : c_i\in\mathbb R,\, \phi_i\in\mathcal D,\, 1\leq i\leq m\}\). These complete some results obtained by \textit{J. L. Nelson} and \textit{V. N. Temlyakov} [J. Approx. Theory 163, No. 9, 1238--1245 (2011; Zbl 1242.41037)] and \textit{D. L. Donoho, M. Elad} and \textit{V. N. Temlyakov} [J. Approx. Theory 147, No. 2, 185--195 (2007; Zbl 1120.41007)]. A book by \textit{V. Temlyakov} [Greedy approximation. Cambridge: Cambridge University Press (2011; Zbl 1279.41001)] is also announced.