On the Rate of Convergence of Greedy Algorithms

Abstract

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 ∥f∥.

Keywords

• greedy approximation
• rate of convergence
• pure greedy algorithm