A Greedy Two-Subspace Randomized Kaczmarz Method for Solving Large Sparse Linear Systems
CSTR:
Author:
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

  • Article
  • | |
  • Metrics
  • |
  • Reference [43]
  • |
  • Related [20]
  • | | |
  • 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.

    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.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
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
Share
Article Metrics
  • Abstract:218
  • PDF: 909
  • HTML: 468
  • Cited by: 0
History
  • Received:March 19,2021
  • Online: October 18,2021
Article QR Code