Papers for

data scientists using matrix factorization

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Computing best rank 2 nonnegative matrix factorization is strongly NP-hard

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

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.

Thu 15 OctComputational Complexity

The gist

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.

Open → 2610.21874v1