A Semi-randomized Block Kaczmarz Method with Simple Random Sampling for Large-Scale Consistent Linear Systems

Abstract

The randomized block Kaczmarz (RBK) method is a randomized orthogonal projection iterative approach, which plays an important role in solving large-scale linear systems. A key point of this type of method is to select working rows effectively during iterations. However, in most of the RBK-type methods, one has to scan all the rows of the coefficient matrix in advance to compute probabilities or paving, or to compute the residual vector of the linear system in each iteration to determine the working rows. These are unfavorable for big data problems. To cure these drawbacks, we propose a semi-randomized block Kaczmarz (SRBK) method with simple random sampling for large-scale linear systems in this paper. The convergence of the proposed method is established. Numerical experiments on some real-world and large-scale data sets show that the proposed method is often superior to many state-of-the-art RBK-type methods for large linear systems.

Keywords

Randomized Kaczmarz (RK) method / Randomized block Kaczmarz (RBK) method / Semi-randomized Kaczmarz (SRK) method / Semi-randomized block Kaczmarz (SRBK) method / Simple random sampling / Large-scale linear system / 65F15 / 65F10

References

[1] Agaskar A., Wang C., Lu Y.-M.: Randomized Kaczmarz algorithms: exact MSE analysis and optimal sampling probabilities. In: IEEE Global Conference on Signal and Information Processing, Atlanta, GA, pp. 389–393 (2014)

[2] AnsorgeR. Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations. Computing, 1984, 33: 367-375

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

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

[5] BaiZ-Z, WangL, MuratovaGV. On relaxed greedy randomized augmented Kaczmarz methods for solving large sparse inconsistent linear systems. East Asian J. Appl. Math., 2021, 27: 323-332

[6] BaiZ-Z, WangL, WuW-T. On convergence rate of the randomized Gauss-Seidel method. Linear Algebra Appl., 2021, 611: 237-252

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

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

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

[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, 26e2237

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

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

[14] CarltonM. Probability and statistics for computer scientists. Am. Stat., 2008, 62: 271-272

[15] ChenJ-Q, HuangZ-D. On the error estimate of the randomized double block Kaczmarz method. Appl. Math. Comput., 2020, 370124907

[16] CloughRW, PenzienJStructural Dynamics, 1975, New York. McGrowHill Inc.

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

[18] DuK, SiW-T, SunX-H. Randomized extended average block Kaczmarz for solving least squares. SIAM J. Sci. Comput., 2020, 42: A3541-A3559

[19] ElfvingT. Block-iterative methods for consistent and inconsistent linear equations. Numer. Math., 1980, 35: 1-12

[20] FreundRW. Krylov-subspace methods for reduced-order modeling in circuit simulation. J. Comput. Appl. Math., 2000, 123: 395-421

[21] Golub, G.H., Van Loan, C.F.: Matrix Computations. 4th edn. The Johns Hopkins University Press, Baltimore (2013)

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

[23] GuoW, ChenH, GengW, LeiL. A modified Kaczmarz algorithm for computerized tomographic image reconstruction. IEEE Intern. Conf. Biom. Eng. Inf., 2009, 3: 1-4

[24] JiangY, WuG, JiangL. A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems. Adv. Comput. Math., 2023, 4920

[25] KaczmarzS. Approximate solution of systems of linear equations. Int. J. Control, 1937, 35: 355-357

[26] LeeS, KimH. Noise properties of reconstructed images in a kilo-voltage on-board imaging system with iterative reconstruction techniques: a phantom study. Phys. Med., 2014, 30: 365-373

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

[28] LiuY, GuC. On greedy randomized block Kaczmarz method for consistent linear systems. Linear Algebra Appl., 2021, 616: 178-200

[29] MaA, NeedellD, RamdasA. Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl., 2015, 36: 1590-1604

[30] MiaoC-Q, WuW-T. On greedy randomized average block Kaczmarz method for solving large linear systems. J. Comput. Appl. Math., 2022, 413114372

[31] NecoaraI. Faster randomized block Kaczmarz algorithms. SIAM J. Matrix Anal. Appl., 2019, 40: 1425-1452

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

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

[34] NiuY, ZhengB. A greedy block Kaczmarz algorithm for solving large-scale linear systems. Appl. Math. Letters., 2020, 104106294

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

[36] SaadYIterative Methods for Sparse Linear Systems, 2003, Philadelphia. SIAM. 82

[37] SakuraiT, TadanoH, KuramashiY. Application of block Krylov subspace algorithms to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD. Comput. Phys. Commun., 2010, 181: 113-117

[38] SoudaisP. Iterative solution of a 3D scattering problem from arbitrary shaped multidielectric and multiconducting bodies. IEEE Trans. Antennas Propag., 1994, 42: 954-959

[39] SteinerbergerS. A weighted randomized Kaczmarz method for solving linear systems. Math. Comput., 2021, 90: 2815-2826

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

[41] TajaddiniA, WuG, Saberi-MovahedF, AzizizadehN. Two new variants of the simpler block GMRES method with vector deflation and eigenvalue deflation for multiple linear systems. J. Sci. Comput., 2021, 869

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

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

[44] ZouziasA, FrerisN. Randomized extended Kaczmarz for solving least-squares. SIAM J. Matrix Anal. Appl., 2012, 34: 773-793

Funding

National Natural Science Foundation of China(12271518)

RIGHTS & PERMISSIONS

Shanghai University