An accelerated randomized Kaczmarz method via low-rank approximation

The Kaczmarz method for finding the solution to an overdetermined consistent system of linear equation Ax=b(A∈R^m×n) is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Recently, Strohmer and Vershynin proposed randomized Kaczmarz, and proved its exponential convergence. In this paper, motivated by idea of precondition, we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax=b, and the orthogonal matrix is obtained by low-rank approximation. Our approach fits the problem when m is huge and m?n. Theoretically, we improve the convergence rate of the randomized Kaczmarz method. The numerical results show that our approach is faster than the standard randomized Kaczmarz.