使用迭代方法求解核主成分分析

To Solve Kernel Principal Component Analysis Using Iterative Method

核主成分分析方法是使用核方法将经典的线性算法主成分分析推广到高维空间,用来处理复杂非线性数据的一种常用的特征提取算法,该算法首先在高维空间中计算所有样本之间的核矩阵,然后使用特征分解技术计算核矩阵的特征解,其计算的时间和空间复杂度分别为O(m2)和O(m3).然而在大规模数据集的情况下,由于储存和计算的问题无法进行正常的求解.文中提出首先使用幂迭代方法计算核矩阵的高阶特征解,然后重复使用Schur-Weilandt收缩方法分别计算出核矩阵的其它阶特征解.文中算法在计算过程中,不需要像传统的计算方法那样需要事先存储核矩阵,空间复杂度只有O(m).通过在模拟和真实数据的实验结果充分验证了算法的有效性.

Kernel Principal Component Analysis （KPCA） is the generalized algorithm of famous Principal Component Analysis （ PCA）, which uses the kernel method and treats with the complex nonlinear dataset. It firstly computes the kernel matrix between mapped samples in high dimensional space, and uses eigen-decomposition technique to compute the eigen-solution for kernel matrix. The space and time complexity of the KPCA is O（ m2 ） and O（ m3 ） , respectively. When faced with large-scale data set, the method is infeasible for the sake of the storage and computational problem. In this paper, the Power iteration is introduced to compute the highest eigen-solution. Then the Schur-Weilandt deflation is repeatedly applied to achieve other higher order eigenvectors. In the process of computation, the kernel matrix needs not to compute and store in advance. The space complexity of the proposed method is only O （ m ）. The effectiveness of proposed method is validated from experimental results on toy and real dataset.