On maximum residual block Kaczmarz method for solving large consistent linear systems

Wen-Ning Sun; Mei Qin; Wen-Ning Sun; Mei Qin

doi:10.3934/math.20241614

AIMS Mathematics

2024, Volume 9, Issue 12: 33843-33860. doi: 10.3934/math.20241614

Previous Article Next Article

Research article Special Issues

On maximum residual block Kaczmarz method for solving large consistent linear systems

Wen-Ning Sun ,
Mei Qin ^,

College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China

Received: 25 September 2024 Revised: 21 November 2024 Accepted: 25 November 2024 Published: 28 November 2024
MSC : 65F10, 65F20

In this paper, we propose two block variants of the Kaczmarz method for solving large-scale consistent linear equations $ Ax = b $. The first method, named the maximum residual block Kaczmarz (denoted as MRBK) method, first partitions the coefficient matrix, and then captures the largest block in the residual vector during each block iteration to ensure that it is eliminated first. Simultaneously, in order to avoid the pseudo-inverse calculation of the MRBK method during block iteration and improve the convergence speed, we further propose the maximum residual average block Kaczmarz method. This method completes the iterative process by projecting the current solution vector onto each row of the constrained subset of the matrix $ A $ and averaging it with different extrapolation steps. We analyze and prove the deterministic convergence of both methods. Numerical experiments validate our theory and show that our proposed methods are superior to some other block Kaczmarz methods.
- consistent linear system,
- maximum residual block Kaczmarz,
- maximum residual average block Kaczmarz,
- free pseudo-inverse,
- convergence property
Citation: Wen-Ning Sun, Mei Qin. On maximum residual block Kaczmarz method for solving large consistent linear systems[J]. AIMS Mathematics, 2024, 9(12): 33843-33860. doi: 10.3934/math.20241614

Related Papers:

Abstract

In this paper, we propose two block variants of the Kaczmarz method for solving large-scale consistent linear equations $ Ax = b $. The first method, named the maximum residual block Kaczmarz (denoted as MRBK) method, first partitions the coefficient matrix, and then captures the largest block in the residual vector during each block iteration to ensure that it is eliminated first. Simultaneously, in order to avoid the pseudo-inverse calculation of the MRBK method during block iteration and improve the convergence speed, we further propose the maximum residual average block Kaczmarz method. This method completes the iterative process by projecting the current solution vector onto each row of the constrained subset of the matrix $ A $ and averaging it with different extrapolation steps. We analyze and prove the deterministic convergence of both methods. Numerical experiments validate our theory and show that our proposed methods are superior to some other block Kaczmarz methods.

References

[1]	L.-P. Sun, Y.-M. Wei, J.-Y. Zhou, On an iterative method for solving the least squares problem of rank-deficient systems, Int. J. Comput. Math., 92 (2014), 532–541. https://doi.org/10.1080/00207160.2014.900173 doi: 10.1080/00207160.2014.900173
[2]	Z.-Z. Bai, C.-H. Jin, Column-decomposed relaxation methods for the overdetermined systems of linear equations, Int. J. Appl. Math., 13 (2003), 71–82.
[3]	S. Kaczmarz, Angenäherte Auflösung von systemen linearer gleichungen, Bull. Int. Acad. Polon. Sci. Lett., 35 (1937), 355–357.
[4]	M. A. Brooks, A survey of algebraic algorithms in computerized tomography, Oshawa: University of Ontario Institute of Technology, 2010.
[5]	G. N. Hounsfield, Computerized transverse axial scanning (tomography): Part 1. Description of system, Brit. J. Radiol., 46 (1973), 1016–1022. https://doi.org/10.1259/0007-1285-46-552-1016 doi: 10.1259/0007-1285-46-552-1016
[6]	G. T. Herman, Fundamentals of computerized tomography: Image reconstruction from projections, 2 Eds., London: Springer, 2009. https://doi.org/10.1007/978-1-84628-723-7
[7]	F. Natterer, The mathematics of computerized tomography, Philadelphia: SIAM Publications, 2001. https://doi.org/10.1137/1.9780898719284
[8]	G. T. Herman, R. Davidi, Image reconstruction from a small number of projections, Inverse Probl., 24 (2008), 045011. https://doi.org/10.1088/0266-5611/24/4/045011 doi: 10.1088/0266-5611/24/4/045011
[9]	R. Gordon, R. Bender, G. T. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theor. Biol., 29 (1970), 471–481. https://doi.org/10.1016/0022-5193(70)90109-8 doi: 10.1016/0022-5193(70)90109-8
[10]	G. T. Herman, L. B. Meyer, Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application), IEEE. Trans. Med. Imaging, 12 (1993), 600–609. https://doi.org/10.1109/42.241889 doi: 10.1109/42.241889
[11]	C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (2004), 103. https://doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
[12]	D. A. Lorenz, S. Wenger, F. Schöpfer, M. Magnor, A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing, In: 2014 IEEE International conference on image processing, 2014, 1347–1351. https://doi.org/10.1109/ICIP.2014.7025269
[13]	F. Pasqualetti, R. Carli, F. Bullo, Distributed estimation via iterative projections with application to power network monitoring, Automatica, 48 (2012), 747–758. https://doi.org/10.1016/j.automatica.2012.02.025 doi: 10.1016/j.automatica.2012.02.025
[14]	J. M. Elble, N. V. Sahinidis, P. Vouzis, GPU computing with Kaczmarz's and other iterative algorithms for linear systems, Parallel Comput., 36 (2010), 215–231. https://doi.org/10.1016/j.parco.2009.12.003 doi: 10.1016/j.parco.2009.12.003
[15]	A. Galántai, Projectors and projection methods, New York: Springer, 2004. https://doi.org/10.1007/978-1-4419-9180-5
[16]	P. A. Knight, Error analysis of stationary iteration and associated problems, Manchester: University of Manchester, 1993.
[17]	Z.-Z. Bai, X.-G. Liu, On the Meany inequality with applications to convergence analysis of several row-action iteration methods, Numer. Math., 124 (2013), 215–236. https://doi.org/10.1007/s00211-012-0512-6 doi: 10.1007/s00211-012-0512-6
[18]	A. Ma, D. Needell, A. Ramdas, Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36 (2015), 1590–1604. https://doi.org/10.1137/15M1014425 doi: 10.1137/15M1014425
[19]	L. Dai, T. B. Schön, On the exponential convergence of the Kaczmarz algorithm, IEEE Signal Process. Lett., 22 (2015), 1571–1574. https://doi.org/10.1109/LSP.2015.2412253 doi: 10.1109/LSP.2015.2412253
[20]	T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
[21]	Z.-Z. Bai, W.-T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
[22]	R. Ansorge, Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations, Computing, 33 (1984), 367–375. https://doi.org/10.1007/bf02242280 doi: 10.1007/bf02242280
[23]	C. Popa, Convergence rates for Kaczmarz-type algorithms, Numer. Algor., 79 (2018), 1–17. https://doi.org/10.1007/s11075-017-0425-7 doi: 10.1007/s11075-017-0425-7
[24]	Z.-Z. Bai, W.-T. Wu, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), 21–26. https://doi.org/10.1016/j.aml.2018.03.008 doi: 10.1016/j.aml.2018.03.008
[25]	J.-J. Zhang, A new greedy Kaczmarz algorithm for the solution of very large linear systems, Appl. Math. Lett., 91 (2019), 207–212. https://doi.org/10.1016/j.aml.2018.12.022 doi: 10.1016/j.aml.2018.12.022
[26]	Z.-Z. Bai, W.-T. Wu, On convergence rate of the randomized Kaczmarz method, Linear Algebra Appl., 553 (2018), 252–269. https://doi.org/10.1016/j.laa.2018.05.009 doi: 10.1016/j.laa.2018.05.009
[27]	Y. Jiang, G. Wu, L. Jiang, A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems, Adv. Comput. Math., 49 (2023), 20. https://doi.org/10.1007/s10444-023-10018-2 doi: 10.1007/s10444-023-10018-2
[28]	Y. Zeng, D. Han, Y. Su, J. Xie, Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems, Numer. Algor., 94 (2023), 1403–1420. https://doi.org/10.1007/s11075-023-01540-x doi: 10.1007/s11075-023-01540-x
[29]	Z.-Z. Bai, W.-T. Wu, Randomized Kaczmarz iteration methods: Algorithmic extensions and convergence theory, Japan J. Indust. Appl. Math., 40 (2023), 1421–1443. https://doi.org/10.1007/s13160-023-00586-7 doi: 10.1007/s13160-023-00586-7
[30]	Z.-Z. Bai, L. Wang, On convergence rates of Kaczmarz-type methods with di erent selection rules of working rows, Appl. Numer. Math., 186 (2023), 289–319. https://doi.org/10.1016/j.apnum.2023.01.013 doi: 10.1016/j.apnum.2023.01.013
[31]	X.-Z. Wang, M.-L. Che, Y.-M. Wei, Randomized Kaczmarz methods for tensor complementarity problems, Comput. Optim. Appl., 82 (2022), 595–615. https://doi.org/10.1007/s10589-022-00382-y doi: 10.1007/s10589-022-00382-y
[32]	D. Needell, J. A. Tropp, Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. https://doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
[33]	D. Needell, R. Zhao, A. Zouzias, Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484 (2015), 322–343. https://doi.org/10.1016/j.laa.2015.06.027 doi: 10.1016/j.laa.2015.06.027
[34]	Y. Liu, C.-Q. Gu, On greedy randomized block Kaczmarz method for consistent linear systems, Linear Algebra Appl., 616 (2021), 178–200. https://doi.org/10.1016/j.laa.2021.01.024 doi: 10.1016/j.laa.2021.01.024
[35]	I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. Appl., 40 (2019), 1425–1452. https://doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
[36]	C.-Q. Miao, W.-T. Wu, On greedy randomized average block Kaczmarz method for solving large linear systems, J. Comput. Appl. Math., 413 (2022), 114372. https://doi.org/10.1016/j.cam.2022.114372 doi: 10.1016/j.cam.2022.114372
[37]	W. Li, F. Yin, Y.-M. Liao, G.-X. Huang, A greedy average block Kaczmarz method for the large scaled consistent system of linear equations, AIMS Mathematics, 7 (2022), 6792–6806. https://doi.org/10.3934/math.2022378 doi: 10.3934/math.2022378
[38]	A.-Q. Xiao, J.-F. Yin, N. Zheng, On fast greedy block Kaczmarz methods for solving large consistent linear systems, Comput. Appl. Math., 42 (2023), 119. https://doi.org/10.1007/s40314-023-02232-x doi: 10.1007/s40314-023-02232-x
[39]	J. Briskman, D. Needell, Block Kaczmarz method with inequalities, J. Math. Imaging Vis., 52 (2015), 385–396. https://doi.org/10.1007/s10851-014-0539-7 doi: 10.1007/s10851-014-0539-7
[40]	Y. Zhang, H. Li, Block sampling Kaczmarz-Motzkin methods for consistent linear systems, Calcolo, 58 (2021), 39. https://doi.org/10.1007/s10092-021-00429-2 doi: 10.1007/s10092-021-00429-2
[41]	Y. Zhang, H. Li, Randomized block subsampling Kaczmarz-Motzkin method, Linear Algebra Appl., 667 (2023), 133–150. https://doi.org/10.1016/j.laa.2023.03.003 doi: 10.1016/j.laa.2023.03.003
[42]	R.-R. Li, H. Liu, On randomized partial block Kaczmarz method for solving huge linear algebraic systems, Comput. Appl. Math., 41 (2022), 278. https://doi.org/10.1007/s40314-022-01978-0 doi: 10.1007/s40314-022-01978-0
[43]	J.-Q. Chen, Z.-D. Huang, On a fast deterministic block Kaczmarz method for solving large-scale linear systems, Numer. Algor., 89 (2022), 1007–1029. https://doi.org/10.1007/s11075-021-01143-4 doi: 10.1007/s11075-021-01143-4
[44]	Å. Björck, Numerical methods for least squares problems, Philadelphia: SIAM Publications, 1996. https://doi.org/10.1137/1.9781611971484
[45]	S. P. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. A. Davis, M. Henderson, et al., The SuiteSparse matrix collection website interface, J. Open Source Softw., 4 (2019), 1244. https://doi.org/10.21105/joss.01244 doi: 10.21105/joss.01244

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)