Stability of the Lanczos Method for Matrix Function Approximation

Cameron Musco, Christopher Musco, Aaron Sidford

TL;DR

This paper analyzes the stability of the Lanczos method for approximating matrix functions in finite precision arithmetic. It shows that for general functions, Lanczos performs nearly as well as in exact arithmetic, requiring only a modest amount of precision. However, for the important case of solving linear systems, existing finite-precision bounds are surprisingly weak, suggesting a potential gap between theory and practice.

What Problem Does This Paper Address?

The Lanczos method is a powerful tool for approximating functions of matrices, like $f(A)x$. In exact arithmetic, its error is bounded by the best polynomial approximation of $f(x)$ on the matrix's eigenvalue range. However, in real-world computations using floating-point numbers, numerical errors can accumulate, potentially degrading performance. While the Lanczos method is known to be surprisingly robust in practice for matrix function approximation, rigorous theoretical guarantees matching the exact arithmetic bounds in finite precision were missing. For the specific problem of solving linear systems ($f(A) = A^{-1}$), existing finite-precision bounds are significantly weaker than their exact arithmetic counterparts, raising questions about the true performance limits.

Methods

The paper's core contribution is a rigorous analysis of Lanczos in finite precision. Key techniques include:

  • Leveraging Chebyshev Polynomials: The authors build upon existing work that uses the stability of Chebyshev polynomials to analyze the behavior of more general functions.
  • Error Analysis of Lanczos Recurrence: They carefully analyze the error introduced by floating-point arithmetic in the Lanczos recurrence relations, particularly focusing on the loss of orthogonality in the computed basis vectors.
  • Stable Eigendecomposition of Tridiagonal Matrices: A crucial part of the analysis involves showing that the final step of computing $f(T)$ (where $T$ is the tridiagonal matrix produced by Lanczos) can be done stably using existing algorithms, even with finite precision.
  • Lower Bound Construction: For the linear systems case, a novel "hard instance" construction is used to derive a lower bound on the number of iterations required by finite-precision algorithms, demonstrating that some existing bounds are overly pessimistic.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • General Functions are Well-Behaved: For general matrix functions, Lanczos in finite precision is remarkably stable, closely matching the theoretical guarantees of exact arithmetic with a reasonable number of bits. This explains its practical robustness.
  • Linear Systems are Tricky: The analysis for $A^{-1}$ reveals a significant gap between exact and finite-precision guarantees. The authors construct matrices where finite-precision methods require exponentially more iterations than exact arithmetic, even for relatively low precision.
  • "Stable Approximating Polynomials" are a Bottleneck: The paper suggests that for linear systems, the performance of finite-precision Lanczos/CG might be fundamentally limited by the existence of "stable approximating polynomials" for $1/x$ around eigenvalues. If such polynomials don't exist with low degree, convergence suffers.
  • The Power of Polynomial Approximation: The work highlights how understanding the approximation properties of polynomials (especially Chebyshev polynomials) is key to analyzing the stability of numerical algorithms.

Key Results

  • Theorem 1: For general functions $f(A)x$, finite-precision Lanczos achieves an error bound that matches the exact arithmetic guarantee up to a logarithmic factor in the number of iterations, provided sufficient precision is used (related to $\log(nk||A||)$ bits).
  • Lower Bound (Theorem 3 & Corollary 4): For positive definite matrices, there exist instances where finite-precision conjugate gradient (and by extension, Lanczos) requires $\Omega(\kappa^c)$ iterations (for some constant $c$) to achieve a constant factor approximation to $A^{-1}x$, even with high precision. This is significantly worse than the exact arithmetic bound of $O(\log^2 \kappa)$.
  • Applications: The paper demonstrates how these theoretical results can be applied to achieve state-of-the-art end-to-end runtime bounds for approximating matrix step functions, matrix exponentials, and top singular values, even in finite precision.

Limitations and Future Work

  • Linear Systems Lower Bound: The authors pose the question of whether their lower bound for linear systems is unconditional or if there's a "smarter" approach beyond stable approximating polynomials that could yield better bounds.
  • Generalizing Lower Bounds: Extending the lower bound analysis to other functions beyond $1/x$ is an open area.
  • Other Lanczos Variants: The analysis primarily focuses on a basic Lanczos implementation. Investigating the stability of reorthogonalized or block variants of Lanczos for other tasks (like low-rank approximation) is suggested.
  • Precision Requirements: While the paper provides bounds based on precision, the exact relationship between required bits and problem parameters could be further explored.

Summary updated

Abstract

The ubiquitous Lanczos method can approximate $f(A)x$ for any symmetric $n \times n$ matrix $A$, vector $x$, and function $f$. In exact arithmetic, the method's error after $k$ iterations is bounded by the error of the best degree-$k$ polynomial uniformly approximating $f(x)$ on the range $[\lambda_{min}(A), \lambda_{max}(A)]$. However, despite decades of work, it has been unclear if this powerful guarantee holds in finite precision. We resolve this problem, proving that when $\max_{x \in [\lambda_{min}, \lambda_{max}]}|f(x)| \le C$, Lanczos essentially matches the exact arithmetic guarantee if computations use roughly $\log(nC\|A\|)$ bits of precision. Our proof extends work of Druskin and Knizhnerman [DK91], leveraging the stability of the classic Chebyshev recurrence to bound the stability of any polynomial approximating $f(x)$. We also study the special case of $f(A) = A^{-1}$, where stronger guarantees hold. In exact arithmetic Lanczos performs as well as the best polynomial approximating $1/x$ at each of $A$'s eigenvalues, rather than on the full eigenvalue range. In seminal work, Greenbaum gives an approach to extending this bound to finite precision: she proves that finite precision Lanczos and the related CG method match any polynomial approximating $1/x$ in a tiny range around each eigenvalue [Gre89]. For $A^{-1}$, this bound appears stronger than ours. However, we exhibit matrices with condition number $\kappa$ where exact arithmetic Lanczos converges in $polylog(\kappa)$ iterations, but Greenbaum's bound predicts $\Omega(\kappa^{1/5})$ iterations. It thus cannot offer significant improvement over the $O(\kappa^{1/2})$ bound achievable via our result. Our analysis raises the question of if convergence in less than $poly(\kappa)$ iterations can be expected in finite precision, even for matrices with clustered, skewed, or otherwise favorable eigenvalue distributions.
BibTeX
@inproceedings{musco2017stability,
  author = {Cameron Musco and Christopher Musco and Aaron Sidford},
  title = {{Stability of the Lanczos Method for Matrix Function Approximation}},
  booktitle = {SODA},
  year = {2017},
  doi = {10.1137/1.9781611975031.105},
}
Figure