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 ingredient of the paper is that we bound the error of approximation by the product of both norms -- the norm of $f$ and the $A_1$-norm of $f$. Typically, only the $A_1$-norm of $f$ is used. In particular, we establish that some greedy algorithms (Pure Greedy Algorithm (PGA) and its generalizations) 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 worth than the OGA in the standard sense.
翻译:我们证明了一些关于贪婪算法收敛率的结果,并给出了展开式。我们考虑了希尔伯特空间和更一般的巴拿赫空间的情况。本文的新要素在于,我们将逼近误差的界限定义为两个范数的乘积-- $f$ 的范数和 $A_1$-范数。通常只使用 $f$ 的 $A_1$-范数。特别地,我们证明了一些贪婪算法(纯粹贪婪算法(PGA)及其推广)在这种新的收敛率意义下与正交贪婪算法(OGA)一样好,而众所周知,在标准意义下,PGA 远不如 OGA。