{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:26:26Z","timestamp":1787329586602,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2123224"],"award-info":[{"award-number":["DMS-2123224"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Let [Formula: see text] be invertible, [Formula: see text] unknown, and [Formula: see text] given. We are interested in approximate solutions: vectors [Formula: see text] such that [Formula: see text] is small. We prove that for all [Formula: see text], there is a composition of [Formula: see text] orthogonal projections onto the [Formula: see text] hyperplanes generated by the rows of [Formula: see text], where [Formula: see text], which maps the origin to a vector [Formula: see text] satisfying [Formula: see text]. We note that this upper bound on [Formula: see text] is independent of the matrix [Formula: see text]. This procedure is stable in the sense that [Formula: see text]. The existence proof is based on a probabilistically refined analysis of the randomized Kaczmarz method, which seems to achieve this rate when solving for [Formula: see text] with high likelihood. We also prove a general version for matrices [Formula: see text] with [Formula: see text] and full rank.<\/jats:p>","DOI":"10.1137\/22m1517196","type":"journal-article","created":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T10:24:57Z","timestamp":1695723897000},"page":"1436-1446","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Solutions of Linear Systems at a Universal Rate"],"prefix":"10.1137","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7745-4217","authenticated-orcid":true,"given":"Stefan","family":"Steinerberger","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Washington, Seattle, WA 98195 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,9,25]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-037-2"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1137747"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2018.05.009"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"C. Cenker , \nH. G. Feichtinger , \nM. Mayer , \nH. Steier , and \nT. Strohmer , New variants of the POCS method using affine subspaces of finite codimension, with applications to irregular sampling, in Proceedings of SPIE: Visual Communications and Image Processing, International Society for Optics and Photonics, Bellingham, WA, 1992, pp. 299\u2013310.","DOI":"10.1117\/12.131447"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2004.12.050"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025487"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/19M1285846"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/19M1307044"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/18M1179213"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-018-0737-6"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/21M1429187"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6420\/aa8e82"},{"key":"ref13","first-page":"355","volume":"35","author":"Kaczmarz S.","year":"1937","journal-title":"Bull. Int. Acad. Polonaise Sci. Lett."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0456"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.4208\/nmtma.OA-2018-0066"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/15M1014425"},{"key":"ref17","unstructured":"N. Marshall  and \nO. Mickelin , An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm, preprint, arXiv:2202.12224, 2022."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-038-x"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-010-0265-5"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.12.022"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-012-9248-z"},{"key":"ref22","first-page":"1017","volume-title":"Advances in Neural Information Processing Systems","author":"Needell D."},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2015.06.027"},{"key":"ref24","unstructured":"J. Nutini , \nB. Sepehry , \nI. Laradji , \nM. Schmidt , \nH. Koepke , and \nA. Virani , Convergence rates for greedy Kaczmarz algorithms, and faster randomized Kaczmarz rules using the orthogonality graph, in Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, Association for Computing Machinery, New York, 2016."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/20M1350947"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3644"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1553\/etna_vol54s610"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/1587"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaab029"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"ref31","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\/22M1517196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:24:00Z","timestamp":1787325840000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1517196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,25]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1137\/22M1517196"],"URL":"https:\/\/doi.org\/10.1137\/22m1517196","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,25]]}}}