{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:24:06Z","timestamp":1787333046563,"version":"3.56.0"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"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":["BRC Award N00014-18-1-2363"],"award-info":[{"award-number":["BRC Award N00014-18-1-2363"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"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\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FRG Award 1952777"],"award-info":[{"award-number":["FRG Award 1952777"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000015","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,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTrace and XNysTrace, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard\u2013Hutchinson estimator or the Hutch++ estimator.\u00a0A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs.<\/jats:p>","DOI":"10.1137\/23m1548323","type":"journal-article","created":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T04:02:57Z","timestamp":1704254577000},"page":"1-23","source":"Crossref","is-referenced-by-count":28,"title":["XT\n                    <scp>race<\/scp>\n                    : Making the Most of Every Sample in Stochastic Trace Estimation"],"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1024-1791","authenticated-orcid":true,"given":"Joel A.","family":"Tropp","sequence":"additional","affiliation":[{"name":"Division 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":"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,1,3]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1226"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/100788860"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"ref4","unstructured":"R. A. Baston  and \nY. Nakatsukasa  , Stochastic Diagonal Estimation: Probabilistic Bounds and an Improved Algorithm, preprint, arXiv:2201.10684, 2022."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2007.01.003"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg340"},{"key":"ref7","unstructured":"T. Chen  and \nE. Hallman  , Krylov-aware Stochastic Trace Estimation, preprint, arXiv:2205.01736, 2022."},{"key":"ref8","unstructured":"T. Chen , \nT. Trogdon , and \nS. Uba ru  , Randomized Matrix-Free Quadrature for Spectrum and Spectral Sum Approximation, preprint, arXiv:2204.01941, 2022."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"ref10","unstructured":"E. N. Epperly  and \nJ. A. Tropp  , Efficient Error and Variance Estimation for Randomized Matrix Computations, preprint, arXiv:2207.06342, 2023."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s40324-021-00275-w"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/16M1066361"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"A. C. Gilbert , \nM. J. Strauss , \nJ. A. Tropp , and \nR. Vershynin  , One sketch for all: Fast algorithms for compressed sensing, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 237\u2013246, https:\/\/doi.org\/10.1145\/1250790.1250824.","DOI":"10.1145\/1250790.1250824"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01395775"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731020"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717778"},{"key":"ref18","unstructured":"N. J. Higham  , Matrix Exponential Times a Vector, https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/29576-matrix-exponential-times-a-vector, 2010."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"ref20","unstructured":"S. Jiang , \nH. Pham , \nD. P. Woodruff , and \nQ. Zhang  , Optimal sketching for trace estimation, in 35th Conference on Neural Information Processing Systems 2021, p. 13."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-3515-5"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/3004053"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-016-0837-7"},{"key":"ref24","unstructured":"C. Litens  , Transverse Field Ising Model with Different Boundary Conditions, bachelor\u2019s thesis, Stockholm University, 2019, https:\/\/staff.fysik.su.se\/\u223cardonne\/files\/theses\/bachelor-thesis_christopher-litens.pdf."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"R. A. Meyer , \nC. Musco , \nC. Musco , and \nD. P. Woodruff  , Hutch++: Optimal stochastic trace estimation, in Symposium on Simplicity in Algorithms, SIAM, Philadelphia, 2021.","DOI":"10.1137\/1.9781611976496.16"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"R. A. Meyer , \nC. Musco , \nC. Musco , and \nD. P. Woodruff  , Hutch++: Optimal Stochastic Trace Estimation, preprint, https:\/\/arxiv.org\/abs\/2010.09649v5, 2021.","DOI":"10.1137\/1.9781611976496.16"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/21M1447623"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4916(70)90270-8"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0804869105"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-017-0880-z"},{"key":"ref32","unstructured":"J. A. Tropp  and \nR. J. Webber  , Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, preprint, https:\/\/arxiv.org\/abs\/2306.12418v3, 2023."},{"key":"ref33","first-page":"1225","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Tropp J. A.","year":"2017"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104974"},{"key":"ref35","first-page":"19","volume-title":"High Performance Computing in Science and Engineering","author":"Ubaru S.","year":"2017"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1548323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:28:06Z","timestamp":1787329686000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1548323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,3]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/23M1548323"],"URL":"https:\/\/doi.org\/10.1137\/23m1548323","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,3]]}}}