The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

DOI10.1137/19M1275231MaRDI QIDQ5146700zbMATH OpenOpenAlexFDO

Authors Jorge Garza Vargas, Archit Kulkarni

Publication date 26 January 2021

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.06012

zbMATH Keywords

concentration of measureLanczos algorithmorthogonal polynomialsRitz values

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Abstract: We study the Lanczos algorithm where the initial vector is sampled uniformly from $mathbb{S}^{n-1}$. Let $A$ be an $nimesn$ Hermitian matrix. We show that when run for few iterations, the output of Lanczos on $A$ is almost deterministic. More precisely, we show that for any $varepsilonin(0,1)$ there exists $c>0$ depending only on $varepsilon$ and a certain global property of the spectrum of $A$ (in particular, not depending on $n$) such that when Lanczos is run for at most $clogn$ iterations, the output Jacobi coefficients deviate from their medians by $t$ with probability at most $exp(-n^{v}arepsilon{t}^2)$ for $t<VertAVert$. We directly obtain a similar result for the Ritz values and vectors. Our techniques also yield asymptotic results: Suppose one runs Lanczos on a sequence of Hermitian matrices $A_{n}in{M}_n(mathbbC)$ whose spectral distributions converge in Kolmogorov distance with rate $O(n^{-varepsilon})$ to a density $mu$ for some $varepsilon>0$. Then we show that for large enough $n$, and for $k=O(sqrtlogn)$, the Jacobi coefficients output after $k$ iterations concentrate around those for $mu$. The asymptotic setting is relevant since Lanczos is often used to approximate the spectral density of an infinite-dimensional operator by way of the Jacobi coefficients; our result provides some theoretical justification for this approach. In a different direction, we show that Lanczos fails with high probability to identify outliers of the spectrum when run for at most $c^{\prime }logn$ iterations, where again $c^{\prime }$ depends only on the same global property of the spectrum of $A$. Classical results imply that the bound $c^{\prime }logn$ is tight up to a constant factor.

Recommendations

• scientific article; zbMATH DE number 1253981
• A Convergence Analysis for Nonsymmetric Lanczos Algorithms
• Convergence of algorithms for problems of Landesman-Lazer type
• The Lanczos and Conjugate Gradient Algorithms
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The Lanczos Algorithm With Partial Reorthogonalization
• Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory
• scientific article; zbMATH DE number 22191
• scientific article; zbMATH DE number 4157770

Cites work

• A note on a method for generating points uniformly on n -dimensional spheres
• A structure preserving Lanczos algorithm for computing the optical absorption spectrum
• A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems
• Adaptive estimation of a quadratic functional by model selection.
• Alice and Bob Meet Banach
• An implicit restarted Lanczos method for large symmetric eigenvalue problems
• Approximating spectral densities of large matrices
• Computing probabilistic bounds for extreme eigenvalues of symmetric matrices with the Lanczos method
• Construction of Gauss-Christoffel Quadrature Formulas
• Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
• Estimates for Some Computational Techniques in Linear Algebra
• Further analysis of the Arnoldi process for eigenvalue problems
• Hankel forms
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 3633705 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 2107939 (Why is no real title available?)
• Numerical methods for large eigenvalue problems
• On the Rates of Convergence of the Lanczos and the Block-Lanczos Methods
• Orthogonal polynomials and random matrices: a Riemann-Hilbert approach.
• Padé and Hermite-Padé approximation and orthogonality
• Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm
• Some new bounds on perturbation of subspaces
• Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
• Which eigenvalues are found by the Lanczos method?

Cited in

(2)

• Which eigenvalues are found by the Lanczos method?
• Stability of the Lanczos algorithm on matrices with regular spectral distributions

Describes a project that uses

Uses Software

• OPQ

This page was built for publication: The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146700)