A Geometric Algorithm for Contrastive Principal Component Analysis in High Dimension
提出一种几何曲线搜索算法，将对比主成分分析的时间复杂度从O((n∨m)p²)降至O((n∨m)pr)，空间复杂度从O(p²)降至O((n∨m)p)，适用于高维数据场景。
Principal component analysis (PCA) has been widely used in exploratory data analysis. Contrastive PCA (Abid et al.), a generalized method of PCA, is a new tool used to capture features of a target dataset relative to a background dataset while preserving the maximum amount of information contained in the data. With high dimensional data, contrastive PCA becomes impractical due to its high computational requirement of forming the contrastive covariance matrix and associated eigenvalue decomposition for extracting leading components. In this article, we propose a geometric curvilinear-search method to solve this problem and provide a convergence analysis. Our approach offers significant computational efficiencies. Specifically, it reduces the time complexity from O((n∨m)p2) to a more manageable O((n∨m)pr), where n, m are the sample sizes of the target data and background data, respectively, p is the data dimension and r is the number of leading components. Additionally, we streamline the space complexity from O(p2), necessary for storing the contrastive covariance matrix, to a more economical O((n∨m)p), sufficient for storing the data alone. Numerical examples are presented to show the merits of the proposed algorithm. Supplementary materials for this article are available online.