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)