Refined Error Bounds for Relaxed Greedy Randomized Kaczmarz Methods

ABSTRACT By rigorously analyzing the asymptotic convergence property of the relaxed greedy randomized Kaczmarz method, we obtain an upper bound on its asymptotic convergence rate that is sharper than the existing one. Also, this upper bound naturally leads to a strengthened convergence guarantee for the greedy randomized Kaczmarz method. Consequently, this result improves and enriches the convergence theory of the greedy randomized Kaczmarz method with or without a relaxation parameter, when these iteration methods are applied to solve large‐scale and consistent system of linear equations.