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:
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.
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