# Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

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

- [OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport](https://mlsanity.com/paper/2403.02372/) (2024)
- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [Block Alternating Bregman Majorization Minimization with Extrapolation](https://mlsanity.com/paper/2107.04395/) (2021)
- [Non-negative matrix factorization algorithms generally improve topic model fits](https://mlsanity.com/paper/2105.13440/) (2021)
- [Semi-supervised Nonnegative Matrix Factorization for Document Classification](https://mlsanity.com/paper/2203.03551/) (2022)
- [A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization](https://mlsanity.com/paper/2303.17992/) (2023)
- [Efficient Algorithms for Regularized Nonnegative Scale-invariant Low-rank Approximation Models](https://mlsanity.com/paper/2403.18517/) (2024)
- [Plastic tensor networks for interpretable generative modeling](https://mlsanity.com/paper/2504.06722/) (2025)
- [Deep Nonnegative Matrix Factorization with Beta Divergences](https://mlsanity.com/paper/2309.08249/) (2023)
- [Block Majorization Minimization with Extrapolation and Application to β-NMF](https://mlsanity.com/paper/2401.06646/) (2024)
- [Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning](https://mlsanity.com/paper/2109.12222/) (2021)
- [Leveraging Joint-Diagonalization in Transform-Learning NMF](https://mlsanity.com/paper/2112.05664/) (2021)
- [Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints](https://mlsanity.com/paper/2201.07657/) (2022)
- [An Unconstrained Symmetric Nonnegative Latent Factor Analysis for Large-scale Undirected Weighted Networks](https://mlsanity.com/paper/2208.04811/) (2022)
- [Efficient algorithms for regularized Poisson Non-negative Matrix Factorization](https://mlsanity.com/paper/2404.16505/) (2024)
- [On the Connection Between Non-negative Matrix Factorization and Latent Dirichlet Allocation](https://mlsanity.com/paper/2405.20542/) (2024)
- [An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2607.13919/) (2026)

## Abstract (arXiv)

Nonnegative matrix factorization (NMF) is a standard linear dimensionality reduction technique for nonnegative data sets. In order to measure the discrepancy between the input data and the low-rank approximation, the Kullback-Leibler (KL) divergence is one of the most widely used objective function for NMF. It corresponds to the maximum likehood estimator when the underlying statistics of the observed data sample follows a Poisson distribution, and KL NMF is particularly meaningful for count data sets, such as documents or images. In this paper, we first collect important properties of the KL objective function that are essential to study the convergence of KL NMF algorithms. Second, together with reviewing existing algorithms for solving KL NMF, we propose three new algorithms that guarantee the non-increasingness of the objective function. We also provide a global convergence guarantee for one of our proposed algorithms. Finally, we conduct extensive numerical experiments to provide a comprehensive picture of the performances of the KL NMF algorithms.