A quantile-based block Kaczmarz algorithm for solving large consistent linear systems

We develop an efficient block Kaczmarz algorithm to improve the convergence rate of the randomized Kaczmarz method for solving consistent linear equations. It identifies large elements in the residual vector using quantile and then projects the iterate onto the corresponding hyperplanes through the Gaussian Kaczmarz approach. We have validated that the iteration sequence generated by our algorithm converges to the unique least-norm solution. Furthermore, we have demonstrated that the upper bound for estimating the convergence rate of our algorithm can be smaller than those of two related Kaczmarz-type algorithms when appropriate quantile is chosen. Numerical examples show that the proposed algorithm outperforms its counterparts regarding the number of iteration steps and computational time.