On the Rate of Convergence of Greedy Algorithms

被引:0
作者
Temlyakov, Vladimir [1 ,2 ,3 ,4 ]
机构
[1] Russian Acad Sci, Steklov Math Inst, Moscow 117312, Russia
[2] Lomonosov Moscow State Univ, Dept Mech & Math, Moscow 119991, Russia
[3] Moscow Ctr Fundamental & Appl Math, Moscow 119333, Russia
[4] Univ South Carolina, Dept Math, Columbia, SC 29208 USA
基金
俄罗斯科学基金会;
关键词
greedy approximation; rate of convergence; pure greedy algorithm; CONVEX-OPTIMIZATION; SIGNAL RECOVERY; HILBERT; APPROXIMATION; EXPANSIONS;
D O I
10.3390/math11112559
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper, a new criterion for the evaluation of the theoretical efficiency of a greedy algorithm is suggested. Using this criterion, we prove some results on the rate of convergence of greedy algorithms, which provide expansions. We consider both the case of Hilbert spaces and the more general case of Banach spaces. The new component of this paper is that we bound the error of approximation by the product of two norms-the norm of f and the A1-norm of f. Typically, only the A1-norm of f is used. In particular, we establish that some greedy algorithms (Pure Greedy Algorithm (PGA) and its modifications) are as good as the Orthogonal Greedy Algorithm (OGA) in this new sense of the rate of convergence, while it is known that the PGA is much worse than the OGA in the standard sense. Our new results provide better bounds for the accuracy than known results in the case of small parallel to f parallel to.
引用
收藏
页数:15
相关论文
共 23 条
[21]   Greedy expansions in Banach spaces [J].
Temlyakov, V. N. .
ADVANCES IN COMPUTATIONAL MATHEMATICS, 2007, 26 (04) :431-449
[22]  
Tewari Ambuj, 2011, Advances in Neural Information Processing Systems, P882
[23]   Sequential greedy approximation for certain convex optimization problems [J].
Zhang, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (03) :682-691