论文标题
关于无限矩阵的随机痕量估计，并应用了决定因素
On randomized trace estimates for indefinite matrices with an application to determinants
论文作者
论文摘要
随机跟踪估计是一种流行且研究良好的技术，它通过计算许多随机矢量$ x $的样品的平均值，近似于大规模矩阵$ b $的跟踪。通常，$ b $是对称的正定确定性（SPD），但许多应用程序会导致无限期的$ b $。最值得注意的是，对数确定估计是这种情况，这是在统计学习中突出特征的任务，例如，高斯过程回归的最大似然估计。包括尾巴界限在内的随机痕量估计值的分析主要集中在SPD情况下。在这项工作中，我们为与Rademacher或Gaussian随机向量应用于无限$ b $的随机痕量估计的新尾部边界。这些界限显着改善了无限$ b $的现有结果，将所需样本的数量减少了一个因子$ n $甚至更多，其中$ n $的大小为$ b $。即使对于SPD矩阵，我们的工作也改善了Roosta-Khorasani和Ascher的Rademacher载体的现有结果。这项工作还分析了随机痕量估计与兰开斯方法的组合，用于近似于$ f（a）$。特别注意矩阵对数，这是对数确定估计所需的。我们改善并扩展了现有结果，不仅涵盖了Rademacher，还涵盖了高斯随机向量。
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 the number of required samples by a factor $n$ or even more, where $n$ is the size of $B$. Even for an SPD matrix, our work improves an existing result by Roosta-Khorasani and Ascher for Rademacher vectors. This work also analyzes the combination of randomized trace estimates with the Lanczos method for approximating the trace of $f(A)$. 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.
