Error bounds for Lanczos-based matrix function approximation

Tyler Chen

This is a companion piece to the publication:

    title={Error bounds for Lanczos-based matrix function approximation},
    author={Tyler Chen and Anne Greenbaum and Cameron Musco and Christopher Musco},
    author+an = {1=highlight},
    journal={SIAM Journal on Matrix Analysis and Applications},
    eprint = {2106.09806},
    archivePrefix = {arXiv},
    primaryClass = {math.NA},

The Lanczos method for matrix function approximation (Lanczos-FA) can be used to approximate \(f(\mathbf{A})\mathbf{b}\), and in the case that \(f(x) = 1/x\) and \(\mathbf{A}\) is positive definite, this approximation is optimal over Krylov subspace. This case is very well studied and a range of error bounds and estimates exist. However, for other functions, the standard bounds are often too pessimistic as they do not take into account fine grained information about the spectrum of \(\mathbf{A}\) such as outlaying or clustered eigenvalues. This makes it difficult to know when Lanczos-FA has reached a suitable accuracy for a given problem.

In this paper we show how to reduce the error of approximating \(f(\mathbf{A})\mathbf{b}\) with Lanczos-FA to the error of solving a certain linear system with the Lanczos-FA. This allows us to leverage the range of existing bounds for the convergence of Lanczos-FA on linear systems to easily obtain a priori and a posteriori bounds for other matrix functions. Our a posteriori bounds are highly accurate and can be used as practical stopping criteria.