提出一种随机化算法求解稀疏PCA，性能有理论保证且实测有效。
A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
- 基于SDP松弛解构造确定性和随机解，选最优者作为结果。
- 在高概率下近似比不超过稀疏常数，平均近似比为O(log d)。
- 适用于需要高效降维的高维数据场景，尤其适合稀疏结构明显的数据。
稀疏主成分分析（SPCA）是重要的降维技术，但属于NP难问题。本文提出一种基于基本半定规划（SDP）松弛的随机化近似算法。该算法利用（近似）SDP解，生成一个确定性稀疏解和多个随机解，并输出其中最优者。若运行足够多次，算法在高概率下具有不超过稀疏常数的近似比。在一项技术假设下（该假设在数值实验中始终成立），平均近似比也受限于$\mathcal{O}(\log{d})$，其中$d$为特征数。我们证明，当SDP解为低秩或特征值呈指数衰减时，该假设成立，并给出了两类满足此条件的实例。此外，在推广的尖峰威沙特协方差模型中，算法中的确定性解能达到近优近似比。通过真实数据集上的数值测试，验证了算法的有效性。
原文摘要 · Abstract (English)
Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm takes an (approximate) SDP solution, constructs one deterministic sparse solution and several randomized solutions, and outputs the best among them. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a technical assumption, which is consistently satisfied in our numerical tests, the average approximation ratio is also bounded by $\mathcal{O}(\log{d})$, where $d$ is the number of features. We show that this technical assumption is satisfied if the SDP solution is low-rank, or has exponentially decaying eigenvalues. We then present two classes of instances for which this technical assumption holds. We also demonstrate that in a covariance model, which generalizes the spiked Wishart model, the deterministic solution in our algorithm achieves a near-optimal approximation ratio. We demonstrate the efficacy of our algorithm through numerical tests on real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。