Random Fourier Features vs Eigenfunctions for Gaussian Process Kernel Approximations?

Question

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?

Answer 1

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.