Convergence Analysis of Greedy Algorithms with Adaptive Relaxation in Hilbert Spaces

The Power-Relaxed Greedy Algorithm (PRGA) was introduced as a generalization of the so called Relaxed Greedy Algorithm, introduced by DeVore and Temlyakov, by replacing the relaxation parameter $1\mathrm{/}m$ with $1\mathrm{/}{m}^{\alpha }$, with the aim of improving convergence rates. While the case $\alpha \le 1$ is well understood, the behavior of the algorithm for $\alpha >1$ remained an open problem. In this work, we answer this question and, moreover, we introduce a relaxed greedy algorithm with an optimal step size chosen by exact line search at each iteration.