On Lebesgue-type inequalities for greedy approximation

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 in-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 LIS to get rid of ail extra factor ill 1/2 in the Lebesgue-type inequality for the Orthogonal Greedy AIL,,orithin. (C) 2007 Elsevier Inc. All rights reserved.