A New Theoretical Estimate for the Convergence Rate of the Maximal Weighted Residual Kaczmarz Algorithm
Year: 2019
Numerical Mathematics: Theory, Methods and Applications, Vol. 12 (2019), Iss. 2 : pp. 627–639
Abstract
In this note we prove a new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm for solving a consistent linear system. The estimate depends only on quantities that are easy to compute and not on the number of equations in the system. We compare the maximal weighted residual Kaczmarz algorithm and the greedy randomized Kaczmarz algorithm by two sets of examples. Numerical results show that the maximal weighted residual Kaczmarz algorithm requires almost the same number of iterations as that of the greedy randomized Kaczmarz algorithm for underdetermined linear systems and less iterations for overdetermined linear systems. Due to less computational cost in the row index selection strategy, the maximal weighted residual Kaczmarz algorithm is more efficient than the greedy randomized Kaczmarz algorithm.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/nmtma.OA-2018-0039
Numerical Mathematics: Theory, Methods and Applications, Vol. 12 (2019), Iss. 2 : pp. 627–639
Published online: 2019-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 13
-
Gauss–Seidel method with oblique direction
Wang, Fang | Li, Weiguo | Bao, Wendi | Lv, ZhongluResults in Applied Mathematics, Vol. 12 (2021), Iss. P.100180
https://doi.org/10.1016/j.rinam.2021.100180 [Citations: 3] -
On the adaptive deterministic block Kaczmarz method with momentum for solving large-scale consistent linear systems
Tan, Longze | Guo, Xueping | Deng, Mingyu | Chen, JingrunJournal of Computational and Applied Mathematics, Vol. 457 (2025), Iss. P.116328
https://doi.org/10.1016/j.cam.2024.116328 [Citations: 0] -
Randomized average block iterative methods for solving factorised linear systems
Zhao, Jing | Wang, Xiang | Zhang, JianhuaFilomat, Vol. 37 (2023), Iss. 14 P.4603
https://doi.org/10.2298/FIL2314603Z [Citations: 0] -
On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems
Tan, Long-Ze | Deng, Ming-Yu | Guo, Xue-PingCommunications on Applied Mathematics and Computation, Vol. (2024), Iss.
https://doi.org/10.1007/s42967-023-00358-7 [Citations: 0] -
RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression
Gazagnadou, Nidham | Ibrahim, Mark | Gower, Robert M.SIAM Journal on Matrix Analysis and Applications, Vol. 43 (2022), Iss. 3 P.1440
https://doi.org/10.1137/21M1422963 [Citations: 4] -
Randomized Extended Average Block Kaczmarz for Solving Least Squares
Du, Kui | Si, Wu-Tao | Sun, Xiao-HuiSIAM Journal on Scientific Computing, Vol. 42 (2020), Iss. 6 P.A3541
https://doi.org/10.1137/20M1312629 [Citations: 55] -
Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
Haddock, Jamie | Ma, AnnaSIAM Journal on Mathematics of Data Science, Vol. 3 (2021), Iss. 1 P.342
https://doi.org/10.1137/19M1307044 [Citations: 30] -
On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations
Tan, Yun-Xia | Huang, Zheng-DaCommunications on Applied Mathematics and Computation, Vol. (2024), Iss.
https://doi.org/10.1007/s42967-024-00427-5 [Citations: 0] -
On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
Zhang, Jianhua | Guo, JinghuiApplied Numerical Mathematics, Vol. 157 (2020), Iss. P.372
https://doi.org/10.1016/j.apnum.2020.06.014 [Citations: 18] -
Research on Water Pollution in River Groundwater Systems
王, 雨茼
Advances in Applied Mathematics, Vol. 13 (2024), Iss. 03 P.934
https://doi.org/10.12677/AAM.2024.133088 [Citations: 0] -
Greedy Motzkin–Kaczmarz methods for solving linear systems
Zhang, Yanjun | Li, HanyuNumerical Linear Algebra with Applications, Vol. 29 (2022), Iss. 4
https://doi.org/10.1002/nla.2429 [Citations: 11] -
Greedy randomized sampling nonlinear Kaczmarz methods
Zhang, Yanjun | Li, Hanyu | Tang, LingCalcolo, Vol. 61 (2024), Iss. 2
https://doi.org/10.1007/s10092-024-00577-1 [Citations: 4] -
Accelerated Pseudo-Inverse-Free Greedy Block Methods in the Kaczmarz Algorithm Category
颜, 鑫鹏
Advances in Applied Mathematics, Vol. 13 (2024), Iss. 01 P.466
https://doi.org/10.12677/AAM.2024.131046 [Citations: 0] -
Accelerated Randomized Coordinate Descent for Solving Linear Systems
Wang, Qin | Li, Weiguo | Bao, Wendi | Zhang, FeiyuMathematics, Vol. 10 (2022), Iss. 22 P.4379
https://doi.org/10.3390/math10224379 [Citations: 1] -
On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation AXB=C
Wu, Nian-Ci | Liu, Cheng-Zhi | Zuo, QianJournal of Computational and Applied Mathematics, Vol. 413 (2022), Iss. P.114374
https://doi.org/10.1016/j.cam.2022.114374 [Citations: 9] -
A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
Zhang, Yanjun | Li, HanyuApplied Mathematics and Computation, Vol. 410 (2021), Iss. P.126486
https://doi.org/10.1016/j.amc.2021.126486 [Citations: 5] -
Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
Wang, Fang | Li, Weiguo | Bao, Wendi | Liu, LiElectronic Research Archive, Vol. 30 (2022), Iss. 4 P.1158
https://doi.org/10.3934/era.2022062 [Citations: 1] -
Quantile-based Random Kaczmarz for corrupted linear systems of equations
Steinerberger, Stefan
Information and Inference: A Journal of the IMA, Vol. 12 (2023), Iss. 1 P.448
https://doi.org/10.1093/imaiai/iaab029 [Citations: 7] -
On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems
Tan, Long-Ze | Guo, Xue-PingComputational and Applied Mathematics, Vol. 42 (2023), Iss. 1
https://doi.org/10.1007/s40314-022-02163-z [Citations: 0]