{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:23:50Z","timestamp":1787336630482,"version":"3.56.0"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006192","name":"Office of Advanced Scientific Computing Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006192","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Department of Energy Computational Science Graduate Fellowship","award":["DE-SC0021110"],"award-info":[{"award-number":["DE-SC0021110"]}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2146"],"award-info":[{"award-number":["N00014-17-1-2146"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2363"],"award-info":[{"award-number":["N00014-18-1-2363"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF FRG","award":["1952777"],"award-info":[{"award-number":["1952777"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Randomized matrix algorithms have become workhorse tools in scientific computing and machine learning. To use these algorithms safely in applications, they should be coupled with posterior error estimates to assess the quality of the output. To meet this need, this paper proposes two diagnostics: a leave-one-out error estimator for randomized low-rank approximations and a jackknife resampling method to estimate the variance of the output of a randomized matrix computation. Both of these diagnostics are rapid to compute for randomized low-rank approximation algorithms such as the randomized SVD and randomized Nystr\u00f6m approximation, and they provide useful information that can be used to assess the quality of the computed output and guide algorithmic parameter choices.<\/jats:p>","DOI":"10.1137\/23m1558537","type":"journal-article","created":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T08:52:02Z","timestamp":1707382322000},"page":"A508-A528","source":"Crossref","is-referenced-by-count":8,"title":["Efficient Error and Variance Estimation for Randomized Matrix Computations"],"prefix":"10.1137","volume":"46","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0712-8296","authenticated-orcid":true,"given":"Ethan N.","family":"Epperly","sequence":"first","affiliation":[{"name":"Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1024-1791","authenticated-orcid":true,"given":"Joel A.","family":"Tropp","sequence":"additional","affiliation":[{"name":"Department 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,2,8]]},"reference":[{"key":"ref1","unstructured":"D. Arthur and S. Vassilvitskii, k-means++: The advantages of careful seeding, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2007, pp. 1027\u20131035."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/2842602"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970319"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345462"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/23M1548323"},{"key":"ref6","unstructured":"A. Gittens and M. Mahoney, Revisiting the Nystr\u00f6m method for improved large-scale machine learning, in Proceedings of the 30th International Conference on Machine Learning, PMLR, 2013, pp. 567\u2013575."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3004053"},{"key":"ref9","unstructured":"M. Lopes, N. B. Erichson, and M. Mahoney, Error estimation for sketched SVD via the bootstrap, in Proceedings of the 37th International Conference on Machine Learning, Proc. Mach. Learn. Res. 119, PMLR, 2020, pp. 6382\u20136392."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.3150\/22-BEJ1463"},{"key":"ref11","first-page":"39","volume":"20","author":"Lopes M. E.","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref13","unstructured":"R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Derezinski, M. E. Lopes, T. Liang, H. Luo, and J. Dongarra, Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software, http:\/\/arxiv.org\/abs\/2302.11474, 2023."},{"key":"ref14","unstructured":"C. Musco and C. Musco, Randomized block Krylov methods for stronger and faster approximate singular value decomposition, in Proceedings of the 28th International Conference on Neural Information Processing Systems, Vol. 1, MIT Press, Cambridge, MA, 2015, pp. 1396\u20131404."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1054"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-24273-2_1"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1949.tb00023.x"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1038\/sdata.2014.22"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1021\/ci300415d"},{"key":"ref20","volume-title":"Numerical Methods for Large Eigenvalue Problems","author":"Saad Y.","year":"1992"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349952"},{"key":"ref22","series-title":"Monogr. Statist. Appl. Probab. 57","volume-title":"An Introduction to the Bootstrap","author":"Tibshirani R. J.","year":"1993"},{"key":"ref23","unstructured":"J. A. Tropp and R. J. Webber, Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applictions, 2023, https:\/\/doi.org\/10.48550\/arXiv.2306.12418."},{"key":"ref24","first-page":"1225","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Tropp J. A.","year":"2017"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/18M1201068"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706647"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"ref28","unstructured":"C. K. I. Williams and M. Seeger, Using the Nystr\u00f6m method to speed up kernel machines, in Proceedings of the 13th International Conference on Neural Information Processing Systems, MIT Press, Cambridge, MA, 2000, pp. 661\u2013667."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"ref30","unstructured":"J. Yao, N. B. Erichson, and M. E. Lopes, Error estimation for random Fourier features, in Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res. 206, PMLR, 2023, pp. 2348\u20132364."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1558537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:24:34Z","timestamp":1787333074000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1558537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,8]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1137\/23M1558537"],"URL":"https:\/\/doi.org\/10.1137\/23m1558537","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,8]]}}}