Hutch++: Optimal Stochastic Trace Estimation.
Hutch++: Optimal Stochastic Trace Estimation.
复制标题
DOI：
10.1137/1.9781611976496.16
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Woodruff DP
中科院分区：
文献类型：
--
作者：
Meyer RA;Musco C;Musco C;Woodruff DP
我们研究了矩阵A的迹估计问题，该问题只能通过矩阵-向量乘法来获得。介绍了一种新的随机化算法Hutch++，该算法仅用O(1/ε)个矩阵向量积即可计算出任意半正定(PsD)A的(1±ε)个tr(A)逼近.这改进了普遍存在的Hutchinson估计，它需要O(1/ε2)个矩阵向量乘积。我们的方法基于一种简单的技术，可以使用低阶近似步骤来降低Hutchinson估计的方差，并且易于实现和分析。此外，我们证明了当查询可以自适应地选择时，Hutch++算法的复杂度在所有矩阵-向量查询算法中是最优的，直到对数倍。实验表明，该方法的性能明显优于Hutchinson的方法。虽然我们的理论要求A是半正定的，但经验收益扩展到了涉及非PSD矩阵的应用，例如网络中的三角估计。
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 ± ε) 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 requires A to be positive semidefinite, empirical gains extend to applications involving non-PSD matrices, such as triangle estimation in networks.
登录
查看更多内容
影响因子：
1.6
作者：
Chakrabarti, Amit;Regev, Oded
通讯作者：
Regev, Oded
影响因子：
1.1
作者：
Achlioptas, D
通讯作者：
Achlioptas, D
影响因子：
2
作者：
Cai T;Ma Z;Wu Y
通讯作者：
Wu Y
DOI：
10.1080/03610919008812866
发表时间：
1990-01-01
影响因子：
0.9
作者：
HUTCHINSON, MF
通讯作者：
HUTCHINSON, MF
影响因子：
1.1
作者：
de la Pena, Jose Antonio;Gutman, Ivan;Rada, Juan
通讯作者：
Rada, Juan