# Faster Kernel Interpolation for Gaussian Processes

arXiv: https://arxiv.org/abs/2101.11751 · HTML: https://mlsanity.com/paper/2101.11751/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 37 references that are in the map.
- First posted on arXiv 28 Jan 2021.

## Builds on (most cited first, 16 of 16)

- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Process Behaviour in Wide Deep Neural Networks](https://mlsanity.com/paper/1804.11271/) (2018)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Deep Convolutional Networks as shallow Gaussian Processes](https://mlsanity.com/paper/1808.05587/) (2018)
- [Gaussian Process Kernels for Pattern Discovery and Extrapolation](https://mlsanity.com/paper/1302.4245/) (2013)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [A Bayesian Perspective on the Deep Image Prior](https://mlsanity.com/paper/1904.07457/) (2019)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [A Case Study Competition Among Methods for Analyzing Large Spatial Data](https://mlsanity.com/paper/1710.05013/) (2017)
- [Scalable Log Determinants for Gaussian Process Kernel Learning](https://mlsanity.com/paper/1711.03481/) (2017)
- [Product Kernel Interpolation for Scalable Gaussian Processes](https://mlsanity.com/paper/1802.08903/) (2018)
- [Thoughts on Massively Scalable Gaussian Processes](https://mlsanity.com/paper/1511.01870/) (2015)
- [Bayesian and Maximum Likelihood Estimation for Gaussian Processes on an Incomplete Lattice](https://mlsanity.com/paper/1402.4281/) (2014)

## Built on by (most cited first, 5 of 5)

- [Continuous Field Reconstruction from Sparse Observations with Implicit Neural Networks](https://mlsanity.com/paper/2401.11611/) (2024)
- [Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression](https://mlsanity.com/paper/2306.14731/) (2023)
- [Tensor Network-Constrained Kernel Machines as Gaussian Processes](https://mlsanity.com/paper/2403.19500/) (2024)
- [Spatially scalable recursive estimation of Gaussian process terrain maps using local basis functions](https://mlsanity.com/paper/2210.09168/) (2022)
- [Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices](https://mlsanity.com/paper/2408.02346/) (2024)

## Abstract (arXiv)

A key challenge in scaling Gaussian Process (GP) regression to massive datasets is that exact inference requires computation with a dense n x n kernel matrix, where n is the number of data points. Significant work focuses on approximating the kernel matrix via interpolation using a smaller set of m inducing points. Structured kernel interpolation (SKI) is among the most scalable methods: by placing inducing points on a dense grid and using structured matrix algebra, SKI achieves per-iteration time of O(n + m log m) for approximate inference. This linear scaling in n enables inference for very large data sets; however the cost is per-iteration, which remains a limitation for extremely large n. We show that the SKI per-iteration time can be reduced to O(m log m) after a single O(n) time precomputation step by reframing SKI as solving a natural Bayesian linear regression problem with a fixed set of m compact basis functions. With per-iteration complexity independent of the dataset size n for a fixed grid, our method scales to truly massive data sets. We demonstrate speedups in practice for a wide range of m and n and apply the method to GP inference on a three-dimensional weather radar dataset with over 100 million points.