Here is one such result.
Stephen A. Vavasis.
"On the complexity of nonnegative matrix factorization."
2007. (arXiv abstract link)
"In this report, we define an exact version of NMF [nonnegative matrix factorization]. 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."
There is now quite a bit known about this important problem, e.g.,
Arora, Sanjeev, et al. "Computing a nonnegative matrix factorization--provably." Proceedings of the 44th Symposium on Theory of Computing. ACM, 2012. (ACM link)
Incidentally, NMF played a role in the Netflix Prize problem:
Gábor Takács, et al. Matrix factorization and neighbor based algorithms for the Netflix prize problem. In: Proceedings of the 2008 ACM Conference on Recommender Systems, Lausanne, Switzerland, 267-274, 2008. (ACM link)