×

zbMATH — the first resource for mathematics

On the error estimate of the randomized double block Kaczmarz method. (English) Zbl 1441.65033
The authors are concerned with the randomized double block Kaczmarz method developed for inconsistent linear systems by D. Needell et al. [Linear Algebra Appl. 484, 322–343 (2015; Zbl 1330.65056)]. They shorten the original convergence proof and show that the method converges for any proper initial condition.
MSC:
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
68W20 Randomized algorithms
Software:
SparseMatrix
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Byrne, C., A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20, 103-120 (2004) · Zbl 1051.65067
[2] Bai, Z.-Z.; Liu, X. G., On the meany inequality with applications to convergence analysis of several row-action iteration methods, Numer. Math., 124, 215-236 (2013) · Zbl 1306.15015
[3] Bai, Z.-Z.; Wu, W. T., On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40, A592-A606 (2018) · Zbl 1383.65024
[4] Bai, Z.-Z.; Wu, W. T., On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83, 21-26 (2018) · Zbl 06892553
[5] Bai, Z.-Z.; Wu, W. T., On convergence rate of the randomized Kaczmarz method, Linear Algebra Appl., 553, 252-269 (2018) · Zbl 1391.65063
[6] Bai, Z.-Z.; Wu, W. T., On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems, Linear Algebra Appl., 578, 225-250 (2019) · Zbl 1420.65028
[7] Bai, Z.-Z.; Wu, W. T., On greedy randomized coordinate descent methods for solving large linear least-squares problems, Numer. Linear Algebra Appl., 26, e2237, 1-15 (2019) · Zbl 1449.65128
[8] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23, 444-466 (1981) · Zbl 0469.65037
[9] Censor, Y., Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Program., 42, 307-325 (1988) · Zbl 0658.90099
[10] Davis, T. A.; Hu, Y., The university of florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1-25 (2011) · Zbl 1365.65123
[11] Elfving, T., Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35, 1-12 (1980) · Zbl 0416.65031
[12] Eggermont, P. P.B.; Herman, G. T.; Lent, A., Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Linear Algebra Appl., 40, 37-67 (1981) · Zbl 0466.65021
[13] Elble, J. M.; Sahinidis, N. V.; Vouzis, P., GPU computing with Kaczmarz’s and other iterative algorithms for linear systems, Parallel Comput., 36, 215-231 (2010) · Zbl 1204.68260
[14] Gordon, R.; Bender, R.; Herman, G. T., Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography, J. Theor. Biol., 29, 471-481 (1970)
[15] Guenther, R. B.; Kerber, C. W.; Killian, E. K.; Smith, K. T.; Wagner, S. L., Reconstruction of objects from radiographs and location of brain tumors, Proc. Nat. Acad. Sci. USA, 71, 4884-4886 (1974)
[16] Houndfield, G. N., Computerized transverse axial scanning (tomography): part I. Description of system, Br. J. Radiol., 46, 1016-1022 (1973)
[17] Herman, G. T.; Meyer, L. B., Algebraic reconstruction techniques can be made computationally efficient, IEEE T. Med. Imaging, 12, 600-609 (1993)
[18] Kaczmarz, S., Angenäherte auflösung von systemen linearer gleichungen, Bull. Int. Acad. Polon. Sci. Lett. A, 35, 355-357 (1937) · Zbl 0017.31703
[19] Kak, A. C.; Slaney, M., Principles of Computerized Tomographic Imaging (2001), SIAM: SIAM Philadelphia, PA · Zbl 0984.92017
[20] Leventhal, D.; Lewis, A. S., Randomized methods for linear constraints: convergence rates and conditioning, Math. Oper. Res., 35, 641-654 (2010) · Zbl 1216.15006
[21] Ma, A.; Needell, D.; Ramdas, A., Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36, 1590-1604 (2015) · Zbl 1327.65112
[22] Needell, D., Randomized Kaczmarz solver for noisy linear systems, BIT, 50, 395-403 (2010) · Zbl 1195.65038
[23] Needell, D.; Tropp, J. A., Paved with good intentions: analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441, 199-221 (2014) · Zbl 1282.65042
[24] Needell, D.; Ward, R., Two-subspace projection method for coherent overdetermined systems, J. Fourier Anal. Appl., 19, 256-269 (2013) · Zbl 1306.65190
[25] Needell, D.; Zhao, R.; Zouzias, A., Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484, 322-343 (2015) · Zbl 1330.65056
[26] Popa, C., Convergence rates for Kaczmarz-type algorithms, Numer. Algorithms, 79, 1-17 (2018) · Zbl 1398.65049
[27] Popa, C.; Zdunek, R., Kaczmarz extended algorithm for tomographic image reconstruction from limited-data, Math. Comput. Simul., 65, 579-598 (2004)
[28] Pasqualetti, F.; Carli, R.; Bullo, F., Distributed estimation via iterative projections with application to power network monitoring, Automatica, 48, 747-758 (2012) · Zbl 1246.93108
[29] Petra, S.; Popa, C., Single projection Kaczmarz extended algorithms, Numer. Algorithms, 73, 791-806 (2016) · Zbl 1376.65062
[30] Strohmer, T.; Vershynin, R., A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 262-278 (2009) · Zbl 1169.68052
[31] C. Wang, A. Agaskar, Y.M. Lu, Randomized Kaczmarz algorithm for inconsistent linear systems: an exact MSE analysis, Proceedings of International Conference on Sampling Theory and Applications(2015) 498-502.
[32] Zouzias, A.; Freris, N. M., Randomized extended Kaczmarz for solving least squares, SIAM J. Matrix Anal. Appl., 34, 773-793 (2013) · Zbl 1273.65053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.