On the variance of Schatten <i>p</i>-norm estimation with Gaussian sketching matrices

Abstract 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 in [W. Kong and G. Valiant, Spectrum estimation from samples, Ann. Statist. 45 2017, 5, 2218–2247] for the case of Gaussian random vectors and provide a sharper bound than previously available.