<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On randomized explicit block Kaczmarz method for solving large linear systems

  • Cun-Qiang Miao,
  • Xue-Yuan Tan

摘要

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.