一个解决大数据集问题的核主成分分析算法-复旦大学.PDFVIP

∗ + ,, (, 200433) An efficient Kernel Principal Component Analysis Algorithm for large-scale data set * + Shi Weiya, Guo Yue-Fei , Xue Xiangyang (Department of Computer Science and Technology, Fudan University, Shanghai 200433, China) + Corresponding author: Phn: +86-21 Fax: +86-21 E-mail: yfguo@, Abstract: Kernel principal component analysis (KPCA) is a popular nonlinear feature extraction method in the field of machine learning. It uses eigen-decomposition technique to extract the principal components. But the method is infeasible for large-scale data set because of the store and computational problem. To overcome these disadvantages, a new covariance-free method of computing kernel principal components is proposed. First, a matrix, called Gram-power matrix, is constructed using the original Gram matrix. It is proven by the theorem of linear algebra that the eigenvectors of newly constructed matrix are the same as the ones of the Gram matrix. Therefore, we can treat each column of the Gram matrix as the input sample for the covariance-free algorithm. Thus, the kernel principle components can be iteratively computed without the eigen-decomposition. The space complexity of proposed method is only , the time complexity is reduced to . The effectiveness of proposed method is validated from experimental results. 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. Key words: KPCA; Gram matrix; large-scale data set; covariance-free; eigen-decomposition : GramGram-power GramGram