# Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2018.

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

- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Nonnegative Matrix Factorization in Dimensionality Reduction: A Survey](https://mlsanity.com/paper/2405.03615/) (2024)
- [A Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2301.10499/) (2023)
- [Symmetric Sparse Boolean Matrix Factorization and Applications](https://mlsanity.com/paper/2102.01570/) (2021)
- [Self-supervised Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2103.01689/) (2021)
- [Rethinking Symmetric Matrix Factorization: A More General and Better Clustering Perspective](https://mlsanity.com/paper/2209.02528/) (2022)
- [Randomized Algorithms for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2402.08134/) (2024)
- [Spherical Matrix Factorization](https://mlsanity.com/paper/2111.14536/) (2021)
- [SymNMF-Net for The Symmetric NMF Problem](https://mlsanity.com/paper/2205.13214/) (2022)
- [An Efficient Alternating Algorithm for ReLU-based Symmetric Matrix Decomposition](https://mlsanity.com/paper/2503.16846/) (2025)
- [Exact Sparse Orthogonal Dictionary Learning](https://mlsanity.com/paper/2103.09085/) (2021)
- [Robust Principal Component Analysis: A Construction Error Minimization Perspective](https://mlsanity.com/paper/2111.12132/) (2021)
- [Second-order Symmetric Non-negative Latent Factor Analysis](https://mlsanity.com/paper/2203.02088/) (2022)
- [A Constraints Fusion-induced Symmetric Nonnegative Matrix Factorization Approach for Community Detection](https://mlsanity.com/paper/2302.12114/) (2023)
- [On subdifferential chain rule of matrix factorization and beyond](https://mlsanity.com/paper/2410.05022/) (2024)
- [Symmetry Nonnegative Matrix Factorization Algorithm Based on Self-paced Learning](https://mlsanity.com/paper/2410.15306/) (2024)
- [A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering](https://mlsanity.com/paper/2606.02887/) (2026)

## Abstract (arXiv)

Symmetric nonnegative matrix factorization (NMF), a special but important class of the general NMF, is demonstrated to be useful for data analysis and in particular for various clustering tasks. Unfortunately, designing fast algorithms for Symmetric NMF is not as easy as for the nonsymmetric counterpart, the latter admitting the splitting property that allows efficient alternating-type algorithms. To overcome this issue, we transfer the symmetric NMF to a nonsymmetric one, then we can adopt the idea from the state-of-the-art algorithms for nonsymmetric NMF to design fast algorithms solving symmetric NMF. We rigorously establish that solving nonsymmetric reformulation returns a solution for symmetric NMF and then apply fast alternating based algorithms for the corresponding reformulated problem. Furthermore, we show these fast algorithms admit strong convergence guarantee in the sense that the generated sequence is convergent at least at a sublinear rate and it converges globally to a critical point of the symmetric NMF. We conduct experiments on both synthetic data and image clustering to support our result.