On randomized explicit block Kaczmarz method for solving large linear systems
摘要
The randomized block Kaczmarz method (Linear Algebra Appl., 441: 199-221, 2014) proposed by Needell and Tropp is efficient for solving large consistent linear systems. However, each iteration of the randomized block Kaczmarz method carries a high cost, as it calls for the computation of a pseudoinverse, or equivalently, the solution of a least-squares problem. In this paper, we propose a randomized explicit block Kaczmarz method that avoids the direct computation of pseudoinverses by exploiting the structure of the block updates. This explicit formulation allows for a more flexible selection of the rows in the working block at each iteration, without relying on a predefined partition of the row indices. Based on a randomized block selection strategy, we further establish the convergence properties of the proposed method. It indicates that the randomized explicit block Kaczmarz method exhibits faster convergence compared to the multi-step standard randomized Kaczmarz method and the randomized block Kaczmarz method. Finally, numerical experiments are carried out to show great superiority and robustness over some state-of-the-art randomized block Kaczmarz methods.