{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:31Z","timestamp":1787336971946,"version":"3.56.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100006961","name":"California Institute of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006961","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"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-24-1-2223"],"award-info":[{"award-number":["N00014-24-1-2223"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"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":["1952777"],"award-info":[{"award-number":["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":[[2025,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Randomly pivoted Cholesky (RPCholesky) is an algorithm for constructing a low-rank approximation of a positive-semidefinite matrix using a small number of columns. This paper develops an accelerated version of RPCholesky that employs block matrix computations and rejection sampling to efficiently simulate the execution of the original algorithm. For the task of approximating a kernel matrix, the accelerated algorithm can run over [Formula: see text] faster. The paper contains implementation details, theoretical guarantees, experiments on benchmark data sets, and an application to computational chemistry.<\/jats:p>\n                  <jats:p>Reproducibility of computational results. This paper has been awarded the \u201cSIAM Reproducibility Badge: Code and data available\u201d as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https:\/\/github.com\/eepperly\/Randomly-Pivoted-Cholesky and in the supplementary materials ( github-repo.zip [82.9KB]). [Formula: see text]<\/jats:p>","DOI":"10.1137\/24m1699048","type":"journal-article","created":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T08:26:26Z","timestamp":1763367986000},"page":"2527-2557","source":"Crossref","is-referenced-by-count":1,"title":["Embrace Rejection: Kernel Matrix Approximation by Accelerated Randomly Pivoted Cholesky"],"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8286-6315","authenticated-orcid":true,"given":"Robert J.","family":"Webber","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,11,17]]},"reference":[{"key":"ref1","unstructured":"A. Alaoui and M. W. Mahoney, Fast randomized kernel ridge regression with statistical guarantees, in Proceedings of the 28th International Conference on Neural Information Processing Systems, 2015, https:\/\/dl.acm.org\/doi\/10.5555\/2969239.2969326."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1063\/5.0222798"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105396"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.22234"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-018-06169-2"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1126\/sciadv.1603015"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1126\/sciadv.adf0873"},{"key":"ref8","unstructured":"K. Cutajar, M. Osborne, J. Cunningham, and M. Filippone, Preconditioning kernel matrices, in Proceedings of the 33rd International Conference on Machine Learning, 2016, https:\/\/proceedings.mlr.press\/v48\/cutajar16.html."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a012"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"A. Deshpande and S. Vempala, Adaptive sampling and fast low-rank matrix approximation, in Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation, 2006, pp. 292\u2013303, https:\/\/doi.org\/10.1007\/11830924_28.","DOI":"10.1007\/11830924_28"},{"key":"ref11","unstructured":"M. D\u00edaz, E. N. Epperly, Z. Frangella, J. A. Tropp, and R. J. Webber, Robust, Randomized Preconditioning for Kernel Ridge Regression, preprint, 2024, https:\/\/arxiv.org\/abs\/2304.12465v4."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/24M1678027"},{"key":"ref13","volume-title":"Sourcebook of Parallel Computing","author":"Dongarra J.","year":"2003"},{"key":"ref14","first-page":"2153","volume":"6","author":"Drineas P.","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"E. N. Epperly and E. Moreno, Kernel quadrature with randomly pivoted Cholesky, in Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023, https:\/\/dl.acm.org\/doi\/10.5555\/3666122.3668997.","DOI":"10.52202\/075280-2875"},{"key":"ref16","first-page":"243","volume":"2","author":"Fine S.","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/21M1466244"},{"key":"ref18","unstructured":"J. Gardner, G. Pleiss, K. Q. Weinberger, D. Bindel, and A. G. Wilson, GPyTorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration, in Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, https:\/\/dl.acm.org\/doi\/10.5555\/3327757.3327857."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-005-0615-4"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198535645.003.0010"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"ref23","unstructured":"M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K. Sriperumbudur, Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences, preprint, 2018, https:\/\/arxiv.org\/abs\/1807.02582v1."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-76371-2"},{"key":"ref25","unstructured":"G. Meanti, L. Carratino, L. Rosasco, and A. Rudi, Kernel methods through the roof: Handling billions of points efficiently, in Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020, https:\/\/dl.acm.org\/doi\/abs\/10.5555\/3495724.3496932."},{"key":"ref26","unstructured":"R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Derezi\u0144ski, M. E. Lopes, T. Liang, H. Luo, and J. Dongarra, Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software, preprint, 2023, https:\/\/arxiv.org\/abs\/2302.11474v2."},{"key":"ref27","unstructured":"C. Musco and C. Musco, Recursive sampling for the Nystr\u00f6m method, in Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017, https:\/\/dl.acm.org\/doi\/10.5555\/3294996.3295140."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.68"},{"key":"ref29","unstructured":"A. Rezaei and S. O. Gharan, A polynomial time MCMC method for sampling from continuous determinantal point processes, in Proceedings of the 36th International Conference on Machine Learning, 2019, https:\/\/proceedings.mlr.press\/v97\/rezaei19a.html."},{"key":"ref30","unstructured":"A. Rudi, D. Calandriello, L. Carratino, and L. Rosasco, On fast leverage score sampling and optimal learning, in Proceedings of the 32nd International Conference on Neural Information Processing Systems, Vol. 31, 2018, https:\/\/dl.acm.org\/doi\/10.5555\/3327345.3327470."},{"key":"ref31","volume-title":"Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond","author":"Sch\u00f6lkopf B.","year":"2018"},{"key":"ref32","unstructured":"J. A. Tropp and R. J. Webber, Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, preprint, 2023, https:\/\/arxiv.org\/abs\/2306.12418v3."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.0c01111"},{"key":"ref34","unstructured":"K. Wang, G. Pleiss, J. Gardner, S. Tyree, K. Q. Weinberger, and A. G. Wilson, Exact Gaussian processes on a million data points, in Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019, https:\/\/dl.acm.org\/doi\/10.5555\/3454287.3455599."},{"key":"ref35","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, 2000, https:\/\/dl.acm.org\/doi\/10.5555\/3008751.3008847."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1099-7"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1699048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:38:49Z","timestamp":1787333929000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1699048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,17]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/24M1699048"],"URL":"https:\/\/doi.org\/10.1137\/24m1699048","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,17]]}}}