Kernel Principal Component Analysis Action Set

To train an exact KPCA model on the input matrix M of size , the full kernel matrix needs to be constructed, and the computationally expensive eigendecomposition operation, with a computational complexity of , must be applied to K. Thus, for large values of n, the exact KPCA method can be very slow. To address this issue, an approximation method called the Nyström method was proposed by Baker (1977). This method is based on sampling from the rows of the input matrix. Instead of applying the eigendecomposition method to the full kernel matrix K, you apply it to a smaller matrix of size , where C is the sampling size.

The sampling scheme is important in the performance of the Nyström method. In Kwok and Tsang (2004), an error analysis is conducted, and the resulting error bound suggests using k-means clustering as the sampling scheme. The greater the number of clusters that are chosen in k-means clustering, the more accurate the reconstruction of K will be. If the number of clusters equals the number of observations, the reconstruction will be exact. In -means clustering, the algorithm for choosing the initial values (or seeds) has significant impact on the centroids that are obtained. The kPca action includes several algorithms for clustering initialization, among them k-means++ (Arthur and Vassilvitskii 2007). Low-rank approximation reduces the memory complexity of KPCA training from to and reduces the computational complexity of kernel PCA from to , where n is the data size and C is the number of clusters.