R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications
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.
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications
Nimrod Megiddo
Journal of Symbolic Computation
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ