Nyström Method

The core mechanism of the Nyström method is the selection of a landmark subset of m columns (or rows) from the original n x n kernel matrix K. This subset, often chosen via uniform random sampling, k-means clustering, or leverage score sampling, forms the basis for the approximation. The selected columns are assembled into matrix C (size n x m), and the intersection of these columns and corresponding rows forms matrix W (size m x m). The full approximation is then constructed as K ≈ C * W^† * C^T, where W^† is the pseudoinverse of W.

The method explicitly produces a rank-k approximation of the kernel matrix, where k ≤ m. The approximation is derived from the eigendecomposition of the small m x m matrix W. By extending these eigenvectors to the full dataset via the Nyström extension formula, the method approximates the top eigenvalues and eigenvectors of the full n x n matrix K without ever computing it entirely. This is critical for applications like kernel PCA, where the dominant eigenstructure defines the projection.

The primary advantage is a drastic reduction in computational complexity and memory footprint.

• Complexity: Building the full kernel matrix is O(n^2) in memory and O(n^2 * d) in computation (where d is feature dimension). The Nyström method reduces this to O(n * m) memory and computation, where m << n.
• Eigendecomposition: Performing eigenanalysis on the full K is O(n^3). With Nyström, it is performed on W, costing O(m^3), and the extension is O(n * m * k). This enables kernel methods on datasets with millions of points.

This is the mathematical engine that generalizes eigenvectors from the sample to the full dataset. If v is an eigenvector of W with eigenvalue λ, the corresponding approximated eigenvector u for the full matrix K is given by: u = (1/√λ) * C * v This formula allows the out-of-sample extension of kernel-based embeddings, enabling the embedding of new, unseen data points into the low-dimensional space defined by the landmark samples without retraining.

The quality of the approximation is governed by the spectral norm error ||K - K_approx|| or the Frobenius norm error. Theoretical bounds show this error is related to how well the selected columns span the column space of K. Key factors include:

• Number of landmarks (m): Error typically decreases as m increases.
• Sampling strategy: Adaptive methods (e.g., based on leverage scores) often provide tighter bounds than uniform random sampling.
• Matrix spectrum: Matrices with rapidly decaying eigenvalues (i.e., low effective rank) are approximated more accurately with fewer samples.

In Gaussian Processes (GPs), the Nyström method is conceptually identical to the subset of regressors approximation and is closely related to sparse Gaussian Processes using inducing points. The selected landmark columns correspond to the inducing inputs or pseudo-inputs. The approximation K ≈ C * W^† * C^T is used to construct a low-rank approximation of the kernel covariance matrix, reducing the O(n^3) training complexity of exact GPs to O(n * m^2). This makes large-scale GP regression and classification feasible.

A kernel matrix (or Gram matrix) is a square, symmetric matrix where each entry represents the similarity between two data points in a high-dimensional feature space, as defined by a kernel function. It is the fundamental data structure for kernel methods like Support Vector Machines (SVMs) and Gaussian Processes.

• Construction: For a dataset of n points, the kernel matrix K has dimensions n x n, with K_ij = k(x_i, x_j).
• Properties: It must be positive semi-definite (PSD) for many kernel methods to be valid.
• Challenge: Its O(n²) size and O(n³) eigendecomposition cost make direct use infeasible for large datasets, which is precisely the problem the Nyström method addresses.

Low-rank approximation is the process of representing a matrix using a product of smaller matrices whose combined rank k is much less than the original matrix's dimensions. This reduces storage from O(n²) to O(nk) and computational complexity for matrix-vector products.

• Goal: Find a matrix B of rank k that minimizes ||A - B|| under a norm like the Frobenius norm.
• Foundation: The Eckart–Young theorem proves the optimal rank-k approximation is given by the Truncated SVD.
• Connection to Nyström: The Nyström method provides a specific, scalable way to generate a low-rank approximation of a kernel matrix by sampling a subset of its columns.

Randomized linear algebra is a class of algorithms that use randomness as a computational tool to efficiently solve large-scale matrix problems, such as low-rank approximation and linear regression. These methods often provide provable performance guarantees with high probability.

• Core Idea: Use random sampling or random projections to identify a subspace that captures the matrix's essential action.
• Key Techniques: Includes Randomized SVD, random projections (Johnson-Lindenstrauss lemma), and subspace iteration.
• Relation: The Nyström method is a randomized algorithm for kernel matrices, where the randomness comes from the column subset selection. Modern Nyström implementations often use sophisticated randomized sampling strategies.

Inducing points (or landmarks) are a strategically chosen subset of the original data points used to summarize the entire dataset in scalable Gaussian process and kernel method approximations.

• Function: They act as a basis for a low-dimensional subspace that approximates the function space defined by the full kernel.
• Selection Methods: Can be selected uniformly at random, via k-means clustering, or through leverage score sampling to maximize representativeness.
• Direct Link: In the Nyström method, the columns of the kernel matrix corresponding to these inducing points form the submatrix used for the approximation. The quality of the approximation hinges on their selection.

Singular Value Decomposition (SVD) is the fundamental matrix factorization that decomposes any real or complex matrix A into three matrices: A = U Σ V*, where U and V are orthogonal/unitary and Σ is a diagonal matrix of non-negative singular values.

• Significance: It reveals the intrinsic geometric structure of a matrix, including its rank, range, and null space.
• Optimality: The Truncated SVD, which keeps only the top k singular values/vectors, provides the optimal rank-k approximation (Eckart–Young theorem).
• Nyström Connection: The Nyström method approximates the eigendecomposition of a PSD kernel matrix, which is directly related to its SVD. It effectively approximates the dominant eigenvectors/eigenvalues without computing the full matrix.

Kernel Ridge Regression (KRR) is a non-parametric regression technique that combines ridge regression (L2 regularization) with the kernel trick, allowing learning of complex, non-linear functions.

• Problem: Solving (K + λI) α = y, where K is the n x n kernel matrix, is an O(n³) operation.
• Scalability Bottleneck: The need to invert the full kernel matrix makes KRR intractable for large n.
• Primary Application: The Nyström method is frequently used to approximate K with a low-rank matrix ~K, transforming the O(n³) solve into an O(n k²) operation, enabling the application of KRR to massive datasets.