Matrix trace estimation is ubiquitous in machine learning applications and
has traditionally relied on Hutchinson's method, which requires
$O(\log(1/\delta)/\epsilon^2)$ matrix-vector product queries to achieve a $(1
\pm \epsilon)$-multiplicative approximation to $\text{tr}(A)$ with failure
probability $\delta$ on positive-semidefinite input matrices $A$. Recently, the
Hutch++ algorithm was proposed, which reduces the number of matrix-vector
queries from $O(1/\epsilon^2)$ to the optimal $O(1/\epsilon)$, and the
algorithm succeeds with constant probability. However, in the high probability
setting, the non-adaptive Hutch++ algorithm suffers an extra
$O(\sqrt{\log(1/\delta)})$ multiplicative factor in its query complexity.
Non-adaptive methods are important, as they correspond to sketching algorithms,
which are mergeable, highly parallelizable, and provide low-memory streaming
algorithms as well as low-communication distributed protocols. In this work, we
close the gap between non-adaptive and adaptive algorithms, showing that even
non-adaptive algorithms can achieve $O(\sqrt{\log(1/\delta)}/\epsilon +
\log(1/\delta))$ matrix-vector products. In addition, we prove matching lower
bounds demonstrating that, up to a $\log \log(1/\delta)$ factor, no further
improvement in the dependence on $\delta$ or $\epsilon$ is possible by any
non-adaptive algorithm. Finally, our experiments demonstrate the superior
performance of our sketch over the adaptive Hutch++ algorithm, which is less
parallelizable, as well as over the non-adaptive Hutchinson's method.

本文研究了矩阵迹估计的算法，提出了 Hutch++ 以及一种新的非自适应算法，通过实验证明了该算法的优越性。

迹的最优草图估计

Optimal Sketching for Trace Estimation

We examine the problem of estimating the trace of a matrix $A$ when given
access to an oracle which computes $x^\dagger A x$ for an input vector $x$. We
make use of the basis vectors from a set of mutually unbiased bases, widely
studied in the field of quantum information processing, in the selection of
probing vectors $x$. This approach offers a new state of the art single shot
sampling variance while requiring only $O(\log(n))$ random bits to generate
each vector. This significantly improves on traditional methods such as
Hutchinson's and Gaussian estimators in terms of the number of random bits
required and worst case sample variance.

使用互不偏基的基向量作为寻味向量，以估计矩阵迹，要求生成每个向量仅需 O (log (n)) 个随机比特，从而显著地提高了单次采样方差，同时也改进了传统方法。