The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that adapts power methods to find the m "most useful" (tending towards extreme highest or lowest) eigenvalues and eigenvectors of an n×n Hermitian matrix, where m is often but not necessarily much smaller than n. Although computationally efficient in principle, the method as initially formulated was not useful due to its numerical instability. In 1970, Ojalvo and Newman showed how to make the method numerically stable and applied it to the solution of very large engineering structures subjected to dynamic loading. This was achieved using a method for purifying the Lanczos vectors (i.e. by repeatedly reorthogonalizing each newly generated vector with all previously generated ones) to any degree of accuracy, which when not performed, produced a series of vectors that were highly contaminated by those associated with the lowest natural frequencies.
In their original work, these authors also suggested how to select a starting vector (i.e. use a random-number generator to select each element of the starting vector) and suggested an empirically determined method for determining m, the reduced number of vectors (i.e. it should be selected to be approximately 1.5 times the number of accurate eigenvalues desired). Soon thereafter their work was followed by Paige, who also provided an error analysis. In 1988, Ojalvo produced a more detailed history of this algorithm and an efficient eigenvalue error test.
Algorithm Overview
Input a Hermitian matrix A of size n×n, and optionally a number of iterations m (as default, let m=n). Strictly speaking, the algorithm does not need access to the explicit matrix, but only a function v↦Av that computes the product of the matrix by an arbitrary vector. This function is called at most m times. Output an n×m matrix V with orthonormal columns and a tridiagonal real symmetric matrix T=VAV of size m×m. If m=n, then V is unitary, and A=VTV. The Lanczos iteration is prone to numerical instability; when executed in non-exact arithmetic, additional measures (as outlined in later sections) should be taken to ensure validity of the results.
The algorithm proceeds by generating a sequence of orthonormal vectors v1, v2, ..., vm that form a basis for the Krylov subspace. Starting with an arbitrary vector v1 of norm 1, each step computes a new vector by applying the matrix A, orthogonalizing against the previous vector, and normalizing. The coefficients αj and βj form the diagonal and off-diagonal entries of the tridiagonal matrix T, whose eigenvalues approximate those of A.
Numerical Stability and Reorthogonalization
The original Lanczos algorithm suffered from loss of orthogonality due to floating-point roundoff, leading to spurious eigenvalues and inaccurate eigenvectors. The 1970 stabilization by Ojalvo and Newman introduced full reorthogonalization: each newly generated vector is orthogonalized against all previously generated ones. This purifies the Lanczos vectors and restores numerical stability, though at the cost of increased computational overhead. Paige's error analysis in the early 1970s provided theoretical bounds on the effects of roundoff and justified the reorthogonalization approach.
Applications in Machine Learning
In Machine learning, the Lanczos algorithm is used for large-scale eigenvalue problems, such as computing the top eigenvalues of covariance matrices in PCA or spectral clustering. It is also employed in Deep learning for approximating the Hessian spectrum of neural networks, which aids in optimization and generalization analysis. The algorithm's ability to work with matrix-vector products only makes it suitable for very large matrices arising in large language models and generative AI systems, where explicit matrix storage is infeasible.
Related Methods and Extensions
The Lanczos algorithm is closely related to the conjugate gradient method for solving linear systems, as both build Krylov subspaces. It also connects to the Arnoldi iteration for non-Hermitian matrices. Variants such as the block Lanczos algorithm handle multiple starting vectors, and the implicitly restarted Lanczos method (used in ARPACK) improves convergence and memory usage. These extensions are implemented in numerical libraries like LAPACK and SciPy, making the algorithm a standard tool in scientific computing.
Historical Impact and Modern Use
Since its stabilization, the Lanczos algorithm has been applied to structural engineering, quantum chemistry, and signal processing. In the context of Artificial intelligence, it underpins many spectral methods used in data analysis and model compression. The algorithm's efficiency and robustness have made it a cornerstone of numerical linear algebra, with ongoing research into improving its stability and parallelization for modern hardware such as GPUs and specialized AI accelerators.
See Also
- power-iteration
- eigenvalue-decomposition
- krylov-subspace
- conjugate-gradient