  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.
