Efficient Fourier representations of families of Gaussian processes

We introduce a class of algorithms for constructing Fourier representations of Gaussian processes in $1$ dimension that are valid over ranges of hyperparameter values. The scaling and frequencies of the Fourier basis functions are evaluated numerically via generalized Gaussian quadratures. The representations introduced allow for $O(N\log{N} + m^3)$ inference via the non-uniform FFT where $N$ is the number of data points and $m$ is the number of basis functions. Numerical results are provided for Mat\'ern kernels with $\nu \in [3/2, 7/2]$ and $\rho \in [0.1, 0.5]$. The algorithms of this paper generalize mathematically to higher dimensions, though they suffer from the standard curse of dimensionality.