{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:00:11Z","timestamp":1776283211740,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Randomized trace estimation is a popular and well-studied technique that approximates the trace of a large-scale matrix<jats:italic>B<\/jats:italic>by computing the average of<jats:inline-formula><jats:alternatives><jats:tex-math>$$x^T Bx$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msup><mml:mi>x<\/mml:mi><mml:mi>T<\/mml:mi><\/mml:msup><mml:mi>B<\/mml:mi><mml:mi>x<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for many samples of a random vector<jats:italic>X<\/jats:italic>. Often,<jats:italic>B<\/jats:italic>is symmetric positive definite (SPD) but a number of applications give rise to indefinite<jats:italic>B<\/jats:italic>. Most notably, this is the case for log-determinant estimation, a task that features prominently in statistical learning, for instance in maximum likelihood estimation for Gaussian process regression. The analysis of randomized trace estimates, including tail bounds, has mostly focused on the SPD case. In this work, we derive new tail bounds for randomized trace estimates applied to indefinite<jats:italic>B<\/jats:italic>with Rademacher or Gaussian random vectors. These bounds significantly improve existing results for indefinite<jats:italic>B<\/jats:italic>, reducing the number of required samples by a factor<jats:italic>n<\/jats:italic>or even more, where<jats:italic>n<\/jats:italic>is the size of<jats:italic>B<\/jats:italic>. Even for an SPD matrix, our work improves an existing result by Roosta-Khorasani and Ascher (Found Comput Math, 15(5):1187\u20131212, 2015) for Rademacher vectors. This work also analyzes the combination of randomized trace estimates with the Lanczos method for approximating the trace of<jats:italic>f<\/jats:italic>(<jats:italic>B<\/jats:italic>). Particular attention is paid to the matrix logarithm, which is needed for log-determinant estimation. We improve and extend an existing result, to not only cover Rademacher but also Gaussian random vectors.<\/jats:p>","DOI":"10.1007\/s10208-021-09525-9","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T20:02:32Z","timestamp":1625860952000},"page":"875-903","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants"],"prefix":"10.1007","volume":"22","author":[{"given":"Alice","family":"Cortinovis","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Kressner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"9525_CR1","unstructured":"R.\u00a0Adamczak. The entropy method and concentration of measure in product spaces. Master\u2019s thesis, University of Warsaw and Vrije Universiteit van Amsterdam, 2003. Available at\u00a0http:\/\/duch.mimuw.edu.pl\/radamcz\/Old\/Papers\/master.pdf."},{"key":"9525_CR2","unstructured":"R.\u00a0H. Affandi, E.\u00a0Fox, R.\u00a0Adams, and B.\u00a0Taskar. Learning the parameters of determinantal point process kernels. In International Conference on Machine Learning, pages 1224\u20131232, 2014."},{"key":"9525_CR3","first-page":"10","volume":"10","author":"H Avron","year":"2010","unstructured":"H.\u00a0Avron. Counting triangles in large graphs using randomized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Applications, volume\u00a010, pages 10\u20139, 2010.","journal-title":"Workshop on Large-scale Data Mining: Theory and Applications"},{"key":"9525_CR4","doi-asserted-by":"crossref","unstructured":"H.\u00a0Avron and S.\u00a0Toledo. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM, 58(2):Art. 8, 17, 2011.","DOI":"10.1145\/1944345.1944349"},{"issue":"1\u20132","key":"9525_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0377-0427(96)00018-0","volume":"74","author":"Z Bai","year":"1996","unstructured":"Z.\u00a0Bai, M.\u00a0Fahey, and G.\u00a0Golub. Some large-scale matrix computation problems. J. Comput. Appl. Math., 74(1-2):71\u201389, 1996.","journal-title":"J. Comput. Appl. Math."},{"issue":"1\u20133","key":"9525_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0024-3795(97)10009-X","volume":"289","author":"RP Barry","year":"1999","unstructured":"R.\u00a0P. Barry and R.\u00a0K. Pace. Monte Carlo estimates of the log determinant of large sparse matrices. Linear Algebra Appl., 289(1-3):41\u201354, 1999.","journal-title":"Linear Algebra Appl."},{"key":"9525_CR7","doi-asserted-by":"crossref","unstructured":"R.\u00a0Bhatia, M.\u00a0D. Choi, and C.\u00a0Davis. Comparing a matrix to its off-diagonal part. In The Gohberg anniversary collection, Vol. I (Calgary, AB, 1988), volume\u00a040 of Oper. Theory Adv. Appl., pages 151\u2013164. Birkh\u00e4user, Basel, 1989.","DOI":"10.1007\/978-3-0348-9144-8_4"},{"issue":"3","key":"9525_CR8","doi-asserted-by":"publisher","first-page":"1583","DOI":"10.1214\/aop\/1055425791","volume":"31","author":"S Boucheron","year":"2003","unstructured":"S.\u00a0Boucheron, G.\u00a0Lugosi, and P.\u00a0Massart. Concentration inequalities using the entropy method. Ann. Probab., 31(3):1583\u20131614, 2003.","journal-title":"Ann. Probab."},{"key":"9525_CR9","doi-asserted-by":"crossref","unstructured":"S.\u00a0Boucheron, G.\u00a0Lugosi, and P.\u00a0Massart. Concentration inequalities. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"9525_CR10","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.laa.2017.07.004","volume":"533","author":"C Boutsidis","year":"2017","unstructured":"C.\u00a0Boutsidis, P.\u00a0Drineas, P.\u00a0Kambadur, E.-M. Kontopoulou, and A.\u00a0Zouzias. A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix. Linear Algebra Appl., 533:95\u2013117, 2017.","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"9525_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s10208-006-0196-8","volume":"7","author":"A Caponnetto","year":"2007","unstructured":"A.\u00a0Caponnetto and E.\u00a0De\u00a0Vito. Optimal rates for the regularized least-squares algorithm. Found. Comput. Math., 7(3):331\u2013368, 2007.","journal-title":"Found. Comput. Math."},{"issue":"2","key":"9525_CR12","doi-asserted-by":"publisher","first-page":"A577","DOI":"10.1137\/120874527","volume":"35","author":"J Chen","year":"2013","unstructured":"J.\u00a0Chen. On the use of discrete Laplace operator for preconditioning kernel matrices. SIAM J. Sci. Comput., 35(2):A577\u2013A602, 2013.","journal-title":"SIAM J. Sci. Comput."},{"issue":"6","key":"9525_CR13","doi-asserted-by":"publisher","first-page":"A3515","DOI":"10.1137\/15M1051506","volume":"38","author":"J Chen","year":"2016","unstructured":"J.\u00a0Chen. How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator? SIAM J. Sci. Comput., 38(6):A3515\u2013A3539, 2016.","journal-title":"SIAM J. Sci. Comput."},{"key":"9525_CR14","doi-asserted-by":"crossref","unstructured":"T.\u00a0A. Davis and Y.\u00a0Hu. The University of Florida sparse matrix collection. ACM Trans. Math. Software, 38(1):Art. 1, 25, 2011.","DOI":"10.1145\/2049662.2049663"},{"key":"9525_CR15","unstructured":"Distribution of difference of chi-squared variables. https:\/\/math.stackexchange.com\/questions\/85249\/distribution-of-difference-of-chi-squared-variables. Accessed: 06\/03\/2020."},{"issue":"4","key":"9525_CR16","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/18M1165979","volume":"49","author":"D Durfee","year":"2020","unstructured":"D.\u00a0Durfee, J.\u00a0Peebles, R.\u00a0Peng, and A.\u00a0B. Rao. Determinant-preserving sparsification of SDDM matrices. SIAM J. Comput., 49(4):350\u2013408, 2020.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9525_CR17","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1137\/15M1054389","volume":"46","author":"T Eden","year":"2017","unstructured":"T.\u00a0Eden, A.\u00a0Levi, D.\u00a0Ron, and C.\u00a0Seshadhri. Approximately counting triangles in sublinear time. SIAM J. Comput., 46(5):1603\u20131646, 2017.","journal-title":"SIAM J. Comput."},{"key":"9525_CR18","doi-asserted-by":"crossref","unstructured":"J.\u00a0Fitzsimons, D.\u00a0Granziol, K.\u00a0Cutajar, M.\u00a0Osborne, M.\u00a0Filippone, and S.\u00a0Roberts. Entropic trace estimates for log determinants. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 323\u2013338. Springer, 2017.","DOI":"10.1007\/978-3-319-71249-9_20"},{"key":"9525_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7","volume-title":"A mathematical introduction to compressive sensing","author":"S Foucart","year":"2013","unstructured":"S.\u00a0Foucart and H.\u00a0Rauhut. A mathematical introduction to compressive sensing. Applied and Numerical Harmonic Analysis. Birkh\u00e4user\/Springer, New York, 2013."},{"key":"9525_CR20","unstructured":"J.\u00a0R. Gardner, G.\u00a0Pleiss, D.\u00a0Bindel, K.\u00a0Q. Weinberger, and A.\u00a0G. Wilson. GPyTorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration. In Advances in Neural Information Processing Systems, volume 2018-December, pages 7576\u20137586, 2018."},{"key":"9525_CR21","volume-title":"Matrices, moments and quadrature with applications","author":"GH Golub","year":"2010","unstructured":"G.\u00a0H. Golub and G.\u00a0Meurant. Matrices, moments and quadrature with applications. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2010."},{"issue":"2","key":"9525_CR22","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1137\/17M1137541","volume":"39","author":"S Gratton","year":"2018","unstructured":"S.\u00a0Gratton and D.\u00a0Titley-Peloquin. Improved bounds for small-sample estimation. SIAM J. Matrix Anal. Appl., 39(2):922\u2013931, 2018.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9525_CR23","doi-asserted-by":"crossref","unstructured":"S.\u00a0G\u00fcttel, D.\u00a0Kressner, and K.\u00a0Lund. Limited-memory polynomial methods for large-scale matrix functions. GAMM-Mitt., 43(3):e202000019, 19, 2020.","DOI":"10.1002\/gamm.202000019"},{"issue":"4","key":"9525_CR24","doi-asserted-by":"publisher","first-page":"A1558","DOI":"10.1137\/16M1078148","volume":"39","author":"I Han","year":"2017","unstructured":"I.\u00a0Han, D.\u00a0Malioutov, H.\u00a0Avron, and J.\u00a0Shin. Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations. SIAM J. Sci. Comput., 39(4):A1558\u2013A1585, 2017.","journal-title":"SIAM J. Sci. Comput."},{"key":"9525_CR25","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1214\/aoms\/1177693335","volume":"42","author":"DL Hanson","year":"1971","unstructured":"D.\u00a0L. Hanson and F.\u00a0T. Wright. A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist., 42:1079\u20131083, 1971.","journal-title":"Ann. Math. Statist."},{"key":"9525_CR26","unstructured":"T.\u00a0Hunter, A.\u00a0E. Alaoui, and A.\u00a0M. Bayen. Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time. CoRR, abs\/1408.1693, 2014."},{"issue":"3","key":"9525_CR27","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1080\/03610918908812806","volume":"18","author":"MF Hutchinson","year":"1989","unstructured":"M.\u00a0F. Hutchinson. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Comm. Statist. Simulation Comput., 18(3):1059\u20131076, 1989.","journal-title":"Comm. Statist. Simulation Comput."},{"issue":"3","key":"9525_CR28","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1137\/100810447","volume":"43","author":"F Krahmer","year":"2011","unstructured":"F.\u00a0Krahmer and R.\u00a0Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal., 43(3):1269\u20131281, 2011.","journal-title":"SIAM J. Math. Anal."},{"issue":"5","key":"9525_CR29","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1214\/aos\/1015957395","volume":"28","author":"B Laurent","year":"2000","unstructured":"B.\u00a0Laurent and P.\u00a0Massart. Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5):1302\u20131338, 2000.","journal-title":"Ann. Statist."},{"key":"9525_CR30","unstructured":"H.\u00a0Li and Y.\u00a0Zhu. Randomized block Krylov space methods for trace and log-determinant estimators. arXiv preprintarXiv:2003.00212, 2020."},{"issue":"1","key":"9525_CR31","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1137\/130934283","volume":"58","author":"L Lin","year":"2016","unstructured":"L.\u00a0Lin, Y.\u00a0Saad, and C.\u00a0Yang. Approximating spectral densities of large matrices. SIAM Rev., 58(1):34\u201365, 2016.","journal-title":"SIAM Rev."},{"key":"9525_CR32","doi-asserted-by":"crossref","unstructured":"R.\u00a0A. Meyer, C.\u00a0Musco, C.\u00a0Musco, and D.\u00a0P. Woodruff. Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity in Algorithms (SOSA), pages 142\u2013155. SIAM, 2021.","DOI":"10.1137\/1.9781611976496.16"},{"key":"9525_CR33","unstructured":"M.\u00a0Neteler and H.\u00a0Mitasova. Open source GIS: a GRASS GIS approach, volume 689. Springer Science & Business Media, 2013."},{"issue":"2","key":"9525_CR34","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0167-9473(02)00321-3","volume":"45","author":"RK Pace","year":"2004","unstructured":"R.\u00a0K. Pace and J.\u00a0P. LeSage. Chebyshev approximation of log-determinants of spatial weight matrices. Comput. Statist. Data Anal., 45(2):179\u2013196, 2004.","journal-title":"Comput. Statist. Data Anal."},{"issue":"4","key":"9525_CR35","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1016\/j.camwa.2017.11.001","volume":"75","author":"W Peng","year":"2018","unstructured":"W.\u00a0Peng and H.\u00a0Wang. A general scheme for log-determinant computation of matrices via stochastic polynomial approximation. Comput. Math. Appl., 75(4):1259\u20131271, 2018.","journal-title":"Comput. Math. Appl."},{"issue":"5","key":"9525_CR36","doi-asserted-by":"publisher","first-page":"1187","DOI":"10.1007\/s10208-014-9220-1","volume":"15","author":"F Roosta-Khorasani","year":"2015","unstructured":"F.\u00a0Roosta-Khorasani and U.\u00a0Ascher. Improved bounds on sample size for implicit matrix trace estimators. Found. Comput. Math., 15(5):1187\u20131212, 2015.","journal-title":"Found. Comput. Math."},{"issue":"2","key":"9525_CR37","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00211-017-0880-z","volume":"137","author":"AK Saibaba","year":"2017","unstructured":"A.\u00a0K. Saibaba, A.\u00a0Alexanderian, and I.\u00a0C.\u00a0F. Ipsen. Randomized matrix-free trace and log-determinant estimators. Numer. Math., 137(2):353\u2013395, 2017.","journal-title":"Numer. Math."},{"issue":"3","key":"9525_CR38","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s002220050108","volume":"126","author":"M Talagrand","year":"1996","unstructured":"M.\u00a0Talagrand. New concentration inequalities in product spaces. Invent. Math., 126(3):505\u2013563, 1996.","journal-title":"Invent. Math."},{"issue":"3","key":"9525_CR39","doi-asserted-by":"publisher","first-page":"1642","DOI":"10.1103\/PhysRevD.57.1642","volume":"57","author":"C Thron","year":"1998","unstructured":"C.\u00a0Thron, S.\u00a0J. Dong, K.\u00a0F. Liu, and H.\u00a0P. Ying. Pad\u00e9-$$Z_2$$ estimator of determinants. Physical Review D - Particles, Fields, Gravitation and Cosmology, 57(3):1642\u20131653, 1998.","journal-title":"Physical Review D - Particles, Fields, Gravitation and Cosmology"},{"issue":"4","key":"9525_CR40","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/16M1104974","volume":"38","author":"S Ubaru","year":"2017","unstructured":"S.\u00a0Ubaru, J.\u00a0Chen, and Y.\u00a0Saad. Fast estimation of $$\\text{ tr }(f(A))$$ via stochastic Lanczos quadrature. SIAM J. Matrix Anal. Appl., 38(4):1075\u20131099, 2017.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9525_CR41","unstructured":"Upper limit on the central binomial coefficient. https:\/\/mathoverflow.net\/questions\/133732\/upper-limit-on-the-central-binomial-coefficient. Accessed: 23\/03\/2020."},{"key":"9525_CR42","unstructured":"M.\u00a0J. Wainwright. High-dimensional statistics, volume\u00a048 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2019. A non-asymptotic viewpoint."},{"issue":"6","key":"9525_CR43","doi-asserted-by":"publisher","first-page":"2099","DOI":"10.1109\/TSP.2006.874409","volume":"54","author":"MJ Wainwright","year":"2006","unstructured":"M.\u00a0J. Wainwright and M.\u00a0I. Jordan. Log-determinant relaxation for approximate inference in discrete Markov random fields. IEEE Trans. Signal Process., 54(6):2099\u20132109, 2006.","journal-title":"IEEE Trans. Signal Process."},{"key":"9525_CR44","doi-asserted-by":"crossref","unstructured":"K.\u00a0Wimmer, Y.\u00a0Wu, and P.\u00a0Zhang. Optimal query complexity for estimating the trace of a matrix. In International Colloquium on Automata, Languages, and Programming, pages 1051\u20131062. Springer, 2014.","DOI":"10.1007\/978-3-662-43948-7_87"},{"issue":"3\u20134","key":"9525_CR45","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1080\/10629360600569279","volume":"77","author":"Y Zhang","year":"2007","unstructured":"Y.\u00a0Zhang and W.\u00a0E. Leithead. Approximate implementation of the logarithm of the matrix determinant in Gaussian process regression. J. Stat. Comput. Simul., 77(3-4):329\u2013348, 2007.","journal-title":"J. Stat. Comput. Simul."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09525-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09525-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09525-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T21:44:24Z","timestamp":1699220664000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09525-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9525"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09525-9","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,9]]},"assertion":[{"value":"20 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}