Date of Award


Document Type

Campus Access Dissertation



First Advisor

Vladimir N. Temlyakov


In the approximation theory we are commonly interested in finding a best possible approximant to a function (also thought of as a signal or an image in signal processing) from a collection of a given number of elements. In the recent years, there arose an interest in considering rich collections of elements, such as frames, concatenations of several bases, or random dictionaries. What distinguishes them from classic bases is redundancy, in a sense that there may be multiple ways to represent the same signal. In this dissertation we discuss several approaches to find a good approximant, and focus on a class of such techniques called "greedy algorithms". A problem that we will be mostly concerned with is of measuring performance of these algorithms (specifically, Pure Greedy Algorithm and Orthogonal Greedy Algorithm). We will compare several ways to describe the quality of the dictionary; some of them more fit for the our purposes than others. We will show that under conditions of mutual coherence or restricted isometry property, our greedy algorithms output a result that is almost as good as the best possible.