Greedy Orthogonal Pivoting Algorithm for Non-Negative Matrix Factorization

Kai Zhang, Sheng Zhang, Jun Liu, Jun Wang, Jie Zhang
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:7493-7501, 2019.

Abstract

Non-negative matrix factorization is a powerful tool for learning useful representations in the data and has been widely applied in many problems such as data mining and signal processing. Orthogonal NMF, which can improve the locality of decomposition, has drawn considerable interest in solving clustering problems in recent years. However, imposing simultaneous non-negative and orthogonal structure can be quite difficult, and so existing algorithms can only solve it approximately. To address this challenge, we propose an innovative procedure called Greedy Orthogonal Pivoting Algorithm (GOPA). The GOPA algorithm fully exploits the sparsity of non-negative orthogonal solutions to break the global problem into a series of local optimizations, in which an adaptive subset of coordinates are updated in a greedy, closed-form manner. The biggest advantage of GOPA is that it promotes exact orthogonality and provides solid empirical evidence that stronger orthogonality does contribute favorably to better clustering performance. On the other hand, we further design randomized and parallel version of GOPA, which can further reduce the computational cost and improve accuracy, making it suitable for large data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-zhang19r, title = {Greedy Orthogonal Pivoting Algorithm for Non-Negative Matrix Factorization}, author = {Zhang, Kai and Zhang, Sheng and Liu, Jun and Wang, Jun and Zhang, Jie}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {7493--7501}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/zhang19r/zhang19r.pdf}, url = {https://proceedings.mlr.press/v97/zhang19r.html}, abstract = {Non-negative matrix factorization is a powerful tool for learning useful representations in the data and has been widely applied in many problems such as data mining and signal processing. Orthogonal NMF, which can improve the locality of decomposition, has drawn considerable interest in solving clustering problems in recent years. However, imposing simultaneous non-negative and orthogonal structure can be quite difficult, and so existing algorithms can only solve it approximately. To address this challenge, we propose an innovative procedure called Greedy Orthogonal Pivoting Algorithm (GOPA). The GOPA algorithm fully exploits the sparsity of non-negative orthogonal solutions to break the global problem into a series of local optimizations, in which an adaptive subset of coordinates are updated in a greedy, closed-form manner. The biggest advantage of GOPA is that it promotes exact orthogonality and provides solid empirical evidence that stronger orthogonality does contribute favorably to better clustering performance. On the other hand, we further design randomized and parallel version of GOPA, which can further reduce the computational cost and improve accuracy, making it suitable for large data.} }
Endnote
%0 Conference Paper %T Greedy Orthogonal Pivoting Algorithm for Non-Negative Matrix Factorization %A Kai Zhang %A Sheng Zhang %A Jun Liu %A Jun Wang %A Jie Zhang %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-zhang19r %I PMLR %P 7493--7501 %U https://proceedings.mlr.press/v97/zhang19r.html %V 97 %X Non-negative matrix factorization is a powerful tool for learning useful representations in the data and has been widely applied in many problems such as data mining and signal processing. Orthogonal NMF, which can improve the locality of decomposition, has drawn considerable interest in solving clustering problems in recent years. However, imposing simultaneous non-negative and orthogonal structure can be quite difficult, and so existing algorithms can only solve it approximately. To address this challenge, we propose an innovative procedure called Greedy Orthogonal Pivoting Algorithm (GOPA). The GOPA algorithm fully exploits the sparsity of non-negative orthogonal solutions to break the global problem into a series of local optimizations, in which an adaptive subset of coordinates are updated in a greedy, closed-form manner. The biggest advantage of GOPA is that it promotes exact orthogonality and provides solid empirical evidence that stronger orthogonality does contribute favorably to better clustering performance. On the other hand, we further design randomized and parallel version of GOPA, which can further reduce the computational cost and improve accuracy, making it suitable for large data.
APA
Zhang, K., Zhang, S., Liu, J., Wang, J. & Zhang, J.. (2019). Greedy Orthogonal Pivoting Algorithm for Non-Negative Matrix Factorization. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:7493-7501 Available from https://proceedings.mlr.press/v97/zhang19r.html.

Related Material