On the generalized approximate weak Chebyshev greedy algorithm
Volume 237 / 2017
Abstract
\looseness 22The Weak Chebyshev Greedy Algorithm (WCGA) is defined for any Banach space $X$ and a dictionary $\mathcal {D}$, and provides nonlinear $n$-term approximation for a given element $f \in X$ with respect to $\mathcal {D}$. In this paper we study the generalized Approximate Weak Chebyshev Greedy Algorithm (gAWCGA), a modification of the WCGA in which we are allowed to calculate $n$-term approximation with relative and absolute errors in computing a norming functional, an element of best approximation, and an approximant. This is natural for numerical applications and simplifies realization of the algorithm. We obtain conditions that are sufficient for the convergence of the gAWCGA for any element of a uniformly smooth Banach space, and show that they are necessary in the class of uniformly smooth Banach spaces with modulus of smoothness of nontrivial power type (e.g. $L_p$ spaces for $1 \lt p \lt \infty $). In particular, we show that if all the errors are in $\ell _1$ then the conditions for the convergence of the gAWCGA are the same as for the WCGA. We also construct an example of a smooth Banach space in which the algorithm diverges for a dictionary and an element, thus showing that the smoothness of the space is not sufficient for the convergence of the WCGA.
