Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization
  Given a matrix $M$ (not necessarily nonnegative) and a factorization rank
$r$, semi-nonnegative matrix factorization (semi-NMF) looks for a matrix $U$
with $r$ columns and a nonnegative matrix $V$ with $r$ rows such that $UV$ is
the best possible approximation of $M$ according to some metric. In this paper,
we study the properties of semi-NMF from which we develop exact and heuristic
algorithms. Our contribution is threefold. First, we prove that the error of a
semi-NMF of rank $r$ has to be smaller than the best unconstrained
approximation of rank $r-1$. This leads us to a new initialization procedure
based on the singular value decomposition (SVD) with a guarantee on the quality
of the approximation. Second, we propose an exact algorithm (that is, an
algorithm that finds an optimal solution), also based on the SVD, for a certain
class of matrices (including nonnegative irreducible matrices) from which we
derive an initialization for matrices not belonging to that class. Numerical
experiments illustrate that this second approach performs extremely well, and
allows us to compute optimal semi-NMF decompositions in many situations.
Finally, we analyze the computational complexity of semi-NMF proving its
NP-hardness, already in the rank-one case (that is, for $r = 1$), and we show
that semi-NMF is sometimes ill-posed (that is, an optimal solution does not
exist).
