Computational and space complexity analysis of SubXPCA

摘要

Principal Component Analysis (PCA) is one of the well-known linear dimensionality reduction techniques in the literature. Large computational requirements of PCA and its insensitivity to ‘local’ variations in patterns motivated to propose partitional based PCA approaches. It is also observed that these partitioning methods are incapable of extracting ‘global’ information in patterns thus showing lower dimensionality reduction. To alleviate the problems faced by PCA and the partitioning based PCA methods, SubXPCA was proposed to extract principal components with global and local information. In this paper, we prove analytically that (i) SubXPCA shows its computational efficiency up to a factor of k (k≥2) as compared to PCA and competitive to an existing partitioning based PCA method (SubPCA), (ii) SubXPCA shows much lower classification time as compared to SubPCA method, (iii) SubXPCA and SubPCA outperform PCA by a factor up to k (k≥2) in terms of space complexity. The effectiveness of SubXPCA is demonstrated upon a UCI data set and ORL face data.