Date of Award


Document Type

Campus Access Dissertation



First Advisor

Vladimir N. Temlyakov


The sparse approximation problems ask for complete recovery of functions in a given space that are supported by few of the elements of a system of generators for the space or for approximate recovery that involves a limited number of generators.

Traditionally, these problems have been studied by approximation theorists in the context of methods of finding the best approximant from a subspace, or by statisticians concerned in finding good regressions. Recently, a new field of applied mathematics, Compressive Sensing, emerged. It gathered mathematicians, statisticians, electrical engineers, computer scientists, chemists and physicists fascinated by the potential of new algorithms in solving the problem of sparse approximation in diverse settings, which is the primary objective of this field.

One of the most successful approaches in this area, the greedy method, belongs to the theory of nonlinear approximation. The greedy algorithms are designed to make local optimal choices with the hope of obtaining a global optimal solution. This is made in regard with redundant systems which offer convenience of representation as well as better rates of approximation. The redundancy raises, in turn, very difficult theoretical problems.

This dissertation gives answers to some of these problems in the very general setting of Banach spaces. Its theoretical results complete the previous findings in this setting and show, for the first time, the same general recovery properties as the ones known in the particular case of Hilbert spaces.

Moreover, this work provides a novel idea of improvement of the geometry of the redundant systems by switching to a different setting than the standard Hilbert space. This improvement would translate in better recovery properties as the dissertation proved the same efficiency of the greedy approach in the new setting.

This investigation finds its place in the fresh area of Compressive Sensing by proposing a competitive alternative in solving sparse approximation problems, and it gives new insights in the Theory of Greedy Approximation.


© 2009, Daniel Savu