pipette
ENEnglish

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

Arnaud Vandaele

Preprint

En palabras de los autores

Nonnegative matrix factorization (NMF) approximates a nonnegative matrix by the product of two nonnegative matrices with a prescribed inner dimension~. The existence of an exact NMF can be decided in polynomial time for every fixed~, and a best rank- NMF in the Frobenius norm can be obtained from a truncated singular value decomposition. We prove that computing a best rank- 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- symmetric NMF.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.