Greedy algorithms in Banach spaces (Q5950883)

The purpose of this paper is to continue investigations of two greedy type algorithms in uniformly smooth Banach spaces studied recently by author in [Adv. Comput. Math. 12, No. 2-3, 213-227 (2000; Zbl 0964.65009)] for the case of Hilbert space. Let \(X\) be a Banach space. A subset \({\mathcal D}\) in \(X\) is called a dictionary if each \(g\in{\mathcal D}\) has norm one, \(g\in{\mathcal D}\) implies \(-g\in{\mathcal D}\), and and \(\text{Span} \{g: g\in {\mathcal D}\}\) is a dense subset of \(X\). For an element \(f\in X\) let \(F_f\) denote a peak functional for \(f:\|F_f\|=1\) and \(F_f(f)=\|f\|\). Given a sequence \(\{t_k\}_{k=1}^{\infty}\) of positive numbers \(t_k\leq 1\), \(k=1,\dots\), and \(f^c_0:=f\in X\) the Weak Chebyshev Greedy Algorithm (WCGA) is defined inductively with the \(m\)th (\(m\geq 1\)) step consisting of two basic substeps: (1) selection any \(\varphi^c_m\in{\mathcal D}\) satisfying \(F_{f^c_{m-1}}(\varphi_m^c)\geq t_m\sup_{g\in{\mathcal D}}F_{f^c_{m-1}}(g)\), and (2) constructing \(f^c_m:= f-G^c_m\), where \(G^c_m\) is the best \(m\)-term approximant \(f\) from \(\text{Span} \{\pi^c_j\}^m_{j=1}\). The author studies the questions of convergence and the rate of convergence for WCGA in Banach spaces with modulus of smoothness \(\rho (u)\leq\gamma u^q\), \(1<q\leq 2\). He proves that for any \(f\) from the closure of the convex hull of \({\mathcal D}\) the error of \(m\)-term approximation by WCGA is of order \((1+t_1^p+\dots+t_m^p)^{-1/p}\), \(1/p+1/q=1\). Similar results are obtained for Weak Relaxed Greedy Algorithm and its modification.