# A Provably-Correct and Robust Convex Model for Smooth Separable NMF

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 44 references that are in the map.
- First posted on arXiv 10 Nov 2025.

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

- [Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications](https://mlsanity.com/paper/1803.01257/) (2018)
- [Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms](https://mlsanity.com/paper/2007.11446/) (2020)
- [Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization](https://mlsanity.com/paper/1708.02883/) (2017)
- [Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization](https://mlsanity.com/paper/1302.4385/) (2013)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary](https://mlsanity.com/paper/1610.01349/) (2016)
- [Probabilistic Simplex Component Analysis](https://mlsanity.com/paper/2103.10027/) (2021)
- [Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing](https://mlsanity.com/paper/1904.06738/) (2019)
- [Smoothed Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2110.05528/) (2021)
- [On the Robustness of the Successive Projection Algorithm](https://mlsanity.com/paper/2411.16195/) (2024)
- [Endmember Extraction from Hyperspectral Images Using Self-Dictionary Approach with Linear Programming](https://mlsanity.com/paper/2404.13098/) (2024)

## Abstract (arXiv)

Nonnegative matrix factorization (NMF) is a linear dimensionality reduction technique for nonnegative data, with applications such as hyperspectral unmixing and topic modeling. NMF is a difficult problem in general (NP-hard), and its solutions are typically not unique. To address these two issues, additional constraints or assumptions are often used. In particular, separability assumes that the basis vectors in the NMF are equal to some columns of the input matrix. In that case, the problem is referred to as separable NMF (SNMF) and can be solved in polynomial-time with robustness guarantees, while identifying a unique solution. However, in real-world scenarios, due to noise or variability, multiple data points may lie near the basis vectors, which SNMF does not leverage. In this work, we rely on the smooth separability assumption, which assumes that each basis vector is close to multiple data points. We explore the properties of the corresponding problem, referred to as smooth SNMF (SSNMF), and examine how it relates to SNMF and orthogonal NMF. We then propose a convex model for SSNMF and show that it provably recovers the sought-after factors, even in the presence of noise. We finally adapt an existing fast gradient method to solve this convex model for SSNMF, and show that it compares favorably with state-of-the-art methods on both synthetic and hyperspectral datasets.