# Randomized Algorithms for Symmetric Nonnegative Matrix Factorization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 59 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 15 of 15)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Hypergraph Random Walks, Laplacians, and Clustering](https://mlsanity.com/paper/2006.16377/) (2020)
- [Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1811.05642/) (2018)
- [Provable Deterministic Leverage Score Sampling](https://mlsanity.com/paper/1404.1530/) (2014)
- [Lecture Notes on Randomized Linear Algebra](https://mlsanity.com/paper/1608.04481/) (2016)
- [Nonnegative PARAFAC2: a flexible coupling approach](https://mlsanity.com/paper/1802.05035/) (2018)
- [Decomposition of Big Tensors With Low Multilinear Rank](https://mlsanity.com/paper/1412.1885/) (2014)
- [Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1509.01404/) (2015)
- [Hybrid Clustering based on Content and Connection Structure using Joint Nonnegative Matrix Factorization](https://mlsanity.com/paper/1703.09646/) (2017)
- [Compressed Nonnegative Matrix Factorization is Fast and Accurate](https://mlsanity.com/paper/1505.04650/) (2015)
- [MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization](https://mlsanity.com/paper/1609.09154/) (2016)
- [Randomized Nonnegative Matrix Factorization](https://mlsanity.com/paper/1711.02037/) (2017)
- [A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization](https://mlsanity.com/paper/1509.09313/) (2015)
- [Revisiting Approximate Leverage Score Sketching for Matrix Least Squares](https://mlsanity.com/paper/2201.10638/) (2022)
- [WellFactor: Patient Profiling using Integrative Embedding of Healthcare Data](https://mlsanity.com/paper/2312.14129/) (2023)

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

- [Learning nonnegative matrix factorizations from compressed data](https://mlsanity.com/paper/2409.04994/) (2024)
- [A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering](https://mlsanity.com/paper/2606.02887/) (2026)
- [Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization](https://mlsanity.com/paper/2607.24518/) (2026)

## Abstract (arXiv)

Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning that approximates a symmetric matrix with a product of a nonnegative, low-rank matrix and its transpose. To design faster and more scalable algorithms for SymNMF we develop two randomized algorithms for its computation. The first algorithm uses randomized matrix sketching to compute an initial low-rank approximation to the input matrix and proceeds to rapidly compute a SymNMF of the approximation. The second algorithm uses randomized leverage score sampling to approximately solve constrained least squares problems. Many successful methods for SymNMF rely on (approximately) solving sequences of constrained least squares problems. We prove theoretically that leverage score sampling can approximately solve nonnegative least squares problems to a chosen accuracy with high probability. Additionally, we prove sampling complexity results for previously proposed hybrid sampling techniques which deterministically include high leverage score rows. This hybrid scheme is crucial for obtaining speeds ups in practice. Finally we demonstrate that both methods work well in practice by applying them to graph clustering tasks on large real world data sets. These experiments show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.