# Kernel Interpolation with Sparse Grids

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 23 May 2023.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Product Kernel Interpolation for Scalable Gaussian Processes](https://mlsanity.com/paper/1802.08903/) (2018)
- [Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition](https://mlsanity.com/paper/1710.07324/) (2017)
- [Gaussian Quadrature for Kernel Features](https://mlsanity.com/paper/1709.02605/) (2017)
- [SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes](https://mlsanity.com/paper/2106.06695/) (2021)
- [Fast prediction of deterministic functions using sparse grid experimental designs](https://mlsanity.com/paper/1402.6350/) (2014)

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

- [Privacy-aware Gaussian Process Regression](https://mlsanity.com/paper/2305.16541/) (2023)
- [Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner](https://mlsanity.com/paper/2408.00206/) (2024)

## Abstract (arXiv)

Structured kernel interpolation (SKI) accelerates Gaussian process (GP) inference by interpolating the kernel covariance function using a dense grid of inducing points, whose corresponding kernel matrix is highly structured and thus amenable to fast linear algebra. Unfortunately, SKI scales poorly in the dimension of the input points, since the dense grid size grows exponentially with the dimension. To mitigate this issue, we propose the use of sparse grids within the SKI framework. These grids enable accurate interpolation, but with a number of points growing more slowly with dimension. We contribute a novel nearly linear time matrix-vector multiplication algorithm for the sparse grid kernel matrix. Next, we describe how sparse grids can be combined with an efficient interpolation scheme based on simplices. With these changes, we demonstrate that SKI can be scaled to higher dimensions while maintaining accuracy.