Stochastic Lanczos Quadrature for Computational Uncertainty in Linear Algebra
Abstract
Applying a matrix function to a vector is a common operation in large-scale scientific computing, such as Bayesian inference. When the matrix is symmetric positive definite and the function is its inverse, the Lanczos algorithm gives a matrix-free approximation from matrix-vector products alone. Stopping after a fixed number of steps keeps the approximation on the explored Krylov subspace but assigns nothing to its orthogonal complement, which holds the smallest eigenvalues and therefore the largest contributions to the inverse. This truncation is usually treated as a silent numerical error rather than as measurable uncertainty. We show that a single Lanczos run yields both a matrix-free approximation of the inverse and a Gaussian distribution over the exact result, whose covariance measures what the truncation discarded and concentrates as the number of steps grows. The covariance restores the complement in two parts: a rank-one coupling at the truncation boundary, given exactly by the Lanczos residual, and an isotropic term on the remaining bulk, whose size we estimate by Projected Stochastic Lanczos Quadrature, reusing one Krylov basis across all probes. We prove consistency, with bias decaying exponentially in the quadrature depth and variance at the Monte Carlo rate
Related
- A Range-Deflated Stochastic Lanczos Quadrature Method for Large-Scale Log-Determinant Estimation
- Diffusion-Based Stochastic Operator Networks for Uncertainty Quantification in Stochastic Partial Differential Equations
- Enhancing Statistical-Computational Balance in Uncertainty Quantification of Bagging: A Cheap Bootstrap Approach
- On the computational cost of Stochastic Gradient Langevin Dynamics
- Economic resources, sporting efficiency and uncertainty: a stochastic optimization model of football performance in Africa
BibTeX
@misc{fifen2026stochastic,
title = {{Stochastic Lanczos Quadrature for Computational Uncertainty in Linear Algebra}},
author = {Hassan Fifen and Issa Karambal and Philipp Hennig},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10080},
eprint = {2609.10080},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10080},
}
RIS
TY - UNPB
TI - Stochastic Lanczos Quadrature for Computational Uncertainty in Linear Algebra
AU - Hassan Fifen
AU - Issa Karambal
AU - Philipp Hennig
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10080
UR - https://arxiv.org/abs/2609.10080
AB - Applying a matrix function to a vector is a common operation in large-scale scientific computing, such as Bayesian inference. When the matrix is symmetric positive definite and the function is its inverse, the Lanczos algorithm gives a matrix-free approximation from matrix-vector products alone. Stopping after a fixed number of steps keeps the approximation on the explored Krylov subspace but assigns nothing to its orthogonal complement, which holds the smallest eigenvalues and therefore the largest contributions to the inverse. This truncation is usually treated as a silent numerical error rather than as measurable uncertainty. We show that a single Lanczos run yields both a matrix-free approximation of the inverse and a Gaussian distribution over the exact result, whose covariance measures what the truncation discarded and concentrates as the number of steps grows. The covariance restores the complement in two parts: a rank-one coupling at the truncation boundary, given exactly by the Lanczos residual, and an isotropic term on the remaining bulk, whose size we estimate by Projected Stochastic Lanczos Quadrature, reusing one Krylov basis across all probes. We prove consistency, with bias decaying exponentially in the quadrature depth and variance at the Monte Carlo rate
ER -