On the generalized approximate weak Chebyshev greedy algorithm

Volume 237 / 2017

Anton Dereventsov Studia Mathematica 237 (2017), 153-175 MSC: Primary 41A65; Secondary 41A99. DOI: 10.4064/sm8579-10-2016 Published online: 24 February 2017


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


  • Anton DereventsovDepartment of Mathematics
    University of South Carolina
    1523 Greene St.
    Columbia, SC 29208, U.S.A.

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image