Comparison of the convergence rate of pure greedy and orthogonal greedy algorithms (Q1929788)

The author compares the convergence rate of a pure greedy algorithm to an orthogonal greedy orthogonal algorithm. In the real Hilbert space \(H\) with the inner produce \(\langle\cdot, \cdot\rangle\), a set \(\mathcal{D}\subset H\) is called a dictionary if the norm of all elements of \(\mathcal{D}\) is equal to 1 and \(\overline{\mathrm{span}\mathcal{D}}=H\). For a given dictionary \(\mathcal{D}\) and a function \(f \in H\), the following two classes are defined: \[ \mathcal{A}_{1}(\mathcal{D})=\bigcup_{M\geq 0} \overline{\mathcal{A}_{1}^{0}(\mathcal{D},M)} \] where \[ \mathcal{A}_{1}^{0}(\mathcal{D},M)=\{f\in H:f=\sum_{\lambda\in \Lambda}c_{\lambda}g_{\lambda},g_{\lambda}\in\mathcal{D},|\Lambda|<\infty,\sum_{\lambda\in\Lambda}|C_{\lambda}|\leq M \} \] and \(\mathcal{A}_{0}(\mathcal{D})\) is the class of all finite linear combinations of elements of the dictionary \(\mathcal{D}\). The main result in the present paper is that the rate of the orthogonal greedy algorithm can be significantly lower than the rate of convergence of the pure greedy algorithm for separate elements of the class \(\mathcal{A}_{1}(\mathcal{D})\) (and even of the class \(\mathcal{A}_{0}(\mathcal{D})\)), it is contrary to the results on the entire class \(\mathcal{A}_{1}(\mathcal{D})\) that the orthogonal greedy algorithm is optimal and significantly exceeds the pure greedy algorithm.