Efficient reduced-rank methods for Gaussian processes with eigenfunction expansions

Philip Greengard, Michael O'Neil

TL;DR

This paper introduces a numerical framework for Gaussian Process (GP) regression that uses Karhunen-Loève (KL) expansions to achieve $L^2$-optimal reduced-rank approximations. By precomputing the eigenfunctions of the covariance kernel independently of the data, the authors enable high-accuracy inference for large datasets ($N > 100,000$) in seconds, even for non-smooth kernels.

What Problem Does This Paper Address?

Gaussian Processes are a gold standard for Bayesian non-parametric modeling, but they suffer from a "computational tax": the cost of training scales as $O(N^3)$, where $N$ is the number of data points. For modern datasets with tens of thousands of points, this is a dealbreaker.

Existing "fast" methods usually fall into two camps:

  1. Data-dependent approximations: Like Nyström methods, which sub-sample data points to approximate the covariance matrix.
  2. Structural assumptions: Methods that require the kernel to be translation-invariant (stationary) or the data to lie on a grid.

The authors identify a gap: we need a method that is optimally efficient (using the fewest basis functions possible for a given error) and data-independent (allowing us to do the heavy lifting before we even see the observations).

Methods

The core idea is to convert the GP into its Karhunen-Loève (KL) expansion. Think of this as the functional version of Principal Component Analysis (PCA). It represents the GP as a sum of fixed basis functions (eigenfunctions) with random weights.

The authors contribute three specific algorithmic improvements:

  • Algorithm 1 (The Standard Case): A Nyström-based discretization using Gaussian nodes and weights to solve the integral eigenvalue problem. They use Legendre polynomials to represent the eigenfunctions, allowing for high-order accuracy.
  • Algorithm 3 (The Non-Smooth Case): Standard discretization fails for kernels like the Matérn family, which have "kinks" at the origin. The authors use a specialized high-order quadrature scheme that splits the integral to handle the non-smoothness, maintaining super-algebraic convergence.
  • Algorithm 2 (Bayesian Hyperparameters): They introduce a fast way to fit hyperparameters (like length-scale) by discretizing the hyperparameter space and using quadrature, avoiding the need for expensive MCMC or gradient-based optimization in the full GP space.
  • Algorithm 4 (2D Extension): They extend the approach to 2D using tensor products of Gaussian nodes.

Datasets

The paper evaluates the algorithms using synthetic datasets designed to test accuracy and scaling:

  • 1D Regression: Data generated from $y = \cos(3e^x) + \epsilon$ and $y = \sin(2x) + \epsilon$. These test the ability to recover complex oscillations and handle different noise levels.
  • 2D Regression: Data generated on a square grid from $y = -x_2 + \sin(6x_1) + \epsilon$.
  • Kernels: They specifically test the Squared Exponential (very smooth) and Matérn 3/2 (less smooth) kernels.

Key Insights and Ideas

  • Precomputation is King: Because the KL expansion depends only on the kernel and the domain (e.g., an interval $[a, b]$), you can compute the basis functions once. When new data arrives, regression becomes a simple ridge regression problem in "weight space," which is incredibly fast.
  • $L^2$ Optimality: The KL expansion is mathematically guaranteed to be the best possible reduced-rank representation in the $L^2$ sense. This means for a fixed budget of $m$ basis functions, this method will generally be more accurate than Fourier-based or random feature methods.
  • Handling the "Kink": Most reduced-rank methods struggle with Matérn kernels because they aren't infinitely differentiable. By using specialized quadrature (Algorithm 3), the authors show you can still get high-precision results without needing thousands of basis functions.

Key Results

  • Speed: In 2D, the method handled 160,000 data points in roughly 7 seconds (including KL expansion and regression). For comparison, a direct $O(N^3)$ approach would be impossible on a standard laptop for this $N$.
  • Accuracy: For a squared exponential kernel with a length-scale of 0.1, they achieved an accuracy of $10^{-3}$ using only 25 basis functions.
  • Comparison: The authors compared their approach to "Hilbert-GP" (a popular Laplacian-based approximation). Their method (Algorithm 1) consistently achieved lower error for the same number of basis functions, especially for smaller length-scales.

Limitations and Future Work

  • The Curse of Dimensionality: This is the primary bottleneck. Because the number of basis functions scales as $m^d$ (where $d$ is the dimension), the method is currently practical only for 1D, 2D, and perhaps 3D problems. It is not suitable for high-dimensional machine learning tasks (e.g., $d=100$).
  • Spatially Adaptive Methods: The authors suggest that for higher dimensions, one might need to combine this with spatially adaptive trees to locally reduce the ambient dimension.
  • Non-Gaussian Processes: A promising future direction mentioned is extending this framework to "stable distributions" and other non-Gaussian stochastic processes.

Summary updated

Abstract

In this work, we introduce a reduced-rank algorithm for Gaussian process regression. Our numerical scheme converts a Gaussian process on a user-specified interval to its Karhunen–Loève expansion, the $$L^2$$ L 2 -optimal reduced-rank representation. Numerical evaluation of the Karhunen–Loève expansion is performed once during precomputation and involves computing a numerical eigendecomposition of an integral operator whose kernel is the covariance function of the Gaussian process. The Karhunen–Loève expansion is independent of observed data and depends only on the covariance kernel and the size of the interval on which the Gaussian process is defined. The scheme of this paper does not require translation invariance of the covariance kernel. We also introduce a class of fast algorithms for Bayesian fitting of hyperparameters and demonstrate the performance of our algorithms with numerical experiments in one and two dimensions. Extensions to higher dimensions are mathematically straightforward but suffer from the standard curses of high dimensions.
BibTeX
@article{greengard2022efficient,
  author = {Philip Greengard and Michael O'Neil},
  title = {{Efficient reduced-rank methods for Gaussian processes with eigenfunction expansions}},
  journal = {Stat. Comput.},
  year = {2022},
  doi = {10.1007/s11222-022-10124-z},
}

Loading related content...

Figure