In nonnegative matrix factorization (NMF), an n×mn\times m nonnegative matrix MM is factored as M=AWM=AW with nonnegative factors of inner dimension rr. Exact NMF is NP-hard, and Arora, Ge, Kannan and Moitra proved under the exponential time hypothesis (ETH) that no (nm)o(r)(nm)^{o(r)}-time algorithm exists, while giving polynomial-time algorithms under the separability condition (with an α\alpha-robust simplicial condition on the other factor) and singly-exponential-in-rr algorithms for fixed rr; they posed as an open direction the identification of further structural conditions on the factors under which NMF is polynomial-time solvable with provable recovery, together with finer-grained study of nonnegative rank. Later work established that a much weaker geometric condition --- the sufficiently-scattered condition --- makes the ground-truth factors identifiable as the essentially unique optimum of the minimum-volume criterion (unique up to permutation and scaling), an identification that persists even under noise; however, no polynomial-time algorithm is known to compute these ground-truth factors under this condition, a gap explicitly recorded as open in a 2019 tutorial survey and a 2021 paper on simplex-structured matrix factorization. The fine-grained dependence on rr for deciding whether the nonnegative rank is at most rr likewise remains bracketed between the ETH lower bound (nm)Ω(r)(nm)^{\Omega(r)} and Moitra's (nm)O(r2)(nm)^{O(r^2)} algorithm; that gap is retained here as background context only. This tractability frontier --- computing the ground-truth factors identified under conditions weaker than separability --- remains genuinely open.

Background

Nonnegative matrix factorization (NMF) asks, given a nonnegative matrix M∈R+n×mM\in\mathbb{R}_+^{n\times m} and an integer r>0r>0, for nonnegative matrices A∈R+n×rA\in\mathbb{R}_+^{n\times r} and W∈R+r×mW\in\mathbb{R}_+^{r\times m} with M=AWM=AW (exact NMF), or minimizing the Frobenius norm residual ∥M−AW∥F\|M-AW\|_F, where ∥⋅∥F\|\cdot\|_F is the entrywise square-root-of-sum-of-squares norm (approximate NMF). The smallest admissible rr is the nonnegative rank rank+(M)\mathrm{rank}_+(M), which is always at least the ordinary (real) rank; how far apart these two ranks can be is a classical question linking NMF to polyhedral combinatorics and communication complexity. NMF became a standard tool in machine learning and signal processing (topic modeling, hyperspectral unmixing, audio separation), but was long computed only by local-search heuristics; Vavasis proved that exact NMF is NP-hard. Arora, Ge, Kannan and Moitra initiated the rigorous study of when NMF is polynomial-time solvable: (i) exact and approximate NMF are solvable in polynomial time for every constant rr, by reducing to the decision problem for systems of polynomial inequalities (with the dependence on rr improved to singly exponential when the columns of AA are linearly independent, the so-called simplicial case); (ii) under the exponential time hypothesis (ETH, the assumption that 3-SAT admits no 2o(n)2^{o(n)}-time algorithms), exact NMF cannot be solved in time (nm)o(r)(nm)^{o(r)}; and (iii) under the separability condition of Donoho and Stodden --- each basis column of AA occurs itself as a column of MM, so the data contain 'anchor' columns --- NMF is solvable in time polynomial in nn, mm and rr, with a noise-tolerant variant in which the rows of WW, normalized to unit ℓ1\ell_1 norm, are α\alpha-robust simplicial (no row of WW lies within ℓ1\ell_1 distance α\alpha of the convex hull of the other rows). Their paper closes by asking what other plausible conditions on the factors one could impose in real-life applications, and for deeper theoretical study of nonnegative rank. Subsequent identifiability research showed that a much weaker geometric condition suffices for uniqueness: the columns of one factor (say WW, each normalized to unit ℓ1\ell_1 norm) are sufficiently scattered when the cone they generate contains the second-order cone {x: 1Tx≥r−1 ∥x∥2}\{x:\ \mathbf{1}^Tx \ge \sqrt{r-1}\,\|x\|_2\} inscribed in the nonnegative orthant, together with the boundary-contact condition spelled out in the Problem Statement below. Huang, Sidiropoulos and Swami introduced this condition for symmetric NMF and Fu, Huang and Sidiropoulos extended it to the asymmetric case, proving that under sufficient scatteredness (plus a full-rank condition on the other factor) the minimum-volume criterion (minimizing the volume of the convex hull of the columns of AA, subject to the columns of WW summing to one) recovers the ground-truth factors up to permutation and scaling of the rr basis columns; this guarantee is attached to that criterion rather than to arbitrary nonnegative factorizations, which are not in general unique under the same condition, and it was recently proven even in the presence of noise. Uniqueness, however, does not by itself yield an efficient algorithm: plain NMF and its minimum-volume formulations remain NP-hard, the greedy separability-style algorithms rely on anchor columns that sufficient scatteredness does not provide, and the sufficiently-scattered condition is itself NP-hard to check. On the purely complexity side, the constant-rr question was sharpened by Moitra, who reduced the algebraic decision formulation for rank+(M)≤r\mathrm{rank}_+(M)\le r to 2r22r^2 variables and thus decided it in time (nm)O(r2)(nm)^{O(r^2)} --- the first singly-exponential-in-rr exact algorithm, nearly optimal under ETH in the sense that (nm)o(r)(nm)^{o(r)} is impossible --- leaving the precise dependence on rr open as a matter of background interest. Separately, the nonnegative-rank-versus-real-rank relationship is now much better understood through extension complexity (the smallest size of an exact linear description of a polytope): Fiorini, Kaibel, Pashkovich and Theis showed that slack matrices of regular nn-gons have real rank 3 but nonnegative rank Θ(log⁡n)\Theta(\log n).

Problem Statement

Let M∈R+n×mM\in\mathbb{R}_+^{n\times m} of rank rr admit a nonnegative factorization M=AWM=AW with A∈R+n×rA\in\mathbb{R}_+^{n\times r}, W∈R+r×mW\in\mathbb{R}_+^{r\times m} and let the minimum-volume criterion (minimizing the volume of the convex hull of the columns of AA, subject to the columns of WW summing to one) single out the ground-truth factors, uniquely up to permutation and rescaling of the rr basis columns --- in particular, suppose the columns of WW are sufficiently scattered (after unit-ℓ1\ell_1 normalization, cone{W}\mathrm{cone}\{W\} contains the second-order cone C={x: 1⊤x≥r−1 ∥x∥2}\mathcal{C}=\{x:\ \mathbf{1}^\top x\ge\sqrt{r-1}\,\|x\|_2\} inscribed in the nonnegative orthant, and satisfies the boundary-contact condition cone{W}∗∩bd C∗={λek: λ≥0, k=1,…,r}\mathrm{cone}\{W\}^*\cap\mathrm{bd}\,\mathcal{C}^*=\{\lambda e_k:\ \lambda\ge 0,\ k=1,\dots,r\}, where C∗={x: 1⊤x≥∥x∥2}\mathcal{C}^*=\{x:\ \mathbf{1}^\top x\ge\|x\|_2\} and ∗* denotes the dual cone) and AA has full column rank. Is there an algorithm with running time polynomial in nn, mm, rr and the input bit complexity that outputs these ground-truth factors AA and WW? More broadly, per the concluding question of Arora, Ge, Kannan and Moitra ('What other plausible conditions can one impose on the factors in real-life applications?'): identify further plausible, practically motivated structural conditions on the factors --- beyond separability of AA (together with α\alpha-robust simpliciality of WW) --- under which exact or approximate NMF is solvable in polynomial time with provable recovery guarantees, or show that such conditions cannot exist under standard complexity assumptions (e.g., by proving hardness for instances satisfying the sufficiently-scattered condition). The objective is a characterization of the tractability frontier of exact NMF: which structural assumptions on the factors convert the worst-case NP-hard problem into one solvable in polynomial time with provable recovery. A definitive answer to the specific sufficiently-scattered question --- exhibiting such an algorithm, or proving hardness for these instances under standard assumptions --- or a polynomial-time-tractability or hardness result for any single structural condition weaker than separability is a step toward the full characterization.

References

  1. Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra. Computing a Nonnegative Matrix Factorization---Provably. SIAM Journal on Computing 45(4):1582-1611, 2016. DOI: 10.1137/130913869; arXiv:1111.0952. https://arxiv.org/abs/1111.0952
  2. Stephen A. Vavasis. On the Complexity of Nonnegative Matrix Factorization. SIAM Journal on Optimization 20(3):1364-1377, 2009. DOI: 10.1137/070709967; arXiv:0708.4149. https://doi.org/10.1137/070709967
  3. David Donoho, Victoria Stodden. When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?. Advances in Neural Information Processing Systems 16 (NIPS 2003). https://papers.nips.cc/paper_files/paper/2003/hash/1843e35d41ccf6e63273495ba42df3c1-Abstract.html
  4. Ankur Moitra. An Almost Optimal Algorithm for Computing Nonnegative Rank. SIAM Journal on Computing 45(1):156-173, 2016. DOI: 10.1137/140990139. https://doi.org/10.1137/140990139
  5. Kejun Huang, Nicholas D. Sidiropoulos, Ananthram Swami. Non-Negative Matrix Factorization Revisited: Uniqueness and Algorithm for Symmetric Decomposition. IEEE Transactions on Signal Processing 62(1):211-224, 2014. DOI: 10.1109/TSP.2013.2285514. https://doi.org/10.1109/TSP.2013.2285514
  6. Xiao Fu, Kejun Huang, Nicholas D. Sidiropoulos. On Identifiability of Nonnegative Matrix Factorization. IEEE Signal Processing Letters 25(3):328-332, 2018. DOI: 10.1109/LSP.2018.2789405; arXiv:1709.00614. https://arxiv.org/abs/1709.00614
  7. Xiao Fu, Kejun Huang, Nicholas D. Sidiropoulos, Wing-Kin Ma. Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications. IEEE Signal Processing Magazine 36(2):59-80, 2019. DOI: 10.1109/MSP.2018.2877582; arXiv:1803.01257. https://arxiv.org/abs/1803.01257
  8. Maryam Abdolali, Nicolas Gillis. Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms. SIAM Journal on Mathematics of Data Science 3(2):593-623, 2021. DOI: 10.1137/20M1354982; arXiv:2007.11446. https://doi.org/10.1137/20M1354982
  9. Nicolas Gillis, Róbert Rajkó. Partial Identifiability for Nonnegative Matrix Factorization. SIAM Journal on Matrix Analysis and Applications 44(1):27-52, 2023. DOI: 10.1137/22M1507553. https://doi.org/10.1137/22M1507553
  10. Giovanni Barbarino, Nicolas Gillis, Subhayan Saha. Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition. arXiv:2511.04291 (2025). https://arxiv.org/abs/2511.04291
  11. Byoungwook Jang, Alfred Hero. Minimum Volume Topic Modeling. arXiv:1904.02064 (2019). https://arxiv.org/abs/1904.02064
  12. Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis. Combinatorial bounds on nonnegative rank and extended formulations. Discrete Mathematics 313(1):67-83, 2013. DOI: 10.1016/j.disc.2012.09.015. https://doi.org/10.1016/j.disc.2012.09.015