Randomized block Kaczmarz methods with k-means clustering for solving large linear systems

Following the philosophy of the block Kaczmarz methods, we propose a randomized block Kaczmarz method with the blocks determined by the k-means clustering (RBK(k)). It can be considered as an efficient variant of the relaxed greedy randomized Kaczmarz algorithm by using a practical probability criterion for selecting the working block submatrix per iteration. The new algorithm is proved to be convergent when the linear system is consistent. A practical variant of the new method is also given. Some numerical examples are given to verify the effectiveness of the proposed methods. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

In this study, a randomized block Kaczmarz method based on k-means clustering is proposed, which selects the working block submatrix using a practical probability criterion. It is proven to converge when the linear system is consistent, and a practical variant is provided. Numerical examples are used to verify the effectiveness of the methods proposed.