  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 quadratures. The
representations introduced allow for $O(m^3)$ inference, independent of $N$,
for all hyperparameters in the user-specified range after $O(N + m^2\log{m})$
precomputation where $N$, the number of data points, is usually significantly
larger than $m$, the number of basis functions. Inference independent of $N$
for various hyperparameters is facilitated by generalized quadratures, and the
$O(N + m^2\log{m})$ precomputation is achieved with the non-uniform FFT.
Numerical results are provided for Mat\'ern kernels with $\nu \in [3/2, 7/2]$
and lengthscale $\rho \in [0.1, 0.5]$ and squared-exponential kernels with
lengthscale $\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.
