On performance of greedy algorithms (Q719355)

Let \(H\) be a Hilbert space and \(\mathcal{D}:=\{\varphi_{i}:i\in\mathbb{N} \}\subset H\) be such that \(\overline{\text{span}\mathcal{D}}\mathcal{=}H.\) A dictionary \(\mathcal{D}\) is called \(M\)-coherent if its coherence, defined by \(\sup\{|<\varphi,\psi>| :\varphi,\psi\in\mathcal{D}, \varphi\neq\psi\}\) is exactly \(M.\) The authors consider the Orthogonal Greedy Algorithm (OGA) and Pure Greedy Algorithm (PGA) for \(M\)-coherent dictionaries and study the performance of such algorithms. They prove that the OGA for dictionaries with small coherence \(M\) performs almost as well as the best \(m\)-term approximation for signals with sparsity close to the theoretically possible threshold \(m=\frac{1}{2}(M^{-1}+1).\) This threshold is sharp. The above results are obtained by proving an additive-type Lebesgue inequality for OGA applied to every \(M\)-coherent dictionary \(\mathcal{D}\) and any signal \(f\in H\) (Th. 5). Also, an additive-type Lebesgue inequality for PGA (Th.8) is established. The PGA matches the rate of convergence of the best \(m\)-term approximation beyond the saturation limit of \(m^{-\frac{1}{2}}.\)