Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4608198 | Journal of Approximation Theory | 2007 | 11 Pages |
Abstract
We study the efficiency of greedy algorithms with regard to redundant dictionaries in Hilbert spaces. We obtain upper estimates for the errors of the Pure Greedy Algorithm and the Orthogonal Greedy Algorithm in terms of the best m-term approximations. We call such estimates the Lebesgue-type inequalities. We prove the Lebesgue-type inequalities for dictionaries with special structure. We assume that the dictionary has a property of mutual incoherence (the coherence parameter of the dictionary is small). We develop a new technique that, in particular, allowed us to get rid of an extra factor m1/2 in the Lebesgue-type inequality for the Orthogonal Greedy Algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis