# Linear-time inference for Gaussian Processes on one dimension

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2020.

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

- [A Probabilistic State Space Model for Joint Inference from Differential Equations and Data](https://mlsanity.com/paper/2103.10153/) (2021)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations](https://mlsanity.com/paper/2203.03116/) (2022)
- [Multi-modal Gaussian Process Variational Autoencoders for Neural and Behavioral Data](https://mlsanity.com/paper/2310.03111/) (2023)
- [CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra](https://mlsanity.com/paper/2309.03060/) (2023)
- [Hida-Mat'ern Kernel](https://mlsanity.com/paper/2107.07098/) (2021)
- [Linear Time GPs for Inferring Latent Trajectories from Neural Spike Trains](https://mlsanity.com/paper/2306.01802/) (2023)
- [Learning Time-Varying Multi-Region Brain Communications via Scalable Markovian Gaussian Processes](https://mlsanity.com/paper/2407.00397/) (2024)
- [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)
- [Modified Bryson-Frazier Smoothing and Hyperparameter Learning for Temporal Gaussian Process Regression](https://mlsanity.com/paper/2608.17595/) (2026)

## Abstract (arXiv)

Gaussian Processes (GPs) provide powerful probabilistic frameworks for interpolation, forecasting, and smoothing, but have been hampered by computational scaling issues. Here we investigate data sampled on one dimension (e.g., a scalar or vector time series sampled at arbitrarily-spaced intervals), for which state-space models are popular due to their linearly-scaling computational costs. It has long been conjectured that state-space models are general, able to approximate any one-dimensional GP. We provide the first general proof of this conjecture, showing that any stationary GP on one dimension with vector-valued observations governed by a Lebesgue-integrable continuous kernel can be approximated to any desired precision using a specifically-chosen state-space model: the Latent Exponentially Generated (LEG) family. This new family offers several advantages compared to the general state-space model: it is always stable (no unbounded growth), the covariance can be computed in closed form, and its parameter space is unconstrained (allowing straightforward estimation via gradient descent). The theorem's proof also draws connections to Spectral Mixture Kernels, providing insight about this popular family of kernels. We develop parallelized algorithms for performing inference and learning in the LEG model, test the algorithm on real and synthetic data, and demonstrate scaling to datasets with billions of samples.