Vladimir Temlyakov

Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.

In this survey we discuss properties of specific methods of approximation that belong to a family of greedy approximation methods (greedy algorithms). It is now well understood that we need to study nonlinear sparse representations in order to significantly increase our ability to process (compress, denoise, etc. ) large data sets. Sparse representations of a function are not only a powerful analytic tool but they are utilized in many application areas such as image/signal processing and numerical computation. The key to finding sparse representations is the concept of m -term approximation of the target function by the elements of a given system of functions (dictionary). The fundamental question is how to construct good methods (algorithms) of approximation. Recent results have established that greedy-type algorithms are suitable methods of nonlinear approximation in both m -term approximation with regard to bases, and m -term approximation with regard to redundant systems. It turns out that there is one fundamental principle that allows us to build good algorithms, both for arbitrary redundant systems and for very simple well-structured bases, such as the Haar basis. This principle is the use of a greedy step in searching for a new element to be added to a given m -term approximant.