Incomplete Cholesky decomposition based kernel principal component analysis for large-scale data set

Kernel principal component analysis (KPCA) is a popular nonlinear feature extraction method. It generally uses eigen-decomposition technique to extract the principal components. But the method is infeasible for large-scale data set because of the storage and computational problem. To overcome these disadvantages, an efficient iterative method of computing kernel principal components is proposed. First, the Gram matrix is transformed into the two triangular matrices using incomplete Cholesky decomposition. Then each column of the triangular matrix is treated as the input sample for the covariance-free algorithm. Thus, the kernel principal components can be iteratively computed without the eigen-decomposition. The proposed method uses less than half of original storage capacity and also greatly reduces the time complexity. More important, it still can be used even if traditional eigen-decomposition technique cannot be applied when faced with the extremely large-scale data set. The effectiveness of proposed method is validated from experimental results.