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

TL;DR — A new Newton-type optimization algorithm for KL-divergence Nonnegative Matrix Factorization that replaces the standard separable-majorant approach with a second-order Taylor surrogate, improving efficiency while retaining convergence guarantees.

• Targets KL-NMF, the NMF variant best suited to count data (e.g., term-document matrices, images) where samples follow a Poisson distribution.
• Argues that the common approach of minimizing a separable majorant has plateaued, and instead uses the second-order Taylor expansion of the loss for a Newton-type update.
• Minimizes this non-separable surrogate via a generalization of the HALS algorithm, yielding provable convergence.
• Claims competitive-to-favorable performance against state-of-the-art algorithms across a wide range of datasets.