Approximation Algorithms for Orthogonal Non-negative Matrix Factorization |
In the non-negative matrix factorization (NMF) problem, the input is an $m\times n$ matrix $M$ with non-negative entries and the goal is to factorize it as $M\approx AW$. The $m\times k$ matrix $A$ and the $k\times n$ matrix $W$ are both constrained to have non-negative entries. This is in contrast to singular value decomposition, where the matrices $A$ and $W$ can have negative entries but must satisfy the orthogonality constraint: the columns of $A$ are orthogonal and the rows of $W$ are also orthogonal. The orthogonal non-negative matrix factorization (ONMF) problem imposes both the non-negativity and the orthogonality constraints, and previous work showed that it leads to better performances than NMF on many clustering tasks. We give the first constant-factor approximation algorithm for ONMF when one or both of $A$ and $W$ are subject to the orthogonality constraint. We also show an interesting connection to the correlation clustering problem on bipartite graphs. Our experiments on synthetic and real-world data show that our algorithm achieves similar or smaller errors compared to previous ONMF algorithms while ensuring perfect orthogonality (many previous algorithms do not satisfy the hard orthogonality constraint). |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
charikar21a |
0 |
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization |
2728 |
2736 |
2728-2736 |
2728 |
false |
Charikar, Moses and Hu, Lunjia |
| given |
family |
Moses |
Charikar |
|
|
|
2021-03-18 |
|
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics |
130 |
inproceedings |
|
|
| label |
link |
Supplementary ZIP |
|
|
|