  Nonnegative matrix factorization (NMF) has become a prominent technique for
the analysis of image databases, text databases and other information retrieval
and clustering applications. In this report, we define an exact version of NMF.
Then we establish several results about exact NMF: (1) that it is equivalent to
a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a
polynomial-time local search heuristic exists.
