Kernel PCA with an SVD algo

Question

Suppose that I have a great algo for calculating the SVD and I want to do Kernel PCA. It is possible to first apply the Kernel function to my data and then run the SVD algo on the transformed data?

Answer 1

I think it is possible to approximate the result by using explicit feature mapping followed by standard PCA (which amounts to using SVD to find the eigenvectors of your covariance matrix computed from the mapped feature vectors). The idea is to map your feature vectors to a new feature space such that applying "linear" methods (your standard PCA) on the transformed features will give "equivalent" results as using the "kernel trick" to implicitly map features to a higher dimensional feature space, which is done by the Kernel PCA algorithm.

Explicit feature mapping can be done using the Nystrom method or Monte Carlo approximation of the fourier transform. See the docs for kernel_approximation from scikit-learn and the referenced paper therein here and the example here for more details. In particular, the Monte Carlo sampling method is described here.

In fact, the above "trick" is not just applicable to Kernel PCA but also for other "linear" methods, e.g., linear SVM. That is, you can obtain "similar" results as a "kernelized" machine learning algorithm by doing the feature mapping explicitly (rather than implicitly using the "kernel trick") and use a straight forward linear machine learning algorithm on the mapped features. Note that the results might differ slightly (which is why I said "similar" results) since there is approximation involved in the feature mapping.

The downside to doing things this way is that you now have to tune another parameter - the number of components to map your features to. But as usual, this can be another parameter to be estimated using cross-validation etc.