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

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.

Keywords

System of linear equations / Kaczmarz method / Greedy randomized Kaczmarz (GRK) method / Multi-step greedy Kaczmarz method / Convergence

References

[1] AnsorgeR. Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations. Computing., 1984, 333367-375.

[2] BaiZ-Z, JinC-H. Column-decomposed relaxation methods for the overdetermined systems of linear equations. Int. J. Appl. Math., 2003, 13171-82

[3] BaiZ-Z, LiuX-G. On the Meany inequality with applications to convergence analysis of several row-action iteration methods. Numer. Math., 2013, 1242215-236.

[4] BaiZ-Z, RozloznÍkM. On the numerical behavior of matrix splitting iteration methods for solving linear systems. SIAM J. Numer. Anal., 2015, 5341716-1737.

[5] BaiZ-Z, WangL. On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems. Appl. Numer. Math., 2023, 192: 197-213.

[6] BaiZ-Z, WangL. On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math., 2023, 186: 289-319.

[7] BaiZ-Z, WuW-T. On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput., 2018, 401A592-A606.

[8] BaiZ-Z, WuW-T. On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems. Appl. Math. Lett., 2018, 83: 21-26.

[9] BaiZ-Z, WuW-T. On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl., 2018, 553: 252-269.

[10] BaiZ-Z, WuW-T. On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl., 2019, 578: 225-250.

[11] BaiZ-Z, WuW-T. On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numer. Linear Algebra Appl., 2019, 2641-15.

[12] BaiZ-Z, WuW-T. Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory. Jpn. J. Ind. Appl. Math., 2023, 40: 1-23.

[13] BrezinskiCProjection Methods for Systems of Equations, 1997AmsterdamElsevier Science

[14] ByrneC. A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl., 2003, 201103-120.

[15] ByrneCLApplied Iterative Methods, 2007WellesleyA.K. Peters.

[16] CensorY. Row-action methods for huge and sparse systems and their applications. SIAM Rev., 1981, 234444-466.

[17] CensorY. Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Program., 1988, 421307-325.

[18] DavisTA, HuY. The University of Florida sparse matrix collection. ACM Trans. Math. Softw., 2011, 38: 1-25

[19] DuK, GaoH. A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm. Numer. Math. Theory Methods Appl., 2019, 122627-639.

[20] EggermontPPB, HermanGT, LentA. Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl., 1981, 40: 37-67.

[21] ElbleJM, SahinidisNV, VouzisP. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems. Parallel Comput., 2010, 36: 215-231.

[22] GalántaiAProjectors and Projection Methods, 2004NorwellKluwer Academic Publishers.

[23] Gower, R.M., Richtárik, P.: Stochastic dual ascent for solving linear systems. https://arxiv.org/abs/1512.06890 (2015)

[24] HermanGT, DavidiR. Image reconstruction from a small number of projections. Inverse Probl., 2008, 2441-18.

[25] HermanGT, MeyerLB. Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application). IEEE Trans. Med. Imaging, 1993, 12: 600-609.

[26] KaczmarzS. Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A, 1937, 35: 355-357

[27] Knight, P.A.: Error Analysis of Stationary Iteration and Associated Problems. Ph. D. thesis, Manchester University, Manchester (1993)

[28] LeventhalD, LewisAS. Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res., 2010, 35: 641-654.

[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] MaA, NeedellD, RamdasA. Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl., 2015, 36: 1590-1604.

[31] McCormickSF. The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space. Indiana Univ. Math. J., 1977, 26: 1137-1150.

[32] NattererFThe Mathematics of Computerized Tomography, 2001PhiladelphiaSIAM.

[33] NeedellD. Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math., 2010, 50: 395-403.

[34] NeedellD, TroppJA. Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl., 2014, 441: 199-221.

[35] PasqualettiF, CarliR, BulloF. Distributed estimation via iterative projections with application to power network monitoring. Automatica J. IFAC, 2012, 48: 747-758.

[36] PopaC, ZdunekR. Kaczmarz extended algorithm for tomographic image reconstruction from limited-data. Math. Comput. Simul., 2004, 65: 579-598.

[37] StrohmerT, VershyninR. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl., 2009, 15: 262-278.

[38] TanL-Z, GuoX-P. On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems. Comput. Appl. Math., 2023, 42371-20

[39] ZhangJ-J. A new greedy Kaczmarz algorithm for the solution of very large linear systems. Appl. Math. Lett., 2019, 91: 207-212.

[40] ZhangJ-J, GuoJ-H. On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math., 2020, 157: 372-384.

[41] ZhangK, LiF-T, JiangX-L. Multi-step greedy Kaczmarz algorithms with simple random sampling for solving large linear systems. Comput. Appl. Math., 2022, 413321-25

[42] ZouziasA, FrerisNM. Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl., 2013, 34: 773-793.

Funding

National Natural Science Foundation of China(No. 12071149)

Science and Technology Commission of Shanghai Municipality(No. 22DZ2229014)

National Key R &D Program of China(No. 2022YFA1004403)

RIGHTS & PERMISSIONS

Shanghai University