{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T10:20:50Z","timestamp":1789726850323,"version":"4.0.1"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000140911052"],"award-info":[{"award-number":["N000140911052"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1348721"],"award-info":[{"award-number":["1348721"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>The Kaczmarz and Gauss--Seidel methods aim to solve an $m \\times n$ linear system $X{\\beta} = {y}$ by iteratively refining the solution estimate; the former uses random rows of $X$ to update ${\\beta}$ given the corresponding equations and the latter uses random columns of $X$ to update corresponding coordinates in ${\\beta}$. Recent work analyzed these algorithms in a parallel comparison for the overcomplete and undercomplete systems, showing convergence to the ordinary least squares (OLS) solution and the minimum Euclidean norm solution, respectively. This paper considers the natural follow-up to the OLS problem---ridge or Tikhonov regularized regression. By viewing them as variants of randomized coordinate descent, we present variants of the randomized Kaczmarz (RK) and randomized Gauss--Siedel (RGS) for solving this system and derive their convergence rates. We prove that a recent proposal, which can be interpreted as randomizing over both rows and columns, is strictly suboptimal---instead, one should always work with randomly selected columns (RGS) when $m &gt; n$ (\\#rows $&gt;$ \\#cols) and with randomly selected rows (RK) when $ n &gt; m$ (\\#cols $&gt;$ \\#rows).<\/jats:p>","DOI":"10.1137\/16m1077891","type":"journal-article","created":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T16:24:40Z","timestamp":1509035080000},"page":"S528-S542","source":"Crossref","is-referenced-by-count":48,"title":["Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression"],"prefix":"10.1137","volume":"39","author":[{"given":"Ahmed","family":"Hefny","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deanna","family":"Needell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaditya","family":"Ramdas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,10,26]]},"reference":[{"key":"atypb1","volume-title":"A. K. Peters","author":"Byrne C. L.","year":"2008"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-012-9237-2"},{"key":"atypb3","volume-title":"Coordinate Descent Face-Off: Primal or Dual?, arXiv:1605.08982","author":"Csiba D.","year":"2016"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-011-9451-z"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396365"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(70)90109-8"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(78)90214-7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/42.241889"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-723-7"},{"key":"atypb10","first-page":"270","volume":"13","author":"Ivanov A. A.","year":"2013","journal-title":"Appl. Math. E-Notes"},{"key":"atypb11","first-page":"335","volume-title":"Bull. Int. Acad. Polon. Sci. Lett. Ser. A","author":"Kaczmarz S.","year":"1937"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.24"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0456"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/15M1014425"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719284"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-010-0265-5"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0864-7"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.12.022"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-012-9248-z"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2011.02.017"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0614-z"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-02-00398-3"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1134\/S0965542512020169"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/120889897"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1077891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:10:21Z","timestamp":1787328621000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1077891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1077891"],"URL":"https:\/\/doi.org\/10.1137\/16m1077891","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}