Greedy Algorithms In Approximation Theory and Compressed Sensing

Sparse representations of a function is a very powerful tool to analyze and approximate the function. It has been utilized in many applications such as signal/image processing and numerical computation. One of the fundamental questions in this consideration is how to construct good methods (algorithms) of approximation, and how to measure the performance of these methods. One of the most successful approaches in this area is the greedy method, which belongs to the theory of nonlinear approximation. This dissertation answers the question for some greedy type methods. We approach the problem from two aspects, Nonlinear Approximation Theory and Compressed Sensing. In the setting of Nonlinear Approximation Theory, we mainly study the direction (Jackson) and inverse (Bernstein) theorems with bases that are tensor products of univariate greedy bases, as well as Lebesgue type inequalities for quasi-greedy bases. In the area of Compressed Sensing, we study a modified Orthogonal Greedy Algorithm, Orthogonal Greedy Algorithm with Thresholding. We investigate its performance with regard to a redundant system of generators (dictionary), in both theoretical and numerical aspects