A Greedy Two-Subspace Randomized Kaczmarz Method for Solving Large Sparse Linear Systems

doi:10.11908/j.issn.0253-374x.21054

Home > Archive>Volume 49, Issue 10, 2021 >1473-1483. DOI:10.11908/j.issn.0253-374x.21054

A Greedy Two-Subspace Randomized Kaczmarz Method for Solving Large Sparse Linear Systems
DOI:
                        10.11908/j.issn.0253-374x.21054
                    
CSTR:
                        [cstr]
                    
Author:
                        JING Yanfei1JING Yanfei
School of Mathematical Sciences， University of Electronic Science and Technology of China， Chengdu 611731， China
Find this author on All Journals
Find this author on BaiDu
Search for this author on this site
LI Caixia1LI Caixia
School of Mathematical Sciences， University of Electronic Science and Technology of China， Chengdu 611731， China
Find this author on All Journals
Find this author on BaiDu
Search for this author on this site
HU Shaoliang2HU Shaoliang
CAEP Software Center for High Performance Numerical Simulation， Beijing 100088， China
Find this author on All Journals
Find this author on BaiDu
Search for this author on this site

                    
Affiliation:1.School of Mathematical Sciences， University of Electronic Science and Technology of China， Chengdu 611731， China;2.CAEP Software Center for High Performance Numerical Simulation， Beijing 100088， China
Clc Number:O241.6
Fund Project:

Article

Figures

Metrics

Reference [43]

Related [20]

Cited by

Materials

Comments

Abstract:

Based on an effective greedy probability criterion for selecting two working rows from a coefficient matrix， a greedy two-subspace randomized Kaczmarz method for solving large sparse linear systems is proposed. The theoretical analysis shows that this method converges to the minimal-norm solution of consistent linear systems， and the convergence factor of the method is smaller than that of the original two-subspace randomized Kaczmarz method. The numerical experiments show that this method is superior to the original two-subspace randomized Kaczmarz method from the point of view of solution performance.

Key words:two-subspace projection method;randomized Kaczmarz method;large sparse linear systems;convergence analysis

Reference

[1] BREZINSKI C. Projection methods for systems of equations [M]. Amsterdam：North-Holland Publishing Co，1997.

[2] SAAD Y. Iterative methods for sparse linear systems [M]. Philadelphia： SIAM Publisher， 2003.

[3] GALáNTAI A. Projectors and projection methods [M]. Boston： Kluwer Academic Publishers， 2003.

[4] GOLUB G H. Matrix computations[M]. 3rd ed. Baltimore： Johns Hopkins UP， 2008.

[5] KACZMARZ S. Angen?herte aufl?sung von systemen linearer gleichungen [J]. Bulletin International de l'Academie Polonaise des Sciences et des Lettres， 1937， 35： 355.

[6] ANSORGE R. Connections between the Cimmino-method and the Kaczmarz-method for the solution of singular and regular systems of equations [J]. Computing， 1984， 33： 367.

[7] CENSOR Y. Row-action methods for huge and sparse systems and their applications [J]. SIAM Review， 1981， 23： 444.

[8] KNIGHT P A. Error analysis of stationary iteration and associated problems [D]. Manchester： Manchester University， 1993.

[9] BAI Z Z， LIU X G. On the meany inequality with applications to convergence analysis of several row-action iteration methods [J]. Numerische Mathematik， 2013， 124： 215.

[10] CENSOR Y. Parallel application of block-iterative methods in medical imaging and radiation therapy [J]. Mathematical Programming， 1988， 42： 307.

[11] HERMAN G T. Fundamentals of computerized tomography： image reconstruction from projection [M]. 2nd ed. London： Springer， 2009.

[12] KAK A C， SLANEY M. Principles of computerized tomographic imaging [M]. Philadelphia： SIAM Publisher， 2003.

[13] NATTERER F. The mathematics of computerized tomography [M]. Philadelphia： SIAM Publisher， 2001.

[14] GORDON R， BENDER R， HERMAN G T. Algebraic reconstruction techniques （ART） for three-dimensional electron microscopy and X-ray photography [J]. Journal of Theoretical Biology， 1970， 29（3）： 471.

[15] HERMAN G T， DAVIDI R. Image reconstruction from a small number of projections [J]. Inverse Problems， 2008， 24（4）： 45011.

[16] HERMEN G T， MEYER L B. Algebraic reconstruction techniques can be made computationally efficient [J]. IEEE Trans Medical Imaging， 1993， 12（3）： 600.

[17] ELBLE J M， SAHINIDIS N V， VOUZIS P. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems [J]. Parallel Computing， 2010， 36（5）： 215.

[18] PASQUALETTI F， CARLI R，BULLO F. Distributed estimation via iterative projections with application to power network monitoring [J]. Automatica， 2012， 48（5）： 747.

[19] BYRNE C. A unified treatment of some iterative algorithms in signal processing and image reconstruction [J]. Inverse Problems， 2004， 20（1）： 103.

[20] LORENZ D， MAGNOR M， WENGER S， et al. A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing [C]// IEEE International Conference on Image Processing （ICIP）.[S.l.]：ICIP， 2014： 1347-1351.

[21] CENKER C， FEICHTINGER H G， MAYER M， et al. New variants of the POCS method using affine subspaces of finite codimension， with applications to irregular sampling [J]. Proceedings of SPIE - The International Society for Optical Engineering， 1992， 1818： 299.

[22] STROHMER T， VERSHYNIN R. A randomized Kaczmarz algorithm with exponential convergence [J]. Journal of Fourier Analysis and Applications， 2009， 15（2）： 262.

[23] DAI L， SOLTANALIAN M， PELCKMANS K. On the randomized Kaczmarz algorithm[J]. IEEE Signal Processing Letters， 2014， 21（3）： 330.

[24] BAI Z Z， WU W T. On greedy randomized Kaczmarz method for solving large sparse linear systems [J]. SIAM Journal on Scientific Computing， 2018， 40（1）： 592.

[25] BAI Z Z， WU W T. On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems [J]. Applied Mathematics Letters， 2018， 83： 21.

[26] 杜亦疏，殷俊锋，张科. 求解大型稀疏线性方程组的贪婪距离随机Kaczmarz方法[J]. 同济大学学报（自然科学版）， 2020， 48（8）： 1224.

[27] NEEDELL D， WARD R. Two-subspace projection method for coherent over-determined systems [J]. Journal of Fourier Analysis and Applications， 2013， 19（2）： 256.

[28] ZOUZIAS A， FRERIS N. M. Randomized extended Kaczmarz for solving least squares [J]. SIAM Journal on Matrix Analysis and Applications， 2013， 34（2）： 773.

[29] BAI Z Z，WU W T. On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems [J]. Linear Algebra and Its Applications， 2019， 578： 225.

[30] DAI L， SCHON T. On the exponential convergence of the kaczmarz algorithm[J]. IEEE Signal Processing Letters， 2015， 22（10）： 1571.

[31] OSWALD P， ZHOU W Q. Convergence analysis for Kaczmarz-type methods in a Hilbert space framework [J]. Linear Algebra and Its Applications， 2015， 478： 131.

[32] BAI Z Z， WU W T. On convergence rate of the randomized Kaczmarz method [J]. Linear Algebra and Its Applications， 2018， 553： 252.

[33] POPA C. Convergence rates for Kaczmarz-type algorithms [J]. Numerical Algorithms， 2018， 79（1）： 1.

[34] ELDAR Y C， NEEDELL D. Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma [J]. Numerical Algorithms， 2011， 58（2）： 163.

[35] XIANG X， CHENG L Z. An accelerated randomized Kaczmarz method via low-rank approximation [J]. International Journal of Computer Mathematics， 2015， 92（7）： 1413.

[36] LEVENTHAL D， LEWIS A S. Randomized methods for linear constraints： convergence rates and conditioning [J]. Mathematics of Operations Research， 2010， 35（3）： 641.

[37] MA A， NEEDELL D， RAMDAS A. Convergence properties of the randomized extended Gauss–Seidel and Kaczmarz methods [J]. SIAM Journal on Matrix Analysis and Applications， 2015， 36（4）： 1590.

[38] DU K. Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms [J]. Numerical Linear Algebra with Applications， 2019， 26（3）： e2233.

[39] NEEDELL D， TROPP J A. Paved with good intentions： analysis of a randomized block Kaczmarz method [J]. Linear Algebra and Its Applications， 2014， 441： 199.

[40] NEEDELL D， ZHAO R， ZOUZIAS A. Randomized block Kaczmarz method with projection for solving least squares [J]. Linear Algebra and Its Applications， 2015， 484： 322.

[41] NUTINI J， SEPEHRY B， LARADJI I， et al. Convergence rates for greedy Kaczmarz algorithms， and faster randomized Kaczmarz rules using the orthogonality graph [J]. arXiv， 2016， 1612.07838.

[42] HOLODNAK J T，IPSEN I C F. Randomized approximation of the Gram matrix： Exact computation and probabilistic bounds [J]. SIAM Journal on Matrix Analysis and Applications， 2015， 36（1）： 110.

[43] DU Y S， HAYAMI K， ZHENG N， et al. Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems [J]. arXiv，2020，2006.10818.

Get Citation

JING Yanfei, LI Caixia, HU Shaoliang. A Greedy Two-Subspace Randomized Kaczmarz Method for Solving Large Sparse Linear Systems[J].同济大学学报(自然科学版),2021,49(10):1473~1483

Copy

Article Metrics

Abstract:220
PDF: 909
HTML: 468
Cited by: 0

History

Received:March 19,2021
Revised:
Adopted:
Online: October 18,2021
Published:

Get Citation

Share

Article Metrics

History

Article QR Code