Abstract |
: |
Nonnegative Matrix Factorization (NMF) is a data analysis technique which allows compression and
interpretation of nonnegative data. NMF became widely studied after the publication of the seminal paper
by Lee and Seung (Learning the Parts of Objects by Nonnegative Matrix Factorization, Nature, 1999, vol.
401, pp. 788--791), which introduced an algorithm based on Multiplicative Updates (MU). More recently,
another class of methods called Hierarchical Alternating Least Squares (HALS) was introduced that seems
to be much more efficient in practice.
In this paper, we consider the problem of approximating a not necessarily nonnegative matrix
with the product of two nonnegative matrices, which we refer to as Nonnegative Factorization~(NF)~; this
is the subproblem that HALS methods implicitly try to solve at each iteration. We prove that NF is NP-hard
for any fixed factorization rank, using a reduction to the maximum edge biclique problem.
We also generalize the multiplicative updates to NF, which allows us to shed some light on the
differences between the MU and HALS algorithms for NMF and give an explanation for the better
performance of HALS. Finally, we link stationary points of NF with feasible solutions of the biclique
problem to obtain a new type of biclique finding algorithm (based on MU) whose iterations have an
algorithmic complexity proportional to the number of edges in the graph, and show that it performs better
than comparable existing methods. |