{"id":"arxiv/2610.21874","url":"https://arxiv.org/abs/2610.21874","tags":["math.OC","cs.CC"],"score":0,"title":"Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization","domain":"math.OC","source":"arxiv","authors":["Arnaud Vandaele"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}