Exact Nonnegative Matrix Factorization via Conic Optimization

Valentin Leplat, Yurii Nesterov, Nicolas Gillis, François Glineur

Published 2021-05-28Version 1

In this paper, we present two new approaches for computing exact nonnegative matrix factorizations (NMFs). Exact NMF can be defined as follows: given an input nonnegative matrix $V \in \mathbb{R}_+^{F \times N}$ and a factorization rank $K$, compute, if possible, two nonnegative matrices, $W \in \mathbb{R}_+^{F \times K}$ and $H \in \mathbb{R}_+^{K \times N}$, such that $V=WH$. The two proposed approaches to tackle exact NMF, which is NP-hard in general, rely on the same two steps. First, we reformulate exact NMF as minimizing a concave function over a product of convex cones; one approach is based on the exponential cone, and the other on the second-order cone. Second, we solve these reformulations iteratively: at each step, we minimize exactly, over the feasible set, a majorization of the objective functions obtained via linearization at the current iterate. Hence these subproblems are convex conic programs and can be solved efficiently using dedicated algorithms. We show that our approaches, which we call successive conic convex approximations, are able to compute exact NMFs, and compete favorably with the state of the art when applied to several classes of nonnegative matrices; namely, randomly generated, infinite rigid and slack matrices.