  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.
