  Nonnegative matrix factorization is the following problem: given a
nonnegative input matrix $V$ and a factorization rank $K$, compute two
nonnegative matrices, $W$ with $K$ columns and $H$ with $K$ rows, such that
$WH$ approximates $V$ as well as possible. In this paper, we propose two new
approaches for computing high-quality NMF solutions using conic optimization.
These approaches rely on the same two steps. First, we reformulate 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. Then, 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 prove
that our approaches reach a stationary point with an accuracy decreasing as
$\mathcal{O}(\frac{1}{i})$, where $i$ denotes the iteration number. To the best
of our knowledge, our analysis is the first to provide a convergence rate to
stationary points for NMF. Furthermore, in the particular cases of rank-one
factorizations (that is, $K=1$), we show that one of our formulations can be
expressed as a convex optimization problem implying that optimal rank-one
approximations can be computed efficiently. Finally, we show on several
numerical examples that our approaches are able to frequently compute exact
NMFs (that is, with $V = WH$), and compete favorably with the state of the art.
