Error bounds for Lanczos-based matrix function approximation

Abstract

We analyze the Lanczos method for matrix function approximation (Lanczos-FA), an iterative algorithm for computing $f(\mathbf{A})\mathbf{b}$ when $\mathbf{A}$ is a Hermitian matrix and $\mathbf{b}$ is a given vector. Assuming that $f:\mathbb{C}\to \mathbb{C}$ is piecewise analytic, we give a framework, based on the Cauchy integral formula, which can be used to derive a priori and a posteriori error bounds for Lanczos-FA in terms of the error of Lanczos used to solve linear systems. Unlike many error bounds for Lanczos-FA, these bounds account for fine-grained properties of the spectrum of $\mathbf{A}$, such as clustered or isolated eigenvalues. Our results are derived assuming exact arithmetic, but we show that they are easily extended to finite precision computations using existing theory about the Lanczos algorithm in finite precision. We also provide generalized bounds for the Lanczos method used to approximate quadratic forms ${\mathbf{b}}^{\text{H}}f(\mathbf{A})\mathbf{b}$, and demonstrate the effectiveness of our bounds with numerical experiments.

References in corpus (10)

• Numerical Methods for the QCD Overlap Operator: I. Sign-Function and Error Bounds
• On the Neuberger overlap operator
• 2-norm error bounds and estimates for Lanczos approximations to linear systems and rational matrix functions
• Computable upper error bounds for Krylov approximations to matrix exponentials and associated $\phi$-functions
• Computational Methods for UV-Suppressed Fermions
• Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization
• Principal Component Projection Without Principal Component Analysis
• Analysis of stochastic Lanczos quadrature for spectrum approximation
• Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
• Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG

Cited by in corpus (4)

• Krylov-aware stochastic trace estimation
• Low-memory Krylov subspace methods for optimal rational matrix function approximation
• Escaping the Krylov space during finite precision Lanczos
• A posteriori error bounds for the block-Lanczos method for matrix function approximation