论文标题
Hutch ++：最佳随机痕量估计
Hutch++: Optimal Stochastic Trace Estimation
论文作者
论文摘要
我们研究了估计只能通过矩阵矢量乘法访问的矩阵$ a $痕迹的问题。我们引入了一种新的随机算法，Hutch ++，该算法将$（1 \ pmε）$近似值计算为$ tr（a）$，对于任何正面的半finite（psd）$ a $，仅使用$ o（1/ε）$ matrix-vector产品。这改善了无处不在的Hutchinson的估计器，该估计量需要$ O（1/ε^2）$矩阵矢量产品。我们的方法基于一种简单的技术，用于使用低级别近似步骤来减少Hutchinson估计器的差异，并且易于实现和分析。此外，我们证明，在对数因素上，即使可以适应性地选择查询，也可以在所有矩阵 - 矢量查询算法中最佳的Hutch ++的复杂性。我们表明，它在实验中的表现明显优于Hutchinson的方法。虽然我们的理论主要需要$ a $才能成为积极的半决赛，但我们为通用方形矩阵提供了广义的保证，并在此类应用中显示了经验增长。
We study the problem of estimating the trace of a matrix $A$ that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a $(1 \pm ε)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$ using just $O(1/ε)$ matrix-vector products. This improves on the ubiquitous Hutchinson's estimator, which requires $O(1/ε^2)$ matrix-vector products. Our approach is based on a simple technique for reducing the variance of Hutchinson's estimator using a low-rank approximation step, and is easy to implement and analyze. Moreover, we prove that, up to a logarithmic factor, the complexity of Hutch++ is optimal amongst all matrix-vector query algorithms, even when queries can be chosen adaptively. We show that it significantly outperforms Hutchinson's method in experiments. While our theory mainly requires $A$ to be positive semidefinite, we provide generalized guarantees for general square matrices, and show empirical gains in such applications.
