Faster Stochastic Trace Estimation with a Chebyshev Product Identity
Methods for stochastic trace estimation often require the repeated evaluation of expressions of the form z^T p_n(A)z, where A is a symmetric matrix and p_n is a degree n polynomial written in the standard or Chebyshev basis. We show how to evaluate these expressions using only ⌈ n/2⌉ matrix-vector products, thus substantially reducing the cost of existing trace estimation algorithms that use Chebyshev interpolation or Taylor series.
READ FULL TEXT