We introduce a novel algorithm that computes the $k$-sparse principal
component of a positive semidefinite matrix $A$. Our algorithm is combinatorial
and operates by examining a discrete set of special vectors lying in a
low-dimensional eigen-subspace of $A$. We obtain provable approximation
guarantees that depend on the spectral decay profile of the matrix: the faster
the eigenvalue decay, the better the quality of our approximation. For example,
if the eigenvalues of $A$ follow a power-law decay, we obtain a polynomial-time
approximation algorithm for any desired accuracy.
A key algorithmic component of our scheme is a combinatorial feature
elimination step that is provably safe and in practice significantly reduces
the running complexity of our algorithm. We implement our algorithm and test it
on multiple artificial and real data sets. Due to the feature elimination step,
it is possible to perform sparse PCA on data sets consisting of millions of
entries in a few minutes. Our experimental evaluation shows that our scheme is
nearly optimal while finding very sparse vectors. We compare to the prior state
of the art and show that our scheme matches or outperforms previous algorithms
in all tested data sets.

本文介绍了一种计算正半定矩阵的 k - 稀疏主成分的新算法，其通过查看低维度特征子空间中的一组离散特殊向量来实现。该算法的近似保证取决于其特征值分布，这使得其能够在多项式时间内对任意精度进行近似计算，同时几乎能够匹配或优于之前算法在所有测试数据集上的表现。