The best m-term approximation and greedy algorithms

Two theorems on nonlinear ‐term approximation in , are proved in this paper. The first one (theorem 2.1) says that if a basis is ‐equivalent to the Haar basis then a near best >‐term approximation to any can be realized by the following simple greedy type algorithm. Take the expansion and form a sum of terms with the largest out of this expansion. The second one (theorem 3.3) states that nonlinear ‐term approximations with regard to two dictionaries: the Haar basis and the set of all characteristic functions of intervals are equivalent in a very strong sense. This revised version was published online in June 2006 with corrections to the Cover Date.