Approximating sparse matrices and their functions using matrix-vector products

The computation of a matrix function f(A) is an important task in scientific computing appearing in machine learning, network analysis and the solution of partial differential equations. In this work, we use only matrix-vector products x↦Ax to approximate functions of sparse matrices and matrices with similar structures such as sparse matrices A themselves or matrices that have a similar decay property as matrix functions. We show that when A is a sparse matrix with an unknown sparsity pattern, techniques from compressed sensing can be used under natural assumptions. Moreover, if A is a banded matrix then certain deterministic matrix-vector products can efficiently recover the large entries of f(A). We describe an algorithm for each of the two cases and give error analysis based on the decay bound for the entries of f(A). We finish with numerical experiments showing the accuracy of our algorithms.