Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix

We analyze the convergence of randomized trace estimators. Starting at 1989, several algorithms have been proposed for estimating the trace of a matrix by 1/M∑i=1M ziT Azi, where the zi are random vectors; different estimators use different distributions for the zis, all of which lead to E(1/M∑i=1M ziT Azi) = trace(A). These algorithms are useful in applications in which there is no explicit representation of A but rather an efficient method compute zTAz given z. Existing results only analyze the variance of the different estimators. In contrast, we analyze the number of samples M required to guarantee that with probability at least 1−δ, the relative error in the estimate is at most &epsis;. We argue that such bounds are much more useful in applications than the variance. We found that these bounds rank the estimators differently than the variance; this suggests that minimum-variance estimators may not be the best. We also make two additional contributions to this area. The first is a specialized bound for projection matrices, whose trace (rank) needs to be computed in electronic structure calculations. The second is a new estimator that uses less randomness than all the existing estimators.