Papers › Equispaced Fourier representations for efficient Gaussian process regression from a...
Equispaced Fourier representations for efficient Gaussian process regression from a billion data points
Philip Greengard, Manas Rachh, Alex Barnett
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We introduce a Fourier-based fast algorithm for Gaussian process regression in low dimensions. It approximates a translationally-invariant covariance kernel by complex exponentials on an equispaced Cartesian frequency grid of M nodes. This results in a weight-space M×M system matrix with Toeplitz structure, which can thus be applied to a vector in 𝒪(M logM) operations via the fast Fourier transform (FFT), independent of the number of data points N. The linear system can be set up in 𝒪(N + M logM) operations using nonuniform FFTs. This enables efficient massive-scale regression via an iterative solver, even for kernels with fat-tailed spectral densities (large M). We provide bounds on both kernel approximation and posterior mean errors. Numerical experiments for squared-exponential and Mat\'ern kernels in one, two and three dimensions often show 1-2 orders of magnitude acceleration over state-of-the-art rank-structured solvers at comparable accuracy. Our method allows 2D Mat\'ern-$\mbox{$\frac{3}{2}$}$ regression from N=10⁹ data points to be performed in 2 minutes on a standard desktop, with posterior mean accuracy 10⁻³. This opens up spatial statistics applications 100 times larger than previously possible.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections