Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Monte Carlo matrix trace estimation is a popular randomized technique to estimate the trace of implicitly-defined matrices via averaging quadratic forms across several observations of a random vector. The most common approach to analyze the quality of such estimators is to consider the variance over the total number of observations. In this paper we present a procedure to compute the variance of the estimator proposed by Kong and Valiant [Ann. Statist. 45 (5), pp. 2218 - 2247] for the case of Gaussian random vectors and provide a sharper bound than previously available.
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering