# Approximation Algorithms for Orthogonal Non-negative Matrix Factorization

arXiv: https://arxiv.org/abs/2103.01398 · HTML: https://mlsanity.com/paper/2103.01398/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2021.

## Built on by (most cited first, 2 of 2)

- [Nonnegative Matrix Factorization in Dimensionality Reduction: A Survey](https://mlsanity.com/paper/2405.03615/) (2024)
- [Orthogonal Nonnegative Matrix Factorization with Sparsity Constraints](https://mlsanity.com/paper/2210.02672/) (2022)

## Abstract (arXiv)

In the non-negative matrix factorization (NMF) problem, the input is an m× n matrix M with non-negative entries and the goal is to factorize it as M≈ AW. The m× k matrix A and the k× 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).