Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization

Abhishek Kumar, Vikas Sindhwani, Prabhanjan Kambadur
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):231-239, 2013.

Abstract

The separability assumption (Arora et al., 2012; Donoho & Stodden, 2003) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several favorable properties in relation to existing methods. A parallel implementation of our algorithm scales excellently on shared and distributed-memory machines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-kumar13b, title = {Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization}, author = {Kumar, Abhishek and Sindhwani, Vikas and Kambadur, Prabhanjan}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {231--239}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/kumar13b.pdf}, url = {https://proceedings.mlr.press/v28/kumar13b.html}, abstract = {The separability assumption (Arora et al., 2012; Donoho & Stodden, 2003) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several favorable properties in relation to existing methods. A parallel implementation of our algorithm scales excellently on shared and distributed-memory machines.} }
Endnote
%0 Conference Paper %T Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization %A Abhishek Kumar %A Vikas Sindhwani %A Prabhanjan Kambadur %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-kumar13b %I PMLR %P 231--239 %U https://proceedings.mlr.press/v28/kumar13b.html %V 28 %N 1 %X The separability assumption (Arora et al., 2012; Donoho & Stodden, 2003) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several favorable properties in relation to existing methods. A parallel implementation of our algorithm scales excellently on shared and distributed-memory machines.
RIS
TY - CPAPER TI - Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization AU - Abhishek Kumar AU - Vikas Sindhwani AU - Prabhanjan Kambadur BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-kumar13b PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 231 EP - 239 L1 - http://proceedings.mlr.press/v28/kumar13b.pdf UR - https://proceedings.mlr.press/v28/kumar13b.html AB - The separability assumption (Arora et al., 2012; Donoho & Stodden, 2003) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several favorable properties in relation to existing methods. A parallel implementation of our algorithm scales excellently on shared and distributed-memory machines. ER -
APA
Kumar, A., Sindhwani, V. & Kambadur, P.. (2013). Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):231-239 Available from https://proceedings.mlr.press/v28/kumar13b.html.

Related Material