Nonnegative Sparse PCA with Provable Guarantees

Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros Dimakis
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1728-1736, 2014.

Abstract

We introduce a novel algorithm to compute nonnegative sparse principal components of positive 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 approximation quality. If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonnegative sparse PCA within any accuracy εin time polynomial in the matrix size n and desired sparsity k, but not in 1/ε. Further, we obtain 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 previous state of the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-asteris14, title = {Nonnegative Sparse PCA with Provable Guarantees}, author = {Asteris, Megasthenis and Papailiopoulos, Dimitris and Dimakis, Alexandros}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1728--1736}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/asteris14.pdf}, url = {https://proceedings.mlr.press/v32/asteris14.html}, abstract = {We introduce a novel algorithm to compute nonnegative sparse principal components of positive 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 approximation quality. If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonnegative sparse PCA within any accuracy εin time polynomial in the matrix size n and desired sparsity k, but not in 1/ε. Further, we obtain 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 previous state of the art.} }
Endnote
%0 Conference Paper %T Nonnegative Sparse PCA with Provable Guarantees %A Megasthenis Asteris %A Dimitris Papailiopoulos %A Alexandros Dimakis %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-asteris14 %I PMLR %P 1728--1736 %U https://proceedings.mlr.press/v32/asteris14.html %V 32 %N 2 %X We introduce a novel algorithm to compute nonnegative sparse principal components of positive 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 approximation quality. If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonnegative sparse PCA within any accuracy εin time polynomial in the matrix size n and desired sparsity k, but not in 1/ε. Further, we obtain 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 previous state of the art.
RIS
TY - CPAPER TI - Nonnegative Sparse PCA with Provable Guarantees AU - Megasthenis Asteris AU - Dimitris Papailiopoulos AU - Alexandros Dimakis BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-asteris14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1728 EP - 1736 L1 - http://proceedings.mlr.press/v32/asteris14.pdf UR - https://proceedings.mlr.press/v32/asteris14.html AB - We introduce a novel algorithm to compute nonnegative sparse principal components of positive 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 approximation quality. If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonnegative sparse PCA within any accuracy εin time polynomial in the matrix size n and desired sparsity k, but not in 1/ε. Further, we obtain 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 previous state of the art. ER -
APA
Asteris, M., Papailiopoulos, D. & Dimakis, A.. (2014). Nonnegative Sparse PCA with Provable Guarantees. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1728-1736 Available from https://proceedings.mlr.press/v32/asteris14.html.

Related Material