Analysis of probing techniques for sparse approximation and trace\n estimation of decaying matrix functions

The computation of matrix functions $f(A)$, or related quantities like their\ntrace, is an important but challenging task, in particular for large and sparse\nmatrices $A$. In recent years, probing methods have become an often considered\ntool in this context, as they allow to replace the computation of $f(A)$ or\n$\\text{tr}(f(A))$ by the evaluation of (a small number of) quantities of the\nform $f(A)v$ or $v^Tf(A)v$, respectively. These tasks can then efficiently be\nsolved by standard techniques like, e.g., Krylov subspace methods. It is\nwell-known that probing methods are particularly efficient when $f(A)$ is\napproximately sparse, e.g., when the entries of $f(A)$ show a strong\noff-diagonal decay, but a rigorous error analysis is lacking so far. In this\npaper we develop new theoretical results on the existence of sparse\napproximations for $f(A)$ and error bounds for probing methods based on graph\ncolorings. As a by-product, by carefully inspecting the proofs of these error\nbounds, we also gain new insights into when to stop the Krylov iteration used\nfor approximating $f(A)v$ or $v^Tf(A)v$, thus allowing for a practically\nefficient implementation of the probing methods.\n