On randomized explicit block Kaczmarz method for solving large linear systems

Speaker：Cunqiang Miao (Central South University)

Time：2026-4-25 10:30

Location：Conference Room C503 at Administration Building at Haiyun Campus

Abstract:

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 talk, 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.