论文标题
固定矩阵上的稀疏PCA
Sparse PCA on fixed-rank matrices
论文作者
论文摘要
稀疏PCA是从PCA获得的优化问题，通过对主组件添加稀疏性约束。稀疏的PCA是NP-硬的，即使在单一组件情况下也很难近似。在本文中，我们解决了稀疏PCA相对于协方差矩阵等级的计算复杂性。我们表明，如果协方差矩阵的等级是固定值，则有一种算法将稀疏的PCA求解到全局最优性，其运行时间在功能数量上是多项式。我们还证明了稀疏PCA版本的结果类似，该版本要求主要组件具有不相交的支持。
Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the number of features. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.
