# Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 5 Aug 2024.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Scalable Variational Gaussian Process Classification](https://mlsanity.com/paper/1411.2005/) (2014)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Hilbert Space Methods for Reduced-Rank Gaussian Process Regression](https://mlsanity.com/paper/1401.5508/) (2014)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [Sparse Gaussian Processes with Spherical Harmonic Features](https://mlsanity.com/paper/2006.16649/) (2020)
- [Modeling and interpolation of the ambient magnetic field by Gaussian processes](https://mlsanity.com/paper/1509.04634/) (2015)
- [Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition](https://mlsanity.com/paper/1710.07324/) (2017)
- [Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming](https://mlsanity.com/paper/2004.11408/) (2020)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [Quadrature-based features for kernel approximation](https://mlsanity.com/paper/1802.03832/) (2018)
- [Gaussian Quadrature for Kernel Features](https://mlsanity.com/paper/1709.02605/) (2017)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Computationally Efficient Bayesian Learning of Gaussian Process State Space Models](https://mlsanity.com/paper/1506.02267/) (2015)
- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [Parallelized Tensor Train Learning of Polynomial Classifiers](https://mlsanity.com/paper/1612.06505/) (2016)
- [The SPDE approach for Gaussian and non-Gaussian fields: 10 years and still running](https://mlsanity.com/paper/2111.01084/) (2021)
- [Scalable Magnetic Field SLAM in 3D Using Gaussian Process Maps](https://mlsanity.com/paper/1804.01926/) (2018)
- [Online Joint State Inference and Learning of Partially Unknown State-Space Models](https://mlsanity.com/paper/2102.07418/) (2021)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)
- [Faster Kernel Interpolation for Gaussian Processes](https://mlsanity.com/paper/2101.11751/) (2021)
- [Distributed multi-agent magnetic field norm SLAM with Gaussian processes](https://mlsanity.com/paper/2310.19400/) (2023)

## Abstract (arXiv)

The Hilbert-space Gaussian Process (HGP) approach offers a hyperparameter-independent basis function approximation for speeding up Gaussian Process (GP) inference by projecting the GP onto M basis functions. These properties result in a favorable data-independent O(M3) computational complexity during hyperparameter optimization but require a dominating one-time precomputation of the precision matrix costing O(NM2) operations. In this paper, we lower this dominating computational complexity to O(NM) with no additional approximations. We can do this because we realize that the precision matrix can be split into a sum of Hankel-Toeplitz matrices, each having O(M) unique entries. Based on this realization we propose computing only these unique entries at O(NM) costs. Further, we develop two theorems that prescribe sufficient conditions for the complexity reduction to hold generally for a wide range of other approximate GP models, such as the Variational Fourier Feature (VFF) approach. The two theorems do this with no assumptions on the data and no additional approximations of the GP models themselves. Thus, our contribution provides a pure speed-up of several existing, widely used, GP approximations, without further approximations.