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.