Error bounds for Lanczos-based matrix function approximation

Tyler Chen

This is a companion piece to the publication:

@article{lanczos_function_CIF,
    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},
    year={2021},
    eprint = {2106.09806},
    archivePrefix = {arXiv},
    primaryClass = {math.NA},
}

Why should I care?

Computing the product of a matrix function \(f(\mathbf{A})\) with a vector \(\mathbf{b}\), where \(\mathbf{A}\) is a symmetric matrix and \(f : \mathbb{R} \to \mathbb{R}\) is a scalar function, is a fundamental task in many disciplines, including scientific computing and data science. Perhaps the most well known example is when \(f(x) = 1/x\) in which case \(f(\mathbf{A}) \mathbf{b} = \mathbf{A}^{-1} \mathbf{b}\) corresponds to solving a linear system of equations. Other commonly used functions include the exponential and logarithm, square root, and sign function, which have applications such as differential equations, Gaussian process sampling, principle component projection/regression, quantum chromodynamics, eigenvalue counting, etc.

Introduction

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.

Contributions of this paper

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.