Accelerated Kaczmarz Algorithms using History Information

Abstract: The Kaczmarz algorithm is a well known iterative method for solving overdetermined linear systems. Its randomized version yields provably exponential convergence in expectation. In this paper, we propose two new methods to speed up the randomized Kaczmarz algorithm by utilizing the past estimates in the iterations. The first one utilize the past estimates to get a preconditioner. The second one combines the stochastic average gradient (SAG) method with the randomized Kaczmarz algorithm. It takes advantage of past gradients to improve the convergence speed. Numerical experiments indicate that the new algorithms can dramatically outperform the standard randomized Kaczmarz algorithm.

This page was built for publication: Accelerated Kaczmarz Algorithms using History Information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6511709)