Abstract
A novel iteration scheme for solving consistent linear equations is introduced by exploring the circumcenter of a n-dimensional triangle formed with a starting point and its reflections across two hyperplanes. The proposed method, akin to the block Kaczmarz method, provides optimal linear combination within two subspaces. The convergence rate in expectation is also addressed in detail if the row is selected with probability proportional to p-norm of residuals. Numerical experiments demonstrate its superiority over randomized Kaczmarz and reflection methods, particularly evident as highly coherent rows. Performance are enhanced by proper parameter-tuning of p.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
No data was used for the research described in the article.
References
Ansorge R (1984) Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations. Computing 33(3):367–375
Bai Z-Z, Wen-Ting W (2018) On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J Sci Comput 40(1):A592–A606
Behling R, Cruz JYB, Santos L-R (2018) Circumcentering the Douglas–Rachford method. Numer Algorithms 78(3):759–776
Cimmino G (1938) Cacolo approssimato per le soluzioni dei systemi di equazioni lineari. La Ricerca Scientifica (Roma) 1:326–333
De Loera JA, Haddock J, Needell D (2017) A sampling Kaczmarz–Motzkin algorithm for linear feasibility. SIAM J Sci Comput 39(5):S66–S87
Du Y-S, Hayami K, Zheng N, Morikuni K, Yin J-F (2021) Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems. SIAM J Sci Comput 43(5):S345–S366
Duff IS, Guivarch R, Ruiz D, Zenadi M (2015) The augmented block Cimmino distributed method. SIAM J Sci Comput 37(3):A1248–A1269
Filipović D, Glau K, Nakatsukasa Y, Statti F (2019) Weighted Monte Carlo with least squares and randomized extended Kaczmarz for option pricing. Swiss Finance Institute Research Paper (19-54)
Gordon R, Bender R, Herman GT (1970) Algebraic reconstruction techniques (art) for three-dimensional electron microscopy and x-ray photography. J Theor Biol 29(3):471–481
Herman GT, Davidi R (2008) Image reconstruction from a small number of projections. Inverse Problems 24(4):045011
Iusem AN, De Pierro AR (1986) Convergence results for an accelerated nonlinear Cimmino algorithm. Numer Math 49(4):367–378
Jiang X-L, Zhang K, Yin J-F (2022) Randomized block Kaczmarz methods with k-means clustering for solving large linear systems. J Comput Appl Math 403:113828
Karczmarz S (1937) Angenäherte auflösung von systemen linearer gleichungen. Bull Int Acad Pol Sic Lett A 35:355–357
Li W, Wang Q, Bao W, Liu L (2021) On Kaczmarz method with oblique projection for solving large overdetermined linear systems. arXiv preprint arXiv:2106.13368
Lin J, Zhou D-X (2015) Learning theory of randomized Kaczmarz algorithm. J Mach Learn Res 16(1):3341–3365
Liu J, Wright S (2016) An accelerated randomized Kaczmarz algorithm. Math Comput 85(297):153–178
Moorman JD, Tu TK, Molitor D, Needell D (2021) Randomized Kaczmarz with averaging. BIT Numer Math 61(1):337–359
Needell D, Ward R (2013) Two-subspace projection method for coherent overdetermined systems. J Fourier Anal Appl 19(2):256–269
Needell D, Zhao R, Zouzias A (2015) Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl 484:322–343
Shao C (2023) A deterministic Kaczmarz algorithm for solving linear systems. SIAM J Matrix Anal Appl 44(1):212–239
Steinerberger S (2021a) Surrounding the solution of a linear system of equations from all sides. Q Appl Math 79:419–429
Steinerberger S (2021b) A weighted randomized Kaczmarz method for solving linear systems. Math Comput 90(332):2815–2826
Strohmer T, Vershynin R (2009) A randomized Kaczmarz algorithm with exponential convergence. J Fourier Anal Appl 15(2):262–278
Tan YS, Vershynin R (2019) Phase retrieval via randomized Kaczmarz: theoretical guarantees. Inf Inference J IMA 8(1):97–123
Wang F, Li W, Bao W, Liu L (2021) Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection. arXiv preprint arXiv:2106.13606
Wen-Ting W (2022) On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems. Numer Algorithms 89(1):1–31
Yin J-F, Li N, Zheng N (2022) Restarted randomized surrounding methods for solving large linear equations. Appl Math Lett 133:108290
Acknowledgements
This work is sponsored and supported by the National Natural Science Foundation of China (Grant No. 11971354).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no Conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Li, N., Yin, JF. The randomized circumcentered-reflection iteration method for solving consistent linear equations. Comp. Appl. Math. 44, 26 (2025). https://doi.org/10.1007/s40314-024-02966-2
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s40314-024-02966-2