Meyer Raphael A, Musco Cameron, Musco Christopher, Woodruff David P
New York University.
UMass Amherst.
Proc SIAM Symp Simplicity Algorithms. 2021 Jan;2021:142-155. doi: 10.1137/1.9781611976496.16.
We study the problem of estimating the trace of a matrix that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a (1 ± ) approximation to tr( ) for any positive semidefinite (PSD) using just (1) matrix-vector products. This improves on the ubiquitous , which requires (1 ) 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 requires to be positive semidefinite, empirical gains extend to applications involving non-PSD matrices, such as triangle estimation in networks.
我们研究了只能通过矩阵向量乘法访问的矩阵迹估计问题。我们引入了一种新的随机算法Hutch++，对于任何正定（PSD）矩阵，它仅使用(1)次矩阵向量乘积就能计算出tr( )的(1 ± )近似值。这改进了普遍使用的算法，后者需要(1 )次矩阵向量乘积。我们的方法基于一种简单的技术，即使用低秩近似步骤来降低哈钦森估计器的方差，并且易于实现和分析。此外，我们证明，即使查询可以自适应选择，在所有矩阵向量查询算法中，Hutch++的复杂度在对数因子范围内是最优的。我们表明，在实验中它明显优于哈钦森方法。虽然我们的理论要求矩阵为正定，但经验上的优势扩展到了涉及非正定矩阵的应用中，例如网络中的三角形估计。
