On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems

Abstract

To enhance the computational performance of the partially randomized extended Kaczmarz (PREK) method, we propose the multi-step PREK (MPREK) method. By iteratively updating at each step, we establish a non-smooth inner-outer iteration scheme to solve the large, sparse, and inconsistent linear systems. For the MPREK method, a proof of its convergence and an upper bound on the convergence rate are given. Moreover, we show that this upper bound can be lower than that of the PREK method and the multi-step randomized extended Kaczmarz (MREK) method for certain typical choices of the inner iteration step size. Numerical experiments also indicate that, for an appropriate choice of the number of inner iteration steps, the MPREK method has a more efficient computational performance.

Keywords

Large sparse linear system / Multi-step randomized extended Kaczmarz (MREK) method / Inconsistency / Convergence property / 65F10 / 65F20 / 65F50

References

[1] BaiZ-Z. Several splittings for non-Hermitian linear systems. Sci. China Ser. A Math., 2008, 51: 1339-1348

[2] BaiZ-Z, PanJ-YMatrix Analysis and Computations, 2021, Philadelphia. SIAM.

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

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

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

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

[7] 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

[8] BaiZ-Z, WuW-T. On greedy randomized augmented Kaczmarz method for solving large sparse inconsistent linear systems. SIAM J. Sci. Comput., 2021, 43: A3892-A3911

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

[10] ByrneC. A unifed treatment of some iterative algorithms in signal processing and image re-construction. Inverse Prob., 2003, 20: 103-120

[11] CensorY. Row-action methods for huge and sparse systems and their applications. SIAM Rev., 1981, 23: 444-466

[12] CensorY. Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Program., 1988, 42: 307-325

[13] DuK. Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms. Numer. Linear Algebra Appl., 2019, 26e2233

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

[15] EldarYC, NeedellD. Acceleration of randomized Kaczmarz methods via the Johnson-Lindenstrauss lemma. Numer. Algorithms, 2011, 58: 163-177

[16] FeichtingerHG, CenkerC, MayerM, SteierH, StrohmerT. New variants of the POCS method using affine subspaces of finite codimension with applications to irregular sampling. Vis. Commun. Image Process., 1818, 1992: 299-310

[17] GordonR, BenderR, HermanGT. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol., 1970, 29: 471-481

[18] GuentherRB, KerberCW, KillianEK, SmithKT, WagnerSL. Reconstruction of objects from radiographs and the location of brain tumors. Proc. Natl. Acad. Sci., 1974, 71: 4884-4886

[19] HermanGTFundamentals of Computerized Tomography: Image Reconstruction from Projections, 2009, Berlin. Springer.

[20] HermanGT, DavidiR. Image reconstruction from a small number of projections. Inverse Prob., 2008, 24045011

[21] Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Polon. Sci. Lett. 35, 355–357 (1937)

[22] Kak, A.C., Slaney, M.: Principles of Computerized Tomographic Imaging. SIAM, Philadelphia, PA (2001)

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

[24] LiuY, GuC-Q. Variant of greedy randomized Kaczmarz for ridge regression. Appl. Numer. Math., 2019, 143: 223-246

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

[26] NeedellD, ZhaoR, ZouziasA. Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl., 2015, 484: 322-343

[27] PopaC. Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz’s relaxation. Int. J. Comput. Math., 1995, 55: 79-89

[28] PopaC. Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems. BIT, 1998, 38: 151-176

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

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

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

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

RIGHTS & PERMISSIONS

Shanghai University