A Note On Convergence Rate of Randomized Kaczmarz Method

In this paper, we propose an alternative version of the randomized Kaczmarz method, which chooses each row of the coefficient matrix A with probability proportional to the square of the Euclidean norm of the residual of each corresponding equation. We prove that it converges with expected linear rate and the convergence rate of this method is better than the Strohmer and Vershynin’s RK method. Numerical experiments also show this method is more efficient than the RK method.