Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 11 min ago
PreprintarXiv licencearXiv

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

  • Arnaud Vandaele
Open at sourcePDFDOICite

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.

Related

  1. An Alternating Minimization Algorithm for Federated Sparse Orthogonal Nonnegative Matrix Factorization
    Yanjiao Zhu, Xianchao Xiu, Yongyang Xiong +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization
    Matthew McCarver, Jing Qin
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingOptimisation & controlarXiv
  3. Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
    Julius A. Zeiss
    arXivPreprintCC BY 4.0Full textOptimisation & controlQuantum physics & quantum informationarXiv
  4. The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank
    Giovanni Seraghiti, Arnaud Vandaele, Nicolas Gillis
    arXivPreprintCC BY-NC-SA 4.0Full textNumerical analysis & scientific computingarXiv
  5. First-order Optimization Methods with Generalized Smoothness for Low-rank Matrix Factorization
    A. V. Bidanets, F. S. Stonyakin
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{vandaele2026strong,
  title = {{Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization}},
  author = {Arnaud Vandaele},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21874},
  eprint = {2610.21874},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21874},
}
RIS
TY  - UNPB
TI  - Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization
AU  - Arnaud Vandaele
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21874
UR  - https://arxiv.org/abs/2610.21874
AB  - 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.
ER  -