# Random Fourier Features vs Eigenfunctions for Gaussian Process Kernel Approximations?

Say we define kernels in Gaussian processes. There are two approaches to approximating them: random fourier features and eigenfunctions of the kernel. What are the tradeoffs to using each?

If we compute the posterior mean given some samples, this requires inverting the full covariance matrix plus the scaled identity matrix over the data computed via the kernel function: an $$O(n^3)$$ operation, where $$n$$ is the number of data points. Using random Fourier features lets us avoid that and makes the inversion an $$O(l^3)$$ operation, where $$l$$ is the number of Fourier features. This is a large improvement. This approach is taken in the machine learning community.

However, an alternative to random fourier features would be to compute a finite number of eigenvalues and eigenfunctions for the kernel, and then estimate the principal components for the eigenfunctions. We could then approximate the realization of the stochastic process similarly as a weighted sum of basis functions, but the basis functions would not be random Fourier features: they would be the eigenfunctions of the kernel. This is the approach taken in functional data analysis.

What are the advantages of using one approach vs the other? Is one of them faster/more accurate/more general?

• I think there is also some in between methods where you effectively learn the random features. Basically I think rnadom features is just super fast because you need to "do nothing" just rely on Jonhson Lindenstrauss or something like that. Oct 5, 2021 at 13:19

I think what you described as the 'eigenfunction' approach is popularly known as 'Nystrom's method' in machine learning community. Basically, it is a data dependent approach to kernel approximation where we randomly sample a subset of training examples and construct an approximate low-rank kernel matrix. The feature maps for each input are obtained via eigen-decomposition of this low rank matrix matrix. This is a nice paper that provides a theoretical and empirical comparison of the two approaches i.e. random fourier features (RFF) versus Nystrom's method. Essentially, the summary of the paper is that the Nystrom's method has better generalization performance than RFFs when there is a large gap in the eigen-spectrum of the kernel matrix.

Update: The eigenfunction approach is not exactly the same as Nystrom's method. Please see OP's comment on this post.

• Thanks, yeah that's helpful and exactly the kind of tradeoff I was looking for. Note that the eigenfunction approach and the Nystrom method are not exactly the same thing. The Nystrom method can be used to approximately solve for eigenpairs, but can also be applied to other problems. Similarly there might be other ways to approximately/exactly solve for eigenpairs than the Nystrom method. Aug 5, 2020 at 14:52