# An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 51 references that are in the map.
- First posted on arXiv 15 Jul 2026.

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

- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2010.01935/) (2020)
- [Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation](https://mlsanity.com/paper/1805.06604/) (2018)
- [Composite Self-Concordant Minimization](https://mlsanity.com/paper/1308.2867/) (2013)
- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Primal-Dual Algorithms for Non-negative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/1412.1788/) (2014)
- [A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization](https://mlsanity.com/paper/2303.17992/) (2023)
- [Block Majorization Minimization with Extrapolation and Application to β-NMF](https://mlsanity.com/paper/2401.06646/) (2024)
- [An Exterior Method for Nonnegative Matrix Factorization](https://mlsanity.com/paper/2605.19325/) (2026)

## Abstract (arXiv)

Nonnegative Matrix Factorization (NMF) is a fundamental tool in unsupervised learning, which approximates a nonnegative matrix by the product of two low-rank nonnegative factors. The Kullback-Leibler (KL) divergence is best suited to measure the data to model discrepancy when the decomposed data sample follows a Poisson distribution, which is the case for count datasets such as term-document matrices or images. Most KL-NMF algorithms in the literature minimize a separable majorant of the loss to find their next iterate. We argue that this method has reached its limits and propose to use instead the second-order Taylor expansion of the loss, leading to a Newton-type method. We minimize this non-separable surrogate by proposing a generalization of the well-known HALS algorithm. This yields an efficient KL-NMF algorithm which provably converges and which competes favorably with state-of-the-art algorithms on a large variety of datasets.