Computing best rank 2 nonnegative matrix factorization is strongly NP-hard
Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization
Computational Complexity
Summary
Nonnegative matrix factorization (NMF) is a way to break down a large table of numbers into two smaller tables, all containing only positive numbers. This helps find patterns in data like images or text. For very simple cases, it’s easy and fast to find the best factorization, but this paper shows that for the next simplest case, called rank-2, finding the best factorization is actually very hard for computers. The authors prove this by connecting the problem to a well-known tough problem called Clique. This means there’s no quick method likely to work well for every case of rank-2 NMF.
What this means in practice
- •For algorithm designers: Know that designing efficient algorithms to compute best rank-2 NMF exactly is infeasible in general due to strong NP-hardness.
- •For data scientists using matrix factorization: Understand that exact best rank-2 NMF calculations are intractable, guiding reliance on approximate methods or heuristics.
A theory result. No direct application yet.
Authors
Arnaud Vandaele
Abstract
Nonnegative matrix factorization (NMF) approximates a nonnegative matrix by the product of two nonnegative matrices with a prescribed inner dimension~$r$. The existence of an exact NMF can be decided in polynomial time for every fixed~$r$, and a best rank-$1$ NMF in the Frobenius norm can be obtained from a truncated singular value decomposition. We prove that computing a best rank-$2$ NMF in the Frobenius norm is strongly NP-hard. Our proof uses a polynomial-time reduction from \textsc{Clique} that produces symmetric positive-definite, completely positive matrices with polynomially bounded integer entries. The same reduction also establishes strong NP-hardness of rank-$2$ symmetric NMF.