Nyström Subsampling for Scalable Kernel Methods

413 concepts290 papers1 proposal

Kernel methods offer an elegant mathematical framework for learning non-linear relationships by mapping data into infinite-dimensional Reproducing Kernel Hilbert Spaces (RKHS). However, this elegance comes with a severe computational penalty. To train a kernel-based model on a dataset of $n$ samples, one must typically compute and manipulate a pairwise similarity matrix $K \in \mathbb{R}^{n \times n}$.

Downstream operations—such as matrix inversion, eigendecomposition, or solving linear systems—require $O(n^3)$ time and $O(n^2)$ memory. As Zhi-Hua Zhou notes in Kernel method for matrix completion with side information and its application in multi-label learning, these cubic costs quickly become prohibitive for large-scale datasets. If a dataset contains a million points, computing the full kernel matrix requires tracking one trillion entries—an impossible feat for standard hardware.

The Nyström method bypasses this bottleneck by constructing a low-rank approximation of the full kernel matrix using a small, intelligently selected subset of data points.

The Core Mechanism: Landmark-Based Approximation

Instead of computing the full $n \times n$ matrix $K$, the Nyström method randomly samples a small subset of $m$ data points ($m \ll n$), often referred to as landmarks, anchor points, or basis points.

Let the full dataset be $X$ and the sampled landmarks be $Z$. We can partition the exact kernel matrix based on the relationships between these sets:

  1. $K_{mm} \in \mathbb{R}^{m \times m}$: The exact kernel matrix computed exclusively between the landmarks.
  2. $K_{nm} \in \mathbb{R}^{n \times m}$: The cross-kernel matrix measuring the similarity between all $n$ points in the dataset and the $m$ landmarks.

The Nyström method approximates the full, massive $n \times n$ matrix as a product of these smaller matrices:

$$\tilde{K} = K_{nm} K_{mm}^{-1} K_{mn}$$

   Full Matrix K (n x n)               Nyström Approximation K̃
     [               ]               [           ]   [       ]⁻¹ [       ]
     [               ]       ≈       [  K_nm     ] × [ K_mm  ]   [  K_mn ]
     [               ]               [  (n x m)  ]   [ (m x m) ]   [ (m x n)]
     [               ]               [           ]

Mechanically, this factorization acts as a data-dependent projection. Instead of evaluating every point against every other point, we evaluate every point against the landmarks, and use the internal geometry of the landmarks ($K_{mm}^{-1}$) to reconstruct the global structure.

As highlighted by Raja Hafiz Affandi et al. in Nystrom Approximation for Large-Scale Determinantal Processes, this simple algebraic trick collapses the computational complexity of downstream matrix operations from cubic $O(n^3)$ down to linear $O(n m^2)$, making previously impossible tasks highly scalable.

Why It Works: The Intuition of Low-Rank Geometry

It is reasonable to wonder why a tiny fraction of the data can accurately reconstruct the geometry of a massive dataset. The answer lies in the spectral properties of real-world data.

Although the RKHS is high- or infinite-dimensional, real-world data rarely fills this space uniformly. Instead, data typically concentrates along lower-dimensional manifolds. Consequently, the eigenvalues of the true kernel matrix $K$ decay rapidly—often exponentially or polynomially. The vast majority of the matrix's variance is captured by its top few eigenvectors, while the remaining dimensions represent negligible variance or high-frequency noise.

By selecting $m$ landmarks, we are effectively sampling points that span this dominant, low-dimensional subspace. In Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces, Junhong Lin et al. formalize this intuition. They prove that as long as the number of landmarks $m$ is proportional to the "effective dimension" of the data, the Nyström-approximated model achieves the exact same optimal statistical convergence rates as the full-rank estimator.

Crucially, the number of landmarks required does not need to scale linearly with the dataset size. Danica J. Sutherland et al. demonstrate in Efficient and principled score estimation with Nyström kernel exponential families that a sub-linearly growing subset preserves full statistical accuracy. For specific tasks like preconditioning, Amirhesam Abedsoltan et al. show in On the Nyström Approximation for Preconditioning in Kernel Machines that the sample size needed for effective acceleration scales merely logarithmically with the total dataset size.

From Classical Kernels to Neural Tangents

While originally designed for classical algorithms like Kernel Ridge Regression or Gaussian Processes, Nyström approximations have become vital for scaling modern deep learning theory, particularly through the lens of the Neural Tangent Kernel (NTK).

The NTK describes the training dynamics of neural networks as a kernel machine. However, computing the empirical NTK for a large dataset is exceptionally expensive. To make this tractable, Julián Tachella et al. in The Neural Tangent Link Between CNN Denoisers and Non-Local Filters utilize the Nyström method to reconstruct a low-rank version of the full NTK matrix, enabling efficient analytic computation of network outputs without requiring iterative training.

Similarly, in Bayesian deep learning, Zhijie Deng et al. introduce ELLA in Accelerated Linearized Laplace Approximation for Bayesian Deep Learning. ELLA constructs a low-rank approximation of the NTK using Nyström anchor points, slashing the memory and computational requirements for uncertainty estimation. This allows Laplace approximations to scale to massive architectures like Vision Transformers where standard methods fail.

By treating a small subset of data points as landmarks to interpolate infinite-dimensional spaces, the Nyström method bridges the gap between the mathematical elegance of kernel Hilbert spaces and the scale of modern big data. This is epitomized by highly optimized solvers like the one proposed by Giacomo Meanti in Kernel Methods Through the Roof: Handling Billions of Points Efficiently, which scales kernel learning to billions of points by pairing Nyström subsampling with hardware-accelerated solvers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 315 papers
  2. Version 1 · 2026-10-04 · 561 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_low_rank_kernel_approximation_nystrom_ap_ea91f7a9,
  title = {low-rank kernel approximation (Nyström approximation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/low-rank-kernel-approximation-nystrom-approximation/rdr_ea91f7a9067c4a4999b7ddac6ca75f59},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_low_rank_kernel_approximation_nystrom_ap_ea91f7a9_v2,
  title = {low-rank kernel approximation (Nyström approximation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/low-rank-kernel-approximation-nystrom-approximation/rdr_ea91f7a9067c4a4999b7ddac6ca75f59/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake