# Primal-Dual Algorithms for Non-negative Matrix Factorization with the Kullback-Leibler Divergence

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

## Key facts

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

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

- [Expanding boundaries of Gap Safe screening](https://mlsanity.com/paper/2102.10846/) (2021)
- [Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning](https://mlsanity.com/paper/2109.12222/) (2021)
- [Efficient algorithms for regularized Poisson Non-negative Matrix Factorization](https://mlsanity.com/paper/2404.16505/) (2024)
- [An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2607.13919/) (2026)

## Abstract (arXiv)

Non-negative matrix factorization (NMF) approximates a given matrix as a product of two non-negative matrices. Multiplicative algorithms deliver reliable results, but they show slow convergence for high-dimensional data and may be stuck away from local minima. Gradient descent methods have better behavior, but only apply to smooth losses such as the least-squares loss. In this article, we propose a first-order primal-dual algorithm for non-negative decomposition problems (where one factor is fixed) with the KL divergence, based on the Chambolle-Pock algorithm. All required computations may be obtained in closed form and we provide an efficient heuristic way to select step-sizes. By using alternating optimization, our algorithm readily extends to NMF and, on synthetic examples, face recognition or music source separation datasets, it is either faster than existing algorithms, or leads to improved local optima, or both.