Sparse PCA through Lowrank Approximations

30th International Conference on Machine Learning

Dimitris S. Papailiopoulos [e-mail] ; Department of Electrical and Computer Engineering ; the University of Texas at Austin ; TX ; USA

PID  :  118322

来源: CEUR

【 摘 要 】

We introduce a novel algorithm that com putes the ksparse principal component of a positive semidefinite matrix A. Our algo rithm is combinatorial and operates by ex amining a discrete set of special vectors ly ing in a lowdimensional eigensubspace of A. We obtain provable approximation guar antees that depend on the spectral 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 powerlaw decay, we obtain a polynomial time approximation algorithm for any desired accuracy. We implement our algorithm and test it on multiple artificial and real data sets. Due to a feature elimination step, it is possi ble to perform sparse PCA on data sets con sisting 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