# Intersecting Faces: Non-negative Matrix Factorization With New Guarantees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2015.

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

- [Probabilistic Simplex Component Analysis](https://mlsanity.com/paper/2103.10027/) (2021)
- [Smoothed Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2110.05528/) (2021)
- [Learning Topic Models: Identifiability and Finite-Sample Analysis](https://mlsanity.com/paper/2110.04232/) (2021)
- [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)

## Abstract (arXiv)

Non-negative matrix factorization (NMF) is a natural model of admixture and is widely used in science and engineering. A plethora of algorithms have been developed to tackle NMF, but due to the non-convex nature of the problem, there is little guarantee on how well these methods work. Recently a surge of research have focused on a very restricted class of NMFs, called separable NMF, where provably correct algorithms have been developed. In this paper, we propose the notion of subset-separable NMF, which substantially generalizes the property of separability. We show that subset-separability is a natural necessary condition for the factorization to be unique or to have minimum volume. We developed the Face-Intersect algorithm which provably and efficiently solves subset-separable NMF under natural conditions, and we prove that our algorithm is robust to small noise. We explored the performance of Face-Intersect on simulations and discuss settings where it empirically outperformed the state-of-art methods. Our work is a step towards finding provably correct algorithms that solve large classes of NMF problems.