{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:35:13Z","timestamp":1787330113618,"version":"3.56.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Carver Mead New Horizons Fund"},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["DE-SC0021110"],"award-info":[{"award-number":["DE-SC0021110"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FRG 1952777"],"award-info":[{"award-number":["FRG 1952777"]}],"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":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these algorithms produce high-accuracy solutions to least-squares problems faster than standard direct methods based on QR factorization. Recently, Meier et al. demonstrated numerical instabilities in a version of sketch-and-precondition in floating point arithmetic. The work of Meier et\u00a0al. raises the question, is there a randomized least-squares solver that is both fast and stable? This paper resolves this question in the affirmative by proving that iterative sketching, appropriately implemented, is forward stable. Numerical experiments confirm the theoretical findings, demonstrating that iterative sketching is stable and faster than QR -based solvers for large problem instances.<\/jats:p>","DOI":"10.1137\/23m1616790","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T04:33:27Z","timestamp":1728275607000},"page":"1782-1804","source":"Crossref","is-referenced-by-count":9,"title":["Fast and Forward Stable Randomized Algorithms for Linear Least-Squares Problems"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0712-8296","authenticated-orcid":true,"given":"Ethan N.","family":"Epperly","sequence":"first","affiliation":[{"name":"Division of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5308"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90101-7"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484"},{"key":"ref6","unstructured":"Y. Cho, J. W. Demmel, M. Derezi\u0144ski, H. Li, H. Luo, M. W. Mahoney, and R. J. Murray, Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems, preprint, https:\/\/arxiv.org\/abs\/2308.15720v1, 2023."},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"M. B. Cohen, Nearly tight oblivious subspace embeddings by trace inequalities, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 278\u2013287, https:\/\/doi.org\/10.1137\/1.9781611974331.ch21.","DOI":"10.1137\/1.9781611974331.ch21"},{"key":"ref8","unstructured":"M. D\u00edaz, E. N. Epperly, Z. Frangella, J. A. Tropp, and R. J. Webber, Robust, Randomized Preconditioning for Kernel Ridge Regression, preprint, https:\/\/arxiv.org\/abs\/2304.12465v4, 2023."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-023-10061-z"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"ref12","unstructured":"A. Kireeva and J. A. Tropp, Randomized Matrix Computations: Themes and Variations, CIME Summer School on Machine Learning, Cetraro, Italy, 2023, https:\/\/doi.org\/10.7907\/7yade-5k351."},{"key":"ref13","unstructured":"J. Lacotte and M. Pilanci, Faster Least Squares Optimization, preprint, https:\/\/arxiv.org\/abs\/1911.02675v3, 2021."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/23M1551973"},{"key":"ref16","unstructured":"R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, M. Derezi\u0144ski, M. E. Lopes, T. Liang, and H. Luo, Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software, preprint, https:\/\/arxiv.org\/abs\/2302.11474v2, 2022."},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"I. K. Ozaslan, M. Pilanci, and O. Arikan, Iterative Hessian sketch with momentum, in 2019 IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, Piscataway, NJ, 2019, pp. 7470\u20137474, https:\/\/doi.org\/10.1109\/ICASSP.2019.8682720.","DOI":"10.1109\/ICASSP.2019.8682720"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"ref19","first-page":"1842","volume":"17","author":"Pilanci M.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0804869105"},{"key":"ref21","first-page":"3891","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Rudi A.","year":"2017"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"ref23","first-page":"598","volume-title":"Advances in Neural Information Processing Systems","volume":"13","author":"Smola A. J.","year":"2000"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/18M1201068"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933494"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1616790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:47:56Z","timestamp":1787327276000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1616790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/23M1616790"],"URL":"https:\/\/doi.org\/10.1137\/23m1616790","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]}}}