Additive Lebesgue-Type Inequalities for Greedy Approximation

<p>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.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Campus Access Dissertation

Discipline thesis:degree_discipline

Mathematics

Year

2010

Author dc:creator

• Zheltov, Pavel

Contributors dc:contributor

• Vladimir N. Temlyakov

• Mathematics
• Physical Sciences and Mathematics
• algorithms
• approximation
• compressed
• greedy
• sensing
• sparse

Statement dc:rights

• © 2010, Pavel Zheltov

Repository record dc:identifier

https://scholarcommons.sc.edu/etd/430

OAI identifier oai:identifier

oai:scholarcommons.sc.edu:etd-1431