From Feature Space to Primal Space: KPCA and Its Mixture Model

Kernel principal component analysis (KPCA), as a nonlinear extension to PCA via kernel trick, has received great attention for its extreme usefulness in nonlinear feature extraction and many applications. However, a major drawback of the standard KPCA is that the amount of computation required is of cubic growth with the number of training data points, say $n$, and the space needed to store the kernel matrix is of $n$ square. In this paper, viewing KPCA as a primal space problem with the \\\"samples\\\" created by using incomplete Cholesky decomposition, we show that KPCA is equivalent to performing linear PCA in the primal space using the created \\\"samples\\\". Thus, all the efficient algorithms for PCA can be straightforwardly transformed into KPCA. Particularly, whereas KPCA defines only a global projection of the samples, we extend KPCA to a mixture of local KPCA models by applying the mixture model to probabilistic PCA in the primal space. The theoretical analysis and experimental results on both artificial and real data set have shown the superiority of the proposed methods in terms of computational efficiency and storage space, as well as recognition rate, especially when the number of data points $n$ is large.