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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Zheltov, Pavel"],"institution":null,"degree_name":"Ph.D.","degree_level":"Campus Access Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Vladimir N. Temlyakov"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-01-01T08:00:00Z","date_published":"2010-01-01T08:00:00Z","updated_at":"2026-07-24T04:36:50Z","subjects":["Mathematics","Physical Sciences and Mathematics","algorithms","approximation","compressed","greedy","sensing","sparse"],"languages":[],"rights":["© 2010, Pavel Zheltov"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarcommons.sc.edu/etd/430","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vladimir N. Temlyakov"]},{"key":"dc:creator","label":"Author","values":["Zheltov, Pavel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Campus Access Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Physical Sciences and Mathematics","algorithms","approximation","compressed","greedy","sensing","sparse"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["© 2010, Pavel Zheltov"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarcommons.sc.edu/etd/430"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Additive Lebesgue-Type Inequalities for Greedy Approximation"]}]}],"canonical_facts":{"dc:contributor":["Vladimir N. Temlyakov"],"dc:creator":["Zheltov, Pavel"],"dc:description.abstract":["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.
"],"dc:identifier":["https://scholarcommons.sc.edu/etd/430"],"dc:rights":["© 2010, Pavel Zheltov"],"dc:subject":["Mathematics","Physical Sciences and Mathematics","algorithms","approximation","compressed","greedy","sensing","sparse"],"dc:title":["Additive Lebesgue-Type Inequalities for Greedy Approximation"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Campus Access Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T04:36:50Z"}