{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:54:04Z","timestamp":1787385244947,"version":"3.56.0"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-06CH11347"],"award-info":[{"award-number":["DE-AC02-06CH11347"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100001395","name":"Wisconsin Alumni Research Foundation","doi-asserted-by":"publisher","award":["AAD5914"],"award-info":[{"award-number":["AAD5914"]}],"id":[{"id":"10.13039\/100001395","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Randomized linear system solvers have become popular as they have the potential to reduce floating point complexity while still achieving desirable convergence rates. One particularly promising class of methods, random sketching solvers, has achieved the best known computational complexity bounds in theory, but is blunted by two practical considerations: there is no clear way of choosing the size of the sketching matrix a priori; and there is a nontrivial storage cost of the sketched system. In this work, we make progress towards addressing these issues by implicitly generating the sketched system and solving it simultaneously through an iterative procedure. As a result, we replace the question of the size of the sketching matrix with determining appropriate stopping criteria; we also avoid the costs of explicitly representing the sketched linear system; and our implicit representation also solves the system at the same time, which controls the per-iteration computational costs. Additionally, our approach allows us to generate a connection between random sketching methods and randomized iterative solvers (e.g., the randomized Kaczmarz method and randomized Gauss--Seidel). As a consequence, we exploit this connection to (1) produce a stronger, more precise convergence theory for such randomized iterative solvers under arbitrary sampling schemes (i.i.d., adaptive, permutation, dependent, etc.), and (2) improve the rates of convergence of randomized iterative solvers at the expense of a user-determined increase in per-iteration computational and storage costs. We demonstrate these concepts on numerical examples on 49 distinct linear systems.<\/jats:p>","DOI":"10.1137\/19m1259481","type":"journal-article","created":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T15:32:04Z","timestamp":1623166324000},"page":"800-831","source":"Crossref","is-referenced-by-count":4,"title":["An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems"],"prefix":"10.1137","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4130-0897","authenticated-orcid":true,"given":"Vivak","family":"Patel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Jahangoshahi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel A.","family":"Maldonado","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-037-2"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-012-0512-6"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/17M1137747"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/1023097"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-012-9237-2"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2015.2412253"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90126-8"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"R. Durrett,\n                      Probability: Theory and Examples\n                      , Cambridge University Press, Cambridge, UK, 2010.","DOI":"10.1017\/CBO9780511779398"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2004.12.050"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-005-0615-4"},{"key":"atypb13","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(70)90109-8"},{"key":"atypb15","unstructured":"R. Gower, D. Molitor, J. Moorman, and D. Needell,\n                      Adaptive Sketch-and-Project Methods for Solving Linear Systems\n                      , preprint,https:\/\/arxiv.org\/abs\/1909.03604, 2019."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025487"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90113-9"},{"key":"atypb18","unstructured":"J. Haddock and A. Ma,\n                      Greed Works: An Improved Analysis of Sampling Kaczmarz-Motkzin\n                      , preprint,https:\/\/arxiv.org\/abs\/1912.03544, 2019."},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. R. Hestenes,\n                      Conjugate Direction Methods in Optimization\n                      , Appl. Math. 12, Springer-Verlag, New York, Berlin, 1980.","DOI":"10.1007\/978-1-4612-6048-6"},{"key":"atypb20","first-page":"604","author":"Indyk P.","year":"1998","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1080\/00207179308934446"},{"key":"atypb22","first-page":"355","volume":"35","author":"Kaczmarz S.","year":"1937","journal-title":"Acad. Polon. Sci. A"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dry040"},{"key":"atypb24","first-page":"249","author":"Lent A.","year":"1976","journal-title":"Toronto"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0456"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/15M1014425"},{"key":"atypb27","unstructured":"M. W. Mahoney,\n                      Lecture Notes on Randomized Linear Algebra\n                      , preprint,https:\/\/arxiv.org\/abs\/1608.04481, 2016."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-038-x"},{"key":"atypb29","unstructured":"J. Nocedal,\n                      Optimization methods for training neural networks\n                      , in Proceedings of the 23rd International Symposium on Mathematical Programming, Bordeaux, France, 2018,https:\/\/ismp2018.sciencesconf.org\/data\/bookFullProgram.pdf."},{"key":"atypb30","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , 2nd ed., Springer, New York, 2006."},{"key":"atypb31","unstructured":"J. Nutini, B. Sepehry, I. Laradji, M. Schmidt, H. Koepke, and A. Virani,\n                      Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph\n                      , preprint,https:\/\/arxiv.org\/abs\/1612.07838, 2016."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/18M1179249"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20294"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2003,https:\/\/doi.org\/10.1137\/1.9780898718003.","DOI":"10.1137\/1.9780898718003"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111590"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"T. Wallace and A. Sekmen,\n                      Deterministic versus Randomized Kaczmarz Iterative Projection\n                      , preprint,https:\/\/arxiv.org\/abs\/1407.5593, 2014.","DOI":"10.1155\/2014\/908984"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3530"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.58"},{"key":"atypb41","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\/19M1259481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:56:09Z","timestamp":1787331369000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1259481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1259481"],"URL":"https:\/\/doi.org\/10.1137\/19m1259481","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}