Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation

Raphael A. Meyer, Haim Avron

We study the problem of estimating the trace of a matrix $\mathbf{A}$ that can only be accessed through Kronecker-matrix-vector products. That is, for any Kronecker-structured vect…