The linear convergence of the greedy randomized Kaczmarz method is deterministic

Y Su, D Han, Y Zeng, J Xie - arXiv preprint arXiv:2307.01988, 2023 - arxiv.org
Y Su, D Han, Y Zeng, J Xie
arXiv preprint arXiv:2307.01988, 2023arxiv.org
To improve the convergence property of the randomized Kaczmarz (RK) method for solving
linear systems, Bai and Wu (SIAM J. Sci. Comput., 40 (1): A592--A606, 2018) originally
introduced a greedy probability criterion for effectively selecting the working row from the
coefficient matrix and constructed the greedy randomized Kaczmarz (GRK) method. Due to
its simplicity and efficiency, this approach has inspired numerous subsequent works in
recent years, such as the capped adaptive sampling rule, the greedy augmented …
To improve the convergence property of the randomized Kaczmarz (RK) method for solving linear systems, Bai and Wu (SIAM J. Sci. Comput., 40(1):A592--A606, 2018) originally introduced a greedy probability criterion for effectively selecting the working row from the coefficient matrix and constructed the greedy randomized Kaczmarz (GRK) method. Due to its simplicity and efficiency, this approach has inspired numerous subsequent works in recent years, such as the capped adaptive sampling rule, the greedy augmented randomized Kaczmarz method, and the greedy randomized coordinate descent method. Since the iterates of the GRK method are actually random variables, existing convergence analyses are all related to the expectation of the error. In this note, we prove that the linear convergence rate of the GRK method is deterministic, i.e. not in the sense of expectation. 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\'{a}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.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果