A randomized Kaczmarz algorithm with exponential convergence (Q1027734)

The authors introduce a randomized version of the Kaczmarz method (it is an algorithm for solving linear systems) and prove that it converges with expected exponential rate. The rate does not depend on the number of equations in the system and the solver needs to know only a small random part of the system and not the whole system. They discuss conditions under which their algorithm is optimal in a certain sense, as well as the optimality of the estimate on the expected rate of convergence. They also give numerical experiments and compare the convergence of their algorithm with other algorithms.