On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries (Q420768): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 04:46, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries |
scientific article |
Statements
On the optimality of the orthogonal greedy algorithm for \(\mu\)-coherent dictionaries (English)
0 references
23 May 2012
0 references
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.
0 references
orthogonal greedy algorithms
0 references
orthogonal matching pursuit
0 references
Lebesgue-type inequalities
0 references
best \(m\)-term approximation
0 references
orthogonal projection
0 references