Greedy approximations with regard to bases

Abstract

This paper is a survey of recent results on greedy approximations with regard to bases. The theory of greedy approximations is a part of nonlinear approximations. The standard problem in this regard is the problem of m-term approximation where one fixes a basis and seeks to approximate a target function by a linear combination of m terms of the basis. When the basis is a wavelet basis or a basis of other waveforms, then this type of approximation is the starting point for compression algorithms. We are interested in the quantitative aspects of this type of approximation. Introducing the concept of best m-term approximation we obtain a lower bound for the accuracy of any method providing m-term approximation. It is known that a problem of simultaneous optimization over many parameters (like in best m-term approximation) is a very difficult problem. We would like to have an algorithm for constructing m-term approximants that adds at each step only one new element from the basis and keeps elements of the basis obtained at the previous steps. The primary object of our discussion is the Thresholding Greedy Algorithm (TGA) with regard to a given basis. The TGA, applied to a function f, picks at the m-th step an element with the m-th biggest coefficient (in absolute value) of the expansion of f in the series with respect to the basis. We show that this algorithm is very good for a wavelet basis and is not that good for the trigonometric system. We discuss in detail the behavior of the TGA with regard to the trigonometric system. We also discuss one example of an algorithm from a family of very general greedy algorithms that works in the case of a redundant system instead of a basis. It turns out that this general greedy algorithm is very good for the trigonometric system.