Analysis of probing techniques for sparse approximation and trace estimation of decaying matrix functions
share
The computation of matrix functions f(A), or related quantities like their trace, is an important but challenging task, in particular for large and sparse matrices A. In recent years, probing methods have become an often considered f(A) or tr(f(A)) by the evaluation of (a small number of) quantities of the form f(A)v or v^Tf(A)v, respectively. These tasks can then efficiently be solved by standard techniques like, e.g., Krylov subspace methods. It is well-known that probing methods are particularly efficient when f(A) is approximately sparse, e.g., when the entries of f(A) show a strong off-diagonal decay, but a rigorous error analysis is lacking so far. In this paper we develop new theoretical results on the existence of sparse approximations for f(A) and error bounds for probing methods based on graph colorings. As a by-product, by carefully inspecting the proofs of these error bounds, we also gain new insights into when to stop the Krylov iteration used for approximating f(A)v or v^Tf(A)v, thus allowing for a practically efficient implementation of the probing methods.
READ FULL TEXT