Efficient reduced-rank methods for Gaussian processes with eigenfunction expansions

Philip Greengard, Michael O'Neil

Abstract

In this work, we introduce a reduced-rank algorithm for Gaussian process (GP) regression. Our numerical scheme converts a Gaussian process on a user-specified interval to its Karhunen-Loève (KL) expansion, the $L^2$-optimal reduced-rank representation. Numerical evaluation of the KL expansion is performed once during precomputation and involves computing a numerical eigendecomposition of an integral operator whose kernel is the covariance function of the GP. The KL expansion is independent of observed data and depends only on the covariance kernel and the size of the interval. We also introduce a class of fast algorithms for Bayesian fitting of hyperparameters and demonstrate performance in one and two dimensions.

Introduction

Gaussian Processes are a gold standard for Bayesian non-parametric modeling due to their flexibility and principled uncertainty quantification. However, they suffer from a significant "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 cubic scaling becomes a bottleneck.

Existing fast methods often rely on data-dependent approximations (like Nyström methods) or specific structural assumptions (like translation invariance). This paper identifies a gap for a method that is both optimally efficient—using the fewest basis functions possible for a given error—and data-independent, allowing for significant precomputation.

The Karhunen-Loève Framework

The core of the proposed method is the conversion of the GP into its Karhunen-Loève (KL) expansion. This can be viewed 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 first four eigenfunctions $\phi_i(x)$ of a covariance kernel, representing the basis functions used in the KL expansion.

Because these eigenfunctions depend only on the kernel and the domain (e.g., an interval $[a, b]$), they can be precomputed. Once data arrives, the regression problem simplifies to a ridge regression in the "weight space" of these eigenfunctions, which is computationally trivial compared to the original GP formulation.

Algorithmic Innovations

The authors contribute several specific algorithmic improvements to make this framework practical:

  • High-Order Discretization: Using Nyström-based discretization with Gaussian nodes and Legendre polynomials to solve the integral eigenvalue problem with high accuracy.
  • Handling Non-Smooth Kernels: Standard discretization often fails for kernels like the Matérn family, which have "kinks" at the origin. The authors introduce a specialized quadrature scheme that splits the integral to handle these non-smooth points, maintaining super-algebraic convergence.
  • Fast Hyperparameter Tuning: A novel approach for fitting hyperparameters (like length-scale $\ell$) by discretizing the hyperparameter space and using quadrature, avoiding expensive MCMC or gradient-based optimization.

Performance and Results

The efficiency of the reduced-rank approach is driven by the rapid decay of the eigenvalues of the covariance kernel. As shown below, for many common kernels and length-scales, the eigenvalues drop to machine precision very quickly, meaning only a small number of basis functions are required for high-accuracy modeling.

Decay of eigenvalues $\log_{10} \lambda_i$ for different length-scales $\ell$. The rapid decay justifies the use of a low-rank approximation.

In numerical experiments, the method demonstrated remarkable speed and accuracy:

  • Scalability: In 2D regression tasks, the algorithm handled 160,000 data points in approximately 7 seconds on a standard machine.
  • Efficiency: For a squared exponential kernel with a length-scale of 0.1, an accuracy of $10^{-3}$ was achieved using only 25 basis functions.
  • Comparative Advantage: When compared to Laplacian-based approximations (like Hilbert-GP), this method consistently achieved lower error for the same number of basis functions, particularly at smaller length-scales.

Conclusion and Future Work

By leveraging the $L^2$-optimality of the Karhunen-Loève expansion, this framework provides a highly efficient path for GP regression in low dimensions (1D to 3D). While the "curse of dimensionality" remains a challenge for scaling to high-dimensional machine learning tasks, the ability to handle massive datasets with non-smooth kernels in seconds represents a significant advancement for spatial statistics and engineering applications. Future work may explore combining this approach with spatially adaptive trees to address higher-dimensional domains.

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\`eve expansion, the $L^2$-optimal reduced-rank representation. Numerical evaluation of the Karhunen-Lo\`eve 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\`eve 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},
}
Figure