On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

doi:10.1007/s42967-023-00358-7

Abstract

Abstract: Based on the greedy randomized Kaczmarz (GRK) method, we propose a multi-step greedy Kaczmarz method for solving large-scale consistent linear systems, utilizing multi-step projection techniques. Its convergence is proved when the linear system is consistent. Numerical experiments demonstrate that the proposed method is effective and more efficient than several existing classical Kaczmarz methods.

Key words: System of linear equations, Kaczmarz method, Greedy randomized Kaczmarz (GRK) method, Multi-step greedy Kaczmarz method, Convergence

CLC Number:

Long-Ze Tan, Ming-Yu Deng, Xue-Ping Guo. On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1580-1597.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.camc.shu.edu.cn/EN/10.1007/s42967-023-00358-7

https://www.camc.shu.edu.cn/EN/Y2025/V7/I4/1580

[1] Ansorge, R.: Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations. Computing 33(3), 367-375 (1984)
[2] Bai, Z.-Z., Jin, C.-H.: Column-decomposed relaxation methods for the overdetermined systems of linear equations. Int. J. Appl. Math. 13(1), 71-82 (2003)
[3] Bai, Z.-Z., Liu, X.-G.: On the Meany inequality with applications to convergence analysis of several row-action iteration methods. Numer. Math. 124(2), 215-236 (2013)
[4] Bai, Z.-Z., RozloznÍk, M.: On the numerical behavior of matrix splitting iteration methods for solving linear systems. SIAM J. Numer. Anal. 53(4), 1716-1737 (2015)
[5] Bai, Z.-Z., Wang, L.: On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems. Appl. Numer. Math. 192, 197-213 (2023)
[6] Bai, Z.-Z., Wang, L.: On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math. 186, 289-319 (2023)
[7] Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40(1), A592-A606 (2018)
[8] Bai, Z.-Z., Wu, W.-T.: On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems. Appl. Math. Lett. 83, 21-26 (2018)
[9] Bai, Z.-Z., Wu, W.-T.: On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl. 553, 252-269 (2018)
[10] Bai, Z.-Z., Wu, W.-T.: On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl. 578, 225-250 (2019)
[11] Bai, Z.-Z., Wu, W.-T.: On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl. 26(4), 1-15 (2019)
[12] Bai, Z.-Z., Wu, W.-T.: Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math. 40, 1-23 (2023)
[13] Brezinski, C.: Projection Methods for Systems of Equations. Elsevier Science, Amsterdam (1997)
[14] Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20(1), 103-120 (2003)
[15] Byrne, C.L.: Applied Iterative Methods. A.K. Peters, Wellesley (2007)
[16] Censor, Y.: Row-action methods for huge and sparse systems and their applications. SIAM Rev. 23(4), 444-466 (1981)
[17] Censor, Y.: Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Program. 42(1), 307-325 (1988)
[18] Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1-25 (2011)
[19] Du, K., Gao, H.: A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm. Numer. Math. Theory Methods Appl. 12(2), 627-639 (2019)
[20] Eggermont, P.P.B., Herman, G.T., Lent, A.: Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl. 40, 37-67 (1981)
[21] Elble, J.M., Sahinidis, N.V., Vouzis, P.: GPU computing with Kaczmarz’s and other iterative algorithms for linear systems. Parallel Comput. 36, 215-231 (2010)
[22] Galántai, A.: Projectors and Projection Methods. Kluwer Academic Publishers, Norwell (2004)
[23] Gower, R.M., Richtárik, P.: Stochastic dual ascent for solving linear systems. https://arxiv.org/abs/1512.06890 (2015)
[24] Herman, G.T., Davidi, R.: Image reconstruction from a small number of projections. Inverse Probl. 24(4), 1-18 (2008)
[25] Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application). IEEE Trans. Med. Imaging 12, 600-609 (1993)
[26] Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A 35, 355-357 (1937)
[27] Knight, P.A.: Error Analysis of Stationary Iteration and Associated Problems. Ph. D. thesis, Manchester University, Manchester (1993)
[28] Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641-654 (2010)
[29] Lorenz, D.A., Wenger, S., Schöpfer, F., Magnor, M.: A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing. In: 2014 IEEE International Conference on Image Processing (ICIP), Paris, France, 1347-1351 (2014)
[30] Ma, A., Needell, D., Ramdas, A.: Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl. 36, 1590-1604 (2015)
[31] McCormick, S.F.: The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space. Indiana Univ. Math. J. 26, 1137-1150 (1977)
[32] Natterer, F.: The Mathematics of Computerized Tomography. SIAM, Philadelphia (2001)
[33] Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50, 395-403 (2010)
[34] Needell, D., Tropp, J.A.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199-221 (2014)
[35] Pasqualetti, F., Carli, R., Bullo, F.: Distributed estimation via iterative projections with application to power network monitoring. Automatica J. IFAC 48, 747-758 (2012)
[36] Popa, C., Zdunek, R.: Kaczmarz extended algorithm for tomographic image reconstruction from limited-data. Math. Comput. Simul. 65, 579-598 (2004)
[37] Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262-278 (2009)
[38] Tan, L.-Z., Guo, X.-P.: On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems. Comput. Appl. Math. 42(37), 1-20 (2023)
[39] Zhang, J.-J.: A new greedy Kaczmarz algorithm for the solution of very large linear systems. Appl. Math. Lett. 91, 207-212 (2019)
[40] Zhang, J.-J., Guo, J.-H.: On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math. 157, 372-384 (2020)
[41] Zhang, K., Li, F.-T., Jiang, X.-L.: Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems. Comput. Appl. Math. 41(332), 1-25 (2022)
[42] Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34, 773-793 (2013)

On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Fei Li, Sha Li, Liuqiang Zhong, Wanwan Zhu. Modified Adaptive Two-Grid FEMs for Nonsymmetric or Indefinite Elliptic Problems [J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 831-850.
[2]	Hongying Man, Shangyou Zhang. On the Superconvergence of a Conforming Mixed Finite Element for Linear Elasticity on Uniform n-Square Grids [J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 851-867.
[3]	Reetika Chawla, Devendra Kumar, Haitao Qi. A Numerical Technique to Solve Time-Fractional Delay Diffusion Wave Equation via Trigonometric Collocation Approach [J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 909-929.
[4]	B. Yu. Irgashev. Robin Type Problem for a Degenerate Equation of Even Order with Caputo Fractional Derivative [J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 930-952.
[5]	Zhengge Huang. New Gradient-Based Iterative-Like Algorithms for Solving a Class of Sylvester Tensor Equations [J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 1005-1049.
[6]	Bei-Bei Li, Jing-Jing Cui, Zheng-Ge Huang, Xiao-Feng Xie. Two Quasi-combining Real and Imaginary Parts Iteration Methods for Solving Complex Symmetric System of Linear Equations [J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 427-455.
[7]	Lisha Chen, Zhibo Wang. A Second-Order Scheme with Nonuniform Time Grids for the Two-Dimensional Time-Fractional Zakharov-Kuznetsov Equation [J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 456-471.
[8]	Yongjun Chen, Liping Zhang. Linear Convergence of the Collatz Method for Computing the Perron Eigenpair of a Primitive Dual Number Matrix [J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 232-247.
[9]	Chunxiu Liu, Junying Cao, Tong Lyu, Xingyang Ye. Numerical Analysis of a High-Order Scheme with Nonuniform Time Grids for Caputo-Hadamard Fractional Reaction Sub-diffusion Equations [J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 338-365.
[10]	Qin-Qin Shen, Geng-Chen Yang, Chen-Can Zhou. Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1617-1638.
[11]	Xu Li, Jian-Sheng Feng. Parameterized QHSS Iteration Method and Its Variants for Non-Hermitian Positive Definite Linear Systems of Strong Skew-Hermitian Parts [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1665-1683.
[12]	Jin-Feng Mao, Fang Chen. On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1724-1743.
[13]	Lu-Xin Wang, Yang Cao, Qin-Qin Shen. Two Variants of Robust Two-Step Modulus-Based Matrix Splitting Iteration Methods for Mixed-Cell-Height Circuit Legalization Problem [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1769-1790.
[14]	Yan-Xia Dai, Ren-Yi Yan, Ai-Li Yang. Minimum Residual BAS Iteration Method for Solving the System of Absolute Value Equations [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1815-1825.
[15]	Rong Ma, Yu-Jiang Wu, Lun-Ji Song. Modified Newton-PAGSOR Method for Solving Nonlinear Systems with Complex Symmetric Jacobian Matrices [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1880-1906.