{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T06:30:47Z","timestamp":1786170647987,"version":"3.56.0"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"297","license":[{"start":{"date-parts":[[2016,5,29]],"date-time":"2016-05-29T00:00:00Z","timestamp":1464480000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n The randomized Kaczmarz (\n \n \n \n \n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {RK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ) algorithm is a simple but powerful approach for solving consistent linear systems\n \n \n \n \n A<\/mml:mi>\n x<\/mml:mi>\n =<\/mml:mo>\n b<\/mml:mi>\n <\/mml:mrow>\n Ax=b<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This paper proposes an accelerated randomized Kaczmarz (\n \n \n \n \n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {ARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ) algorithm with better convergence than the standard\n \n \n \n \n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {RK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n algorithm on ill-conditioned problems. The per-iteration cost of\n \n \n \n \n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {RK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n \n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {ARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are similar if\n \n \n \n A<\/mml:mi>\n A<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is dense, but\n \n \n \n \n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {RK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is much more able to exploit sparsity in\n \n \n \n A<\/mml:mi>\n A<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n than is\n \n \n \n \n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {ARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . To deal with the sparse case, an efficient implementation for\n \n \n \n \n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {ARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , called\n \n \n \n \n S<\/mml:mi>\n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {SARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , is proposed. A comparison of convergence rates and average per-iteration complexities among\n \n \n \n \n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {RK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ,\n \n \n \n \n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {ARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and\n \n \n \n \n S<\/mml:mi>\n A<\/mml:mi>\n R<\/mml:mi>\n K<\/mml:mi>\n <\/mml:mrow>\n \\rm {SARK}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is given, taking into account different levels of sparseness and conditioning. Comparisons with the leading deterministic algorithm \u2014 conjugate gradient applied to the normal equations \u2014 are also given. Finally, the analysis is validated via computational testing.\n <\/p>","DOI":"10.1090\/mcom\/2971","type":"journal-article","created":{"date-parts":[[2015,5,29]],"date-time":"2015-05-29T08:07:43Z","timestamp":1432886863000},"page":"153-178","source":"Crossref","is-referenced-by-count":87,"title":["An accelerated randomized Kaczmarz algorithm"],"prefix":"10.1090","volume":"85","author":[{"given":"Ji","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Wright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2015,5,29]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1016\/S0167-8191(00)00100-9","article-title":"Component averaging: an efficient iterative parallel algorithm for large and sparse unstructured problems","volume":"27","author":"Censor, Yair","year":"2001","journal-title":"Parallel Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-8191","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s11075-011-9451-z","article-title":"Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma","volume":"58","author":"Eldar, Yonina C.","year":"2011","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.jmaa.2004.12.050","article-title":"On the rate of convergence of the alternating projection method in finite dimensional spaces","volume":"310","author":"Gal\u00e1ntai, A.","year":"2005","journal-title":"J. Math. Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-247X","issn-type":"print"},{"key":"4","series-title":"Computer Science and Applied Mathematics","isbn-type":"print","volume-title":"Image reconstruction from projections","author":"Herman, Gabor T.","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/0123420504"},{"key":"5","doi-asserted-by":"crossref","unstructured":"G. T. Herman, Fundamentals of Computerized Tomography, Springer, 2009.","DOI":"10.1007\/978-1-84628-723-7"},{"key":"6","doi-asserted-by":"crossref","first-page":"263","DOI":"10.6028\/jres.049.027","article-title":"On approximate solutions of systems of linear inequalities","volume":"49","author":"Hoffman, Alan J.","year":"1952","journal-title":"J. Research Nat. Bur. Standards"},{"key":"7","unstructured":"S. Kaczmarz, Angenaherte auflsung von systemen linearer gleichungen, Bulletin International de l\u2019Acadmie Polonaise des Sciences et des Letters 35 (1937), 355\u2013357."},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1287\/moor.1100.0456","article-title":"Randomized methods for linear constraints: convergence rates and conditioning","volume":"35","author":"Leventhal, D.","year":"2010","journal-title":"Math. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"issue":"2","key":"9","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s10543-010-0265-5","article-title":"Randomized Kaczmarz solver for noisy linear systems","volume":"50","author":"Needell, Deanna","year":"2010","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"10","series-title":"Applied Optimization","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory lectures on convex optimization","volume":"87","author":"Nesterov, Yurii","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/1402075537"},{"issue":"2","key":"11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","article-title":"Efficiency of coordinate descent methods on huge-scale optimization problems","volume":"22","author":"Nesterov, Yu.","year":"2012","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"key":"12","series-title":"Springer Series in Operations Research and Financial Engineering","isbn-type":"print","volume-title":"Numerical optimization","author":"Nocedal, Jorge","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387303031","edition":"2"},{"issue":"1","key":"13","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02941906","article-title":"Characterization of the solutions set of inconsistent least-squares problems by an extended Kaczmarz algorithm","volume":"6","author":"Popa, Constantin","year":"1999","journal-title":"Korean J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1226-0061","issn-type":"print"},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/s00041-008-9030-4","article-title":"A randomized Kaczmarz algorithm with exponential convergence","volume":"15","author":"Strohmer, Thomas","year":"2009","journal-title":"J. Fourier Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1069-5869","issn-type":"print"},{"key":"15","isbn-type":"print","first-page":"210","article-title":"Introduction to the non-asymptotic analysis of random matrices","author":"Vershynin, Roman","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9781107005587"},{"key":"16","doi-asserted-by":"crossref","unstructured":"A. Zouzias and N. M. Freris, Randomized extended Kaczmarz for solving least-squares, Preprint arXiv:1205.5770v2, 2012.","DOI":"10.1137\/120889897"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02971-8\/S0025-5718-2015-02971-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02971-8\/S0025-5718-2015-02971-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:37:59Z","timestamp":1776796679000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02971-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,29]]},"references-count":16,"journal-issue":{"issue":"297","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0025-5718-2015-02971-8"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2971","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,5,29]]}}}