An accelerated randomized Kaczmarz method via low-rank approximation

Abstract

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.

Keywords:

• Kaczmarz method
• randomized Kaczmarz method
• low-rank approximations of matrices

2010 AMS Subject Classifications::

• 52C99
• 68Q01

Acknowledgements

The work is supported in part by the National Science Foundation of China under Grants No. 61271014, No.61072118 and No.61170159, and by Science Project of National University if Defense Technology JC120201, also by National Natural Science Foundation of Hunan Province(China) 13JJ2001.