"Push-the-Error" Algorithm for Nonlinear n-Term Approximation

This paper is concerned with further developing and refining the analysis of a recent algorithmic paradigm for nonlinear approximation, termed the "Push-the-Error" scheme. It is especially designed to deal with L_∞-approximation in a multilevel framework. The original version is extended considerably to cover all commonly used multiresolution frameworks. The main conceptually new result is the proof of the quasi-semi-additivity of the functional N(ε) counting the number of terms needed to achieve accuracy ε. This allows one to show that the improved scheme captures all rates of best n-term approximation.