Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence

Abstract

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.

arXiv comment31 pages, Accepted in the Journal of Scientific Computing

References in corpus (5)

• On Tensors, Sparsity, and Nonnegative Factorizations
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Nonnegative Matrix Factorization and I-Divergence Alternating Minimization
• Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation

Cited by in corpus (5)

• Block Alternating Bregman Majorization Minimization with Extrapolation
• Deep Nonnegative Matrix Factorization with Beta Divergences
• Majorization-minimization Bregman proximal gradient algorithms for NMF with the Kullback--Leibler divergence
• Block Majorization Minimization with Extrapolation and Application to $\beta$-NMF
• Leveraging Joint-Diagonalization in Transform-Learning NMF