Accelerating Matrix Trace Estimation by Aitken’s Δ² Process

Abstract

We present an algorithm to estimate the trace of symmetric matrices that are available only via Matrix-Vector multiplication. The proposed algorithm constructs a series of trace estimates by applying the probing technique with an increasing number of vectors. These estimates are then treated as a converging sequence whose limit is the sought matrix trace, and we apply Aitken's $\Delta^2$ process to accelerate its convergence to the trace limit. Numerical experiments performed on covariance matrices demonstrate the competitiveness of the proposed scheme versus probing and randomized trace estimators.