Speaker
Description
We consider the problem of estimating the trace of a matrix function $f(A)$. In certain situations, in particular if $f(A)$ cannot be well approximated by a low-rank matrix, combining probing methods [2] based on graph colorings with stochastic trace estimation techniques can yield very accurate approximations. So far, such methods have not been thoroughly analyzed, though, but were rather used as efficient heuristics by practitioners [1]. We perform a detailed analysis of stochastic probing methods and, in particular, expose conditions under which the expected approximation error in the stochastic probing method scales more favorably with the dimension of the matrix than the error in non-stochastic probing. Extending previous heuristic results [1], we also characterize situations in which using just one stochastic vector is always better than the deterministic probing method. Several numerical experiments illustrate our theory and compare with existing methods.
[1] E. Aune, D. P. Simpson, and J. Eidsvik. Parameter estimation in high dimensional Gaussian distributions. Stat. Comput., 24:247–263, 2014.
[2] A. Frommer, C. Schimmel, and M. Schweitzer. Analysis of probing techniques for sparse approximation and trace estimation of decaying matrix functions. SIAM J. Matrix Anal. Appl., 42(3):1290–1318, 2021.
