Lanczos Algorithm

The algorithm iteratively builds an orthonormal basis for the Krylov subspace K_m(A, v) = span{v, Av, A^2v, ..., A^{m-1}v}, where A is the input matrix and v is a random starting vector. This subspace naturally contains information about A's extreme eigenvalues. The process generates a sequence of vectors using only matrix-vector multiplications, making it highly efficient for sparse matrices where such operations are cheap.

A core output of the Lanczos iteration is a symmetric tridiagonal matrix T_m. This small, dense matrix (m x m, where m << n) is a projection of the large n x n matrix A onto the Krylov subspace. The eigenvalues of T_m (Ritz values) are excellent approximations to the extreme eigenvalues of A. This reduction from a large sparse matrix to a small tridiagonal one is what makes the eigenvalue problem computationally tractable.

• Structure: T_m has non-zero entries only on its main diagonal and the first sub- and super-diagonals.
• Efficiency: Its eigenvalues can be found using fast, specialized methods like the QR algorithm.

The Lanczos process is defined by a three-term recurrence that generates new basis vectors. For a symmetric matrix A, the recurrence is: β_j q_{j+1} = A q_j - α_j q_j - β_{j-1} q_{j-1} where q_j are the orthonormal Lanczos vectors, α_j = q_j^T A q_j, and β_j = ||A q_j - α_j q_j - β_{j-1} q_{j-1}||. This elegant recurrence means each new vector q_{j+1} is computed using only the previous two vectors (q_j and q_{j-1}) and a single matrix-vector product with A. It avoids the full Gram-Schmidt orthogonalization against all previous vectors, which would be prohibitively expensive.

In finite-precision arithmetic, the Lanczos vectors lose orthogonality due to rounding errors, causing spurious duplicate eigenvalues to appear. This is a fundamental numerical instability. Practical implementations use selective reorthogonalization or the full reorthogonalization scheme to stabilize the process.

• Selective: Only reorthogonalize against converged Ritz vectors.
• Full: Maintain full orthogonality of all Lanczos vectors, at increased cost.
• Implicit Restart: Modern libraries like ARPACK use the Implicitly Restarted Lanczos Method (IRLM), which combines the Lanczos process with polynomial filtering to focus on desired eigenvalues and manage subspace size.

The Lanczos algorithm is the foundational prototype for several key numerical methods:

• Arnoldi Iteration: The generalization of Lanczos for non-symmetric matrices, which produces an upper Hessenberg matrix instead of a tridiagonal one.
• Conjugate Gradient Method: For solving symmetric positive-definite linear systems Ax = b, the CG method is mathematically equivalent to the Lanczos algorithm applied to A.
• Kernel Methods & Nyström Approximation: The Nyström method for low-rank kernel matrix approximation can use a Lanczos-based procedure to efficiently approximate the eigendecomposition.

In ML, Lanczos is not typically used for direct model compression but is a critical tool in related linear algebra computations:

• Low-Rank Approximation: Approximating the top singular values/vectors of large data matrices via the Lanczos bidiagonalization algorithm, a variant for SVD.
• Kernel PCA: Enabling scalable Kernel PCA by approximating the eigendecomposition of the large kernel matrix.
• Second-Order Optimization: Approximating the curvature information (Hessian-vector products) in optimizers like Hessian-free optimization or K-FAC.
• Spectral Analysis of Graphs: Finding the largest/smallest eigenvalues of graph Laplacian or adjacency matrices for spectral clustering and embedding.

Principal Component Analysis (PCA) on massive datasets requires computing the dominant eigenvectors of the covariance matrix. The Lanczos algorithm efficiently approximates these eigenvectors without forming the full covariance matrix, which is often intractably large. This enables PCA on datasets with millions of samples and high-dimensional features, such as in genomics or large-scale image datasets.

• Key Advantage: Operates via matrix-vector products, avoiding O(n³) full eigendecomposition.
• Use Case: Dimensionality reduction for pre-processing before training deep neural networks.

Truncated Singular Value Decomposition (SVD) is a fundamental low-rank factorization technique for compressing neural network layers. The Lanczos algorithm computes the leading singular values and vectors needed for the approximation. By decomposing a large weight matrix W (m x n) into U_k, Σ_k, V_k^T, the parameter count is reduced from m x n to k x (m + n + 1).

• Application: Compressing fully-connected and convolutional layers (via reshaping filters).
• Impact: Directly reduces model size and inference latency, critical for on-device deployment.

Kernel PCA and spectral clustering rely on the eigendecomposition of the kernel (Gram) matrix or graph Laplacian. For large datasets, these matrices are dense and enormous. The Lanczos algorithm, often coupled with the Nyström method for approximation, enables the extraction of the dominant eigenpairs. This makes non-linear dimensionality reduction and graph-based clustering feasible at scale.

• Example: Community detection in large social networks or manifold learning for visualization.

Second-order optimization methods like Natural Gradient Descent and K-FAC (Kronecker-Factored Approximate Curvature) require approximating the inverse of large Fisher Information or Hessian matrices. The Lanczos algorithm is used to perform a low-rank approximation of these matrices, enabling efficient computation of the preconditioner. This can lead to faster convergence during the training of large models.

• Mechanism: Builds a Krylov subspace to approximate the curvature information.
• Benefit: Reduces the number of training iterations, saving computational cost.

Modern randomized numerical linear algebra (RandNLA) techniques often use the Lanczos algorithm as a subroutine. Methods like Randomized SVD first use random projection to sketch a matrix to a smaller subspace, then apply a deterministic algorithm like Lanczos to compute the final SVD of the sketch. This hybrid approach provides robust performance guarantees and is the state-of-the-art for factorizing massive matrices in ML.

• Synergy: Combines statistical sampling (speed) with iterative refinement (accuracy).
• Result: Enables factorization of matrices that do not fit in memory.

In model-based reinforcement learning (MBRL), agents learn a dynamics model of their environment. Linear-quadratic regulator (LQR) controllers, often used for planning within these models, require solving algebraic Riccati equations. The Lanczos algorithm can be employed to solve the associated large-scale eigenvalue problems efficiently, enabling real-time control in high-dimensional state spaces.

• Connection: Related to solving Lyapunov and Sylvester equations for system stability analysis.
• Domain: Robotics and autonomous systems where the state dimension is large.

The Lanczos algorithm is a specific instance of a Krylov subspace method. These are iterative algorithms for solving large-scale eigenvalue problems and linear systems of the form (Ax = b). They construct an approximation subspace, the Krylov subspace, generated by repeated matrix-vector products: (\mathcal{K}_k(A, v) = \text{span}{v, Av, A^2v, ..., A^{k-1}v}).

• Core Principle: For large, sparse matrices, these methods avoid forming the full matrix, relying only on matrix-vector multiplications.
• Key Variants: The Arnoldi iteration generalizes Lanczos to non-symmetric matrices. The Conjugate Gradient method is a Krylov subspace solver for symmetric positive-definite linear systems.

Singular Value Decomposition (SVD) is the definitive matrix factorization, expressing any matrix (A) as (A = U\Sigma V^T), where (U) and (V) are orthogonal matrices and (\Sigma) is a diagonal matrix of singular values. The Lanczos algorithm can be used to efficiently compute a partial SVD for large, sparse matrices.

• Connection to Lanczos: Applying Lanczos to the matrices (A^TA) and (AA^T) yields approximations of the singular vectors and values.
• Low-Rank Approximation: The Truncated SVD, keeping only the top-(k) singular values/vectors, is the optimal rank-(k) approximation (Eckart–Young theorem), a primary goal in model compression.

The Rayleigh quotient is a scalar function (R(A, x) = \frac{x^T A x}{x^T x}) for a symmetric matrix (A) and a non-zero vector (x). It provides a crucial estimate for an eigenvalue.

• Min-Max Principle: For a symmetric matrix, the minimum and maximum values of the Rayleigh quotient over all vectors are the smallest and largest eigenvalues, respectively.
• Role in Lanczos: The Ritz values and vectors computed in the Lanczos algorithm are derived from the Rayleigh quotient restricted to the Krylov subspace, providing increasingly accurate approximations to the extreme eigenvalues.

Power iteration is the simplest iterative method for finding the dominant eigenvector (associated with the eigenvalue of largest magnitude) of a diagonalizable matrix. It repeatedly applies the matrix to a vector: (x_{k+1} = \frac{A x_k}{|A x_k|}).

• Limitation: It finds only one eigenvector. Subspace iteration extends it to find multiple eigenvectors.
• Foundation: The Lanczos algorithm can be viewed as a sophisticated generalization. While power iteration uses information from a single vector sequence, Lanczos orthogonalizes the entire Krylov subspace, enabling the simultaneous approximation of multiple eigenvalues and eigenvectors with far superior convergence.

A tridiagonal matrix has non-zero entries only on the main diagonal and the diagonals immediately above and below it. This structure is central to the Lanczos algorithm's efficiency.

• Lanczos Tridiagonalization: For an (n \times n) symmetric matrix (A), the Lanczos process produces an orthonormal basis (Q_k) and a symmetric tridiagonal matrix (T_k) such that (A Q_k \approx Q_k T_k).
• Computational Benefit: The eigenvalue problem for the large, sparse (A) is reduced to the much simpler problem of finding eigenvalues of the small, dense tridiagonal matrix (T_k), which can be solved efficiently using the QR algorithm.

Randomized SVD is a modern, highly scalable algorithm for low-rank matrix approximation. It uses random sampling to construct a small subspace that captures the matrix's range, followed by a deterministic SVD on the reduced matrix.

• Process: It projects the input matrix onto a random low-dimensional subspace, then performs a standard SVD on the projected matrix.
• Comparison to Lanczos: While Lanczos is deterministic and optimal for the Krylov subspace it builds, randomized SVD is often faster for very large matrices and is highly parallelizable. It provides a probabilistic guarantee of accuracy and is less susceptible to the numerical instability (loss of orthogonality) that plagues the naive Lanczos algorithm.