On the generalized approximate weak Chebyshev greedy algorithm

Anton Dereventsov¹

¹ Department of Mathematics University of South Carolina 1523 Greene St. Columbia, SC 29208, U.S.A.

Studia Mathematica, Tome 237 (2017) no. 2, pp. 153-175

Résumé

\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.

Détail

DOI : 10.4064/sm8579-10-2016

Keywords: looseness weak chebyshev greedy algorithm wcga defined banach space dictionary mathcal provides nonlinear n term approximation given element respect mathcal paper study generalized approximate weak chebyshev greedy algorithm gawcga modification wcga which allowed calculate n term approximation relative absolute errors computing norming functional element best approximation approximant natural numerical applications simplifies realization algorithm obtain conditions sufficient convergence gawcga element uniformly smooth banach space necessary class uniformly smooth banach spaces modulus smoothness nontrivial power type spaces infty particular errors ell conditions convergence gawcga the wcga construct example smooth banach space which algorithm diverges dictionary element showing smoothness space sufficient convergence wcga