Decay bounds for functions of hermitian matrices with banded or kronecker structure

We present decay bounds for completely monotonic functions of Hermitian matrices, where the matrix argument is banded or a Kronecker sum of banded matrices. This class includes the exponential, the negative fractional roots, and other functions that are important in applications. Besides being significantly tighter than previous estimates, the new bounds closely capture the actual (nonmonotonic) decay behavior of the entries of functions of matrices with Kronecker sum structure. We also discuss extensions to more general sparse matrices.