On greedy algorithms for dictionaries with bounded cumulative coherence (Q368218)

Let \(H\) be a real separable Hilbert space with inner product \(\langle\cdot\,,\,\cdot\rangle\). A set \({\mathcal D}\) is called a dictionary if \(\overline{\text{span}}\, {\mathcal D}=H\) and each \(g\in {\mathcal D}\) satisfies \(\|g\|=1\). The problem under consideration is that of approximating \(f\in H\) by \[ \sum_{k=1}^m c_k(f) g_k(f), \] where \(c_k(f)\in \Re\) and \(g_k(f)\in {\mathcal D}\). One approach to this problem is that of greedy algorithms. There are various types of greedy algorithms. The best known is the pure greedy algorithm. It is given by setting \(f_0=f\), then choosing \(g_{m+1}\in {\mathcal D}\) to satisfy \[ \langle f_m, g_{m+1}\rangle = \sup_{g\in {\mathcal D}} |\langle f_m, g\rangle|, \] and defining \(f_{m+1} = f_m - \langle f_m, g_{m+1}\rangle g_{m+1}\). In this paper, the author considers rates of convergence of the \(f_m\) to \(f\) as \(m\to\infty\), in this and similar algorithms, under various constraints. An important tool in these estimates is the cumulative coherence of \({\mathcal D}\) which is defined by \[ \mu_1({\mathcal D}) = \sup_{g\in {\mathcal D}} \sum_{h\in {\mathcal D}, h\neq g}|\langle h,g\rangle|. \]