提出首个在一般协方差下有效的组合式稀疏PCA方法。
Combinatorial Sparse PCA Beyond the Spiked Identity Model
- 设计改进的截断幂法，实现对任意协方差矩阵的稀疏主成分恢复。
- 仅需 $s^2 \cdot \mathrm{polylog}(d)$ 样本和 $d^2 \cdot \mathrm{poly}(s, \log d)$ 时间。
- 适用于真实数据与合成数据，突破传统方法对模型的依赖。
稀疏PCA是高维统计中研究最深入的问题之一。给定来自协方差矩阵Σ分布的样本，其最大特征向量v∈R^d是s-稀疏的。现有算法可分为组合类（如对角或元素阈值）与SDP-based类。组合类方法虽简单，但通常仅在脉冲身份模型（Σ = I_d + γvv^⊤）下被分析；而SDP类方法无需额外假设。本文展示标准组合算法在超越脉冲身份模型时的失效反例。为此，我们提出首个可证明在一般Σ下成功的方法：使用 $s^2 \cdot \mathrm{polylog}(d)$ 样本与 $d^2 \cdot \mathrm{poly}(s, \log d)$ 时间，通过改进袁与张（2013）的截断幂法实现全局收敛。我们进一步将该方法推广至恢复稀疏主特征空间中的向量，并在合成与真实数据集上进行了评估。
原文摘要 · Abstract (English)
Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance $Σ$, whose top eigenvector $v \in R^d$ is $s$-sparse. Existing sparse PCA algorithms can be broadly categorized into (1) combinatorial algorithms (e.g., diagonal or elementwise covariance thresholding) and (2) SDP-based algorithms. While combinatorial algorithms are much simpler, they are typically only analyzed under the spiked identity model (where $Σ= I_d + γvv^\top$ for some $γ> 0$), whereas SDP-based algorithms require no additional assumptions on $Σ$. We demonstrate explicit counterexample covariances $Σ$ against the success of standard combinatorial algorithms for sparse PCA, when moving beyond the spiked identity model. In light of this discrepancy, we give the first combinatorial method for sparse PCA that provably succeeds for general $Σ$ using $s^2 \cdot \mathrm{polylog}(d)$ samples and $d^2 \cdot \mathrm{poly}(s, \log(d))$ time, by providing a global convergence guarantee on a variant of the truncated power method of Yuan and Zhang (2013). We provide a natural generalization of our method to recovering a vector in a sparse leading eigenspace. Finally, we evaluate our method on synthetic and real-world sparse PCA datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。