On greedy randomized block Kaczmarz method for consistent linear systems

The randomized block Kaczmarz method aims to solve linear system Ax=b by iteratively projecting the current estimate to the solution space of a subset of the constraints. Recent works analyzed the method for the overdetermined least-squares problem, showing expected linear rate of convergence to the ordinary least squares solution with the use of a randomized control scheme to choose the subset at each step. This paper considers the natural follow-up to the randomized control scheme—greedy strategies like the greedy probability criterion and the almost-maximal residual control, and show convergence to a least-squares least-norm solution. Numerical results show that our proposed methods are feasible and have faster convergence rate than the randomized block Kaczmarz method.