# Sum-of-norms regularized Nonnegative Matrix Factorization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 54 references that are in the map.
- First posted on arXiv 30 Jun 2024.

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

- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Spectral Variability in Hyperspectral Data Unmixing: A Comprehensive Review](https://mlsanity.com/paper/2001.07307/) (2020)
- [Blind Audio Source Separation with Minimum-Volume Beta-Divergence NMF](https://mlsanity.com/paper/1907.02404/) (2019)
- [Algorithms and Comparisons of Non-negative Matrix Factorization with Volume Regularization for Hyperspectral Unmixing](https://mlsanity.com/paper/1903.04362/) (2019)
- [An Efficient Semismooth Newton Based Algorithm for Convex Clustering](https://mlsanity.com/paper/1802.07091/) (2018)
- [Certifying clusters from sum-of-norms clustering](https://mlsanity.com/paper/2006.11355/) (2020)
- [Inhomogeneous graph trend filtering via a l2,0 cardinality penalty](https://mlsanity.com/paper/2304.05223/) (2023)

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

- [Nonnegative matrix factorizations and related compositional models: Equivalence, identifiability, and an application on the grain-size analysis of sediments](https://mlsanity.com/paper/2512.22282/) (2025)
- [Identification of NMF by choosing maximum-volume basis vectors](https://mlsanity.com/paper/2603.24227/) (2026)

## Abstract (arXiv)

When applying nonnegative matrix factorization (NMF), the rank parameter is generally unknown. This rank, called the nonnegative rank, is usually estimated heuristically since computing its exact value is NP-hard. In this work, we propose an approximation method to estimate the rank on-the-fly while solving NMF. We use the sum-of-norm (SON), a group-lasso structure that encourages pairwise similarity, to reduce the rank of a factor matrix when the initial rank is overestimated. On various datasets, SON-NMF can reveal the correct nonnegative rank of the data without prior knowledge or parameter tuning. SON-NMF is a nonconvex, nonsmooth, non-separable, and non-proximable problem, making it nontrivial to solve. First, since rank estimation in NMF is NP-hard, the proposed approach does not benefit from lower computational complexity. Using a graph-theoretic argument, we prove that the complexity of SON-NMF is essentially irreducible. Second, the per-iteration cost of algorithms for SON-NMF can be high. This motivates us to propose a first-order BCD algorithm that approximately solves SON-NMF with low per-iteration cost via the proximal average operator. SON-NMF exhibits favorable features for applications. Besides the ability to automatically estimate the rank from data, SON-NMF can handle rank-deficient data matrices and detect weak components with small energy. Furthermore, in hyperspectral imaging, SON-NMF naturally addresses the issue of spectral variability.