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?