Complexity of globally optimal nonnegative rank-two approximation
For $X \in \mathbb{R}_{\ge 0}^{m \times n}$ and $r \ge 1$, nonnegative matrix factorization (NMF) in the Frobenius norm asks for $$\min \|X - WH\|_F^2 \quad \text{over } W \in \mathbb{R}_{\ge 0}^{m \times r},\ H \in \mathbb{R}_{\ge 0}^{r \times n}.$$ It is NP-hard when $r$ is part of the input (Vavasis; see Gillis), and for $r = 1$ an optimal solution can be computed in polynomial time from a leading pair of singular vectors of $X$ (Gillis). For $r = 2$, if the rank-two truncated singular value decomposition of $X$ is entrywise nonnegative, it is a best nonnegative rank-two approximation, and nonnegative factors of it can be computed in polynomial time (Gillis); in general it may have negative entries. Lindy, Noferini and Van Dooren construct a cheaply computable, in general suboptimal, nonnegative rank-two approximation of an arbitrary nonnegative matrix, used to start alternating nonnegative least squares.
Problem. Given $X \in \mathbb{Q}_{\ge 0}^{m \times n}$ and $\tau \in \mathbb{Q}_{\ge 0}$, determine the complexity of deciding whether there exist $W \in \mathbb{R}_{\ge 0}^{m \times 2}$ and $H \in \mathbb{R}_{\ge 0}^{2 \times n}$ with $$\sum_{i=1}^{m} \sum_{j=1}^{n} \Bigl(X_{ij} - \sum_{k=1}^{2} W_{ik} H_{kj}\Bigr)^2 \le \tau.$$ In particular, is there a deterministic algorithm running in time polynomial in the total binary length of the input, or is this decision problem NP-hard under polynomial-time many-one reductions? These two outcomes are not assumed to be the only possibilities. The factors may have real entries, a zero column of $W$ or zero row of $H$ is allowed, and $X$ need not have rank two.
Source: Stated by OpenProblemsInNLA as an exact decision problem with rational data, after the question of the complexity of computing a best nonnegative rank-two approximation in the Frobenius norm raised by Gillis and Glineur (2008), §2.1, Gillis (2020), §6.1.3, and Lindy, Noferini and Van Dooren (2025), §1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- low-rank approximations, nonnegative matrix factorizations, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{gillis2008,
author = {Gillis, Nicolas and Glineur, Fran{\c{c}}ois},
title = {Nonnegative Factorization and The Maximum Edge Biclique Problem},
year = {2008},
eprint = {0810.4225},
archivePrefix = {arXiv},
note = {Section 2.1},
}
@book{gillis2020,
author = {Gillis, Nicolas},
title = {Nonnegative Matrix Factorization},
publisher = {SIAM},
address = {Philadelphia, PA},
year = {2020},
doi = {10.1137/1.9781611976410},
note = {Chapter 6, Theorems 6.1, 6.4 and 6.6 and Section 6.1.3},
}
@misc{lindy2025,
author = {Lindy, Etna and Noferini, Vanni and Van Dooren, Paul},
title = {On rank-2 Nonnegative Matrix Factorizations and their variants},
year = {2025},
eprint = {2507.20612},
archivePrefix = {arXiv},
}
@article{vavasis2009,
author = {Vavasis, Stephen A.},
title = {On the Complexity of Nonnegative Matrix Factorization},
journal = {SIAM J. Optim.},
volume = {20},
number = {3},
year = {2009},
pages = {1364--1377},
doi = {10.1137/070709967},
eprint = {0708.4149},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-nm03,
author = {Townsend, Alex},
title = {{NM-03}: Complexity of globally optimal nonnegative rank-two approximation},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/nonnegative-and-positive-factorizations/NM-03/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
The paper gives a polynomial-time many-one reduction from positive one-in-three satisfiability to the exact rational-input decision problem for nonnegative rank-two approximation in the squared Frobenius norm, so that this problem is NP-hard. The reduction produces strictly positive, symmetric positive definite rational matrices whose unconstrained best rank-two approximation error is an explicit rational threshold; a nonnegative approximation attains that threshold exactly …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00260, "Complexity of globally optimal nonnegative rank-two approximation", clopen.solutions.