Scholarlink

<p>In this paper, we analyze the greedy randomized Kaczmarz (GRK) method proposed in Bai and Wu (SIAM J. Sci. Comput., <b>40</b>(1), A592–A606, 2018) for solving linear systems. We develop tighter greedy probability criteria to effectively select the working row from the coefficient matrix. Notably, we prove that the linear convergence of the GRK method is deterministic and demonstrate that using a tighter threshold parameter can lead to a better convergence factor. Our result strengthens existing convergence analyses, which are solely based on the expected error by realizing that the iterates of the GRK method are random variables. Consequently, we obtain an improved iteration complexity for the GRK method. Moreover, the Polyak’s heavy ball momentum technique is incorporated to improve the performance of the GRK method. We propose a refined convergence analysis, compared with the technique used in Loizou and Richtárik (Comput. Optim. Appl., <b>77</b>(3), 653–710, 2020), of momentum variants of randomized iterative methods, which shows that the proposed GRK method with momentum (mGRK) also enjoys a deterministic linear convergence. Numerical experiments show that the mGRK method is more efficient than the GRK method.</p>

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

On the convergence analysis of the greedy randomized Kaczmarz method

  • 期刊论文

  • 发表日期：

    2026年3月9日

查看全文
  • Yansheng Su,
  • Deren Han,
  • Yun Zeng,
  • Jiaxin Xie

摘要

In this paper, we analyze the greedy randomized Kaczmarz (GRK) method proposed in Bai and Wu (SIAM J. Sci. Comput., 40(1), A592–A606, 2018) for solving linear systems. We develop tighter greedy probability criteria to effectively select the working row from the coefficient matrix. Notably, we prove that the linear convergence of the GRK method is deterministic and demonstrate that using a tighter threshold parameter can lead to a better convergence factor. Our result strengthens existing convergence analyses, which are solely based on the expected error by realizing that the iterates of the GRK method are random variables. Consequently, we obtain an improved iteration complexity for the GRK method. Moreover, the Polyak’s heavy ball momentum technique is incorporated to improve the performance of the GRK method. We propose a refined convergence analysis, compared with the technique used in Loizou and Richtárik (Comput. Optim. Appl., 77(3), 653–710, 2020), of momentum variants of randomized iterative methods, which shows that the proposed GRK method with momentum (mGRK) also enjoys a deterministic linear convergence. Numerical experiments show that the mGRK method is more efficient than the GRK method.