Convergence rates for Kaczmarz-type algorithms

In this paper, we make a theoretical analysis of the convergence rates of Kaczmarz and extended Kaczmarz projection algorithms for some of the most practically used control sequences. We first prove an at least linear convergence rate for the Kaczmarz-Tanabe and its extended version methods (the one in which a complete set of projections using row/column indices is performed in each iteration). Then, we apply the main ideas of this analysis in establishing an at least sublinear, respectively, linear convergence rate for the Kaczmarz algorithm with almost cyclic and the remotest set control strategies, and their extended versions, respectively. These results complete the existing ones related to the random selection procedures.