Approximate weak greedy algorithms (Q5950886)

Let \(H\) be a real Hilbert space with inner product \(\langle \cdot, \cdot\rangle\). A subset \({\mathcal D}\) in \(H\) is called the dictionary if each \(g\in{\mathcal D}\) has norm one and \(Spann \{g: g\in {\mathcal D}\}\) is a dense subset of \(H\). Given \(\{t_m\}_{m=1}^{\infty}\subset [0, 1]\) and \(\{\epsilon_m\}_{m=1}^{\infty}\subset[-1, 1]\) the Approximate Weak Greedy Algorithm (AWGA) provides an \(m\)-term approximation of \(f_0\in H\) by constructing a sequence \(f_m\in H\), \(m\geq 1\), such that at each step \(f_m=f_{m-1}-(1+\epsilon_m)\langle f_{m-1}, g_m\rangle g_m\), \(g_m\in {\mathcal D}\), with \(|\langle f_{m-1}, g_m\rangle|\geq t_m\sup_{g\in{\mathcal D}}|\langle f_{m-1}, g\rangle|\). The \(m\)-term approximant of \(f_0\) is then defined as \(G_m=f_0-f_m=\sum_{j=1}^m (1+\epsilon_j)\langle f_{j-1}, g_j\rangle g_j\). The authors give sufficient conditions on \(\{\epsilon_m\}\) and \(\{t_m\}\) for AWGA to converge with any dictionary \({\mathcal D}\), i.e. whether \(G_m\to f_0\) for every \(f_0\in H\) (or equivalently, \(f_m\to 0\)). They provide two counter-examples to show that the condition cannot be relaxed in general. For a class of dictionaries with more structure a more relaxed necessary and sufficient condition for convergence of the algorithm are also given.