{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:34:56Z","timestamp":1787333696023,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100006595","name":"Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii","doi-asserted-by":"publisher","award":["39\/2017"],"award-info":[{"award-number":["39\/2017"]}],"id":[{"id":"10.13039\/501100006595","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The Kaczmarz algorithm is a simple iterative scheme for solving consistent linear systems. At each step, the method projects the current iterate onto the solution space of a single constraint. Hence, it requires low cost per iteration and storage, and it has a linear rate of convergence. Distributed implementations of Kaczmarz have recently become the de facto architectural choice for large-scale linear systems. Therefore, in this paper we develop a family of randomized block Kaczmarz algorithms that uses at each step a subset of the constraints and extrapolated stepsizes, and can be deployed on distributed computing units. Our approach is based on several new ideas and tools, including stochastic selection rules for the blocks of rows, stochastic conditioning of linear systems, and novel strategies for designing extrapolated stepsizes. We prove that randomized block Kaczmarz algorithms converge linearly in expectation, with a rate depending on the geometric properties of the matrix and its submatrices and on the size of the blocks. Our convergence analysis reveals that the algorithm is most effective when it is given a good sampling of the rows into well-conditioned blocks. Besides providing a general framework for the design and analysis of randomized block Kaczmarz methods, our results resolve an open problem in the literature related to the theoretical understanding of observed practical efficiency of extrapolated block Kaczmarz methods. We also propose an accelerated block Kaczmarz scheme, that is, acceleration in the sense of Chebyshev semi-iterative methods, where the stepsize is chosen based on the roots of Chebyshev polynomials, and we derive convergence rates depending on the square root of the geometric properties of the matrix. Finally, numerical examples illustrate the benefits of the new algorithms.<\/jats:p>","DOI":"10.1137\/19m1251643","type":"journal-article","created":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T10:50:18Z","timestamp":1574765418000},"page":"1425-1452","source":"Crossref","is-referenced-by-count":127,"title":["Faster Randomized Block Kaczmarz Algorithms"],"prefix":"10.1137","volume":"40","author":[{"given":"Ion","family":"Necoara","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,11,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-005-9010-6"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-014-0539-7"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/1023097"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-011-9401-7"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1006\/jmaa.1997.5202"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396365"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-011-9451-z"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386013"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025487"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(90)90207-S"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1259\/0007-1285-46-552-1016"},{"key":"atypb12","first-page":"355","volume":"35","author":"Kaczmarz S.","year":"1937","journal-title":"Acad. Polon. Sci. Lett. A"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"U. Khan and J. Moura,\n                      Distributed Kalman filters in sensor networks: Bipartite fusion graphs\n                      , in Proceedings of the 2007 IEEE\/SP 14th Workshop on Statistical Signal Processing, 2007, pp. 700-704.","DOI":"10.1109\/SSP.2007.4301349"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/2971"},{"key":"atypb15","unstructured":"J. Liu, S. Wright, and S. Sridhar,\n                      An Asynchronous Parallel Randomized Kaczmarz Algorithm\n                      , preprint,https:\/\/arxiv.org\/abs\/1401.4780, 2014."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0456"},{"key":"atypb17","unstructured":"X. Lian, Y. Huang, Y. Li, and J. Liu,\n                      Asynchronous parallel stochastic gradient for nonconvex optimization\n                      , in Proceeding of the 28th International Conference on Neural Information Processing Systems (NIPS'15) Volume 2, MIT Press, 2015, pp. 2737-2745."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Y. Li, K. Mo, and H. Ye,\n                      Accelerating random Kaczmarz algorithm based on clustering information\n                      , in Proceeding of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16), AAAI Press, 2016, pp. 1823-1829.","DOI":"10.1609\/aaai.v30i1.10217"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/130936269"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(63)90463-4"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/130950288"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/18M1167061"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00245-019-09609-7"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.12.022"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2015.06.027"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"M. A. Olshanskii and E. E. Tyrtyshnikov, eds.\n                      Iterative Methods for Linear Systems: Theory and Applications\n                      , SIAM, 2014,https:\/\/doi.org\/10.1137\/1.9781611973464.","DOI":"10.1137\/1.9781611973464"},{"key":"atypb29","first-page":"1","volume":"18","author":"Patrascu A.","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612715"},{"key":"atypb31","unstructured":"P. Richt\u00e1rik and M. Tak\u00e1\u010d,\n                      Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory\n                      , preprint,https:\/\/arxiv.org\/abs\/1706.01108, 2017."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"atypb33","unstructured":"R. Sun and Y. Ye,\n                      Worst-Case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version\n                      , preprint,https:\/\/arxiv.org\/abs\/1604.07130, 2016."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1142\/S1793536911000787"},{"key":"atypb35","first-page":"978","author":"Tropp J. A.","year":"2009","journal-title":"SIAM"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"L. Xiao, S. Boyd, and S. Lall,\n                      A scheme for robust distributed sensor fusion based on average consensus\n                      , in Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks (IPSN 2005), IEEE Press, 2005, pp. 63-70.","DOI":"10.1109\/IPSN.2005.1440896"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/120889897"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1251643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:18:14Z","timestamp":1787332694000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1251643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/19M1251643"],"URL":"https:\/\/doi.org\/10.1137\/19m1251643","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}