2020/05/20 by Alice Cortinovis, Cortinovis, Alice, Daniel Kreßner +1 · 9 citations
Mathematics · #60E15 (Secondary) #65C05 (Primary) 65F40 #65F60 #68W20 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Random Matrices and Applications #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2005.10009
openalex publication_date 2020/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Randomized trace estimation is a popular and well studied technique that\napproximates the trace of a large-scale matrix B by computing the average of\nxT Bx for many samples of a random vector X. Often, B is symmetric\npositive definite (SPD) but a number of applications give rise to indefinite\nB. Most notably, this is the case for log-determinant estimation, a task that\nfeatures prominently in statistical learning, for instance in maximum\nlikelihood estimation for Gaussian process regression. The analysis of\nrandomized trace estimates, including tail bounds, has mostly focused on the\nSPD case. In this work, we derive new tail bounds for randomized trace\nestimates applied to indefinite B with Rademacher or Gaussian random vectors.\nThese bounds significantly improve existing results for indefinite B,\nreducing the the number of required samples by a factor n or even more, where\nn is the size of B. Even for an SPD matrix, our work improves an existing\nresult by Roosta-Khorasani and Ascher for Rademacher vectors. This work also\nanalyzes the combination of randomized trace estimates with the Lanczos method\nfor approximating the trace of f(A). Particular attention is paid to the\nmatrix logarithm, which is needed for log-determinant estimation. We improve\nand extend an existing result, to not only cover Rademacher but also Gaussian\nrandom vectors.\n