# Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 45 references that are in the map.
- First posted on arXiv 7 Mar 2022.

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

- [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)
- [Gaussian Processes for Data-Efficient Learning in Robotics and Control](https://mlsanity.com/paper/1502.02860/) (2015)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Probabilistic Numerics and Uncertainty in Computations](https://mlsanity.com/paper/1506.01326/) (2015)
- [Local Gaussian process approximation for large computer experiments](https://mlsanity.com/paper/1303.0383/) (2013)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [A multi-resolution approximation for massive spatial datasets](https://mlsanity.com/paper/1507.04789/) (2015)
- [A theoretical framework for calibration in computer models: parametrization, estimation and convergence properties](https://mlsanity.com/paper/1508.07155/) (2015)
- [Linear-time inference for Gaussian Processes on one dimension](https://mlsanity.com/paper/2003.05554/) (2020)
- [Fast prediction of deterministic functions using sparse grid experimental designs](https://mlsanity.com/paper/1402.6350/) (2014)
- [Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features](https://mlsanity.com/paper/2002.04195/) (2020)
- [Linear-Cost Covariance Functions for Gaussian Random Fields](https://mlsanity.com/paper/1711.05895/) (2017)

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

- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [A spectral mixture representation of isotropic kernels with application to random Fourier features](https://mlsanity.com/paper/2411.02770/) (2024)
- [Representing Additive Gaussian Processes by Sparse Matrices](https://mlsanity.com/paper/2305.00324/) (2023)
- [Privacy-aware Gaussian Process Regression](https://mlsanity.com/paper/2305.16541/) (2023)
- [Beyond State Space Representation: A General Theory for Kernel Packets](https://mlsanity.com/paper/2402.04022/) (2024)
- [Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression](https://mlsanity.com/paper/2403.13300/) (2024)
- [Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner](https://mlsanity.com/paper/2408.00206/) (2024)
- [Aggregation Models with Optimal Weights for Distributed Gaussian Processes](https://mlsanity.com/paper/2408.00955/) (2024)
- [Linear cost and exponentially convergent approximation of Gaussian Mat'ern processes on intervals](https://mlsanity.com/paper/2410.13000/) (2024)
- [KP-PINNs: Kernel Packet Accelerated Physics Informed Neural Networks](https://mlsanity.com/paper/2506.08563/) (2025)

## Abstract (arXiv)

We develop an exact and scalable algorithm for one-dimensional Gaussian process regression with Mat'ern correlations whose smoothness parameter nu is a half-integer. The proposed algorithm only requires O(nu3 n) operations and O(nu n) storage. This leads to a linear-cost solver since nu is chosen to be fixed and usually very small in most applications. The proposed method can be applied to multi-dimensional problems if a full grid or a sparse grid design is used. The proposed method is based on a novel theory for Mat'ern correlation functions. We find that a suitable rearrangement of these correlation functions can produce a compactly supported function, called a "kernel packet". Using a set of kernel packets as basis functions leads to a sparse representation of the covariance matrix that results in the proposed algorithm. Simulation studies show that the proposed algorithm, when applicable, is significantly superior to the existing alternatives in both the computational time and predictive accuracy.