2022/10/18 by Philip Greengard, Greengard, Philip, Manas Rachh +3 · 1 citation
Chemistry · Computer Science · Physics and Astronomy · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Numerical Analysis (math.NA) #Scientific Research and Discoveries #Spectroscopy and Chemometric Analyses
paper · pdf · doi:10.48550/arxiv.2210.10210
openalex publication_date 2022/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \mathcal O(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 \mathcal O(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érn 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érn-(3)/(2) regression from N=109 data points to be performed in 2 minutes on a standard desktop, with posterior mean accuracy 10-3. This opens up spatial statistics applications 100 times larger than previously possible.