Nonnegative Sparse PCA with Provable Guarantees

Abstract

We introduce a novel algorithm to compute non-negative sparse principal components of posi-tive semidefinite (PSD) matrices. Our algorithm comes with approximation guarantees contingent on the spectral profile of the input matrix A: the sharper the eigenvalue decay, the better the qual-ity of the approximation. If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonneg-ative sparse PCA within any accuracy ✏ in time polynomial in the matrix dimension n and de-sired sparsity k, but not in 1/✏. Further, we ob-tain a data dependent bound that is computed by executing an algorithm on a given data set. This bound is significantly tighter than a-priori bounds and can be used to show that for all tested datasets our algorithm is provably within 40% 90 % from the unknown optimum. Our algorithm is combinatorial and explores a subspace defined by the leading eigenvectors of A. We test our scheme on several data sets, showing that it matches or outperforms the pre-vious state of the art. 1.