Pre-image calculation for random Fourier feature kernel machines

In this paper we address the pre-image problem for random Fourier feature based kernel machines. Full kernel methods require the calculation of the Gram matrix of scalar products between all training samples. This is not feasible for large sample sizes, and various approximation methods have been proposed previously. Calculation of the inverse transform, known as finding the pre-image, is frequently required, and has been tackled previously for the full kernel approach, but has been less well explored for approximation methods. In this paper we investigate two approaches suitable for finding the pre-image from random Fourier features. The first is a direct adaptation of a learning-based approach to the random features case. This requires the solution of a completely separate optimisation problem, with additional model parameters and a second pass through the data. The second approach only requires solving a single optimisation problem with an augmented vector and a single pass through the data samples. We compare the two methods on four datasets and demonstrate their effectiveness.