On Lebesgue-type inequalities for greedy approximation

被引：35

作者：

Donoho, D. L.

Elad, M.

Temlyakov, V. N. ^{[1
]}

机构：

[1] Univ S Carolina, Dept Math, Columbia, SC 29208 USA

[2] Stanford Univ, Dept Stat, Stanford, CA 94305 USA

[3] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

JOURNAL OF APPROXIMATION THEORY | 2007年 / 147卷 / 02期

关键词：

lebesgue inequality; greedy algorithin; dictionary; coherence;

D O I：

10.1016/j.jat.2007.01.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：185 / 195

页数：11

共 8 条

[1] Some remarks on greedy algorithms [J].