Equispaced Fourier representations for efficient Gaussian process regression from a billion data points

Understand

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\times M$ system matrix with Toeplitz structure, which can thus be applied to a vector in ${\mathcal O}(M \log{M})$ 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 \log{M})$ operations using nonuniform FFTs.