期刊
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
卷 22, 期 3, 页码 875-903出版社
SPRINGER
DOI: 10.1007/s10208-021-09525-9
关键词
Trace estimation; Determinant; Tail bounds; Entropy method; Lanczos method
资金
- SNSF Research Project Fast algorithms from low-rank updates [200020_178806]
- Swiss National Science Foundation (SNF) [200020_178806] Funding Source: Swiss National Science Foundation (SNF)
This work presents new tail bounds for the randomized trace estimates applied to indefinite B with Rademacher or Gaussian random vectors, significantly improving existing results and reducing the required number of samples. Additionally, the combination of randomized trace estimates with the Lanczos method for approximating the trace of f(B) is analyzed, with a particular focus on the importance of the matrix logarithm.
Randomized trace estimation is a popular and well-studied technique that approximates the trace of a large-scale matrix B by computing the average of x(T) Bx for many samples of a random vector X. Often, B is symmetric positive definite (SPD) but a number of applications give rise to indefinite B. 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 B with Rademacher or Gaussian random vectors. These bounds significantly improve existing results for indefinite B, reducing the number of required samples by a factor n or even more, where n is the size of B. Even for an SPD matrix, ourwork improves an existing result by Roosta-Khorasani and Ascher (Found Comput Math, 15(5):1187-1212, 2015) for Rademacher vectors. This work also analyzes the combination of randomized trace estimates with the Lanczos method for approximating the trace of f(B). 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据