Polynomial-time minimum-volume decision under sufficient scattering
Let $e$ be an all-ones vector, and for $H \in \mathbb{R}_{\ge 0}^{r \times n}$ let $\operatorname{cone}(H)$ be the cone generated by its columns. Call $H$ sufficiently scattered if $$\{x \in \mathbb{R}_{\ge 0}^r : e^{\mathsf T} x \ge \sqrt{r - 1}\, \|x\|_2\} \subseteq \operatorname{cone}(H)$$ and every orthogonal $Q \in \mathbb{R}^{r \times r}$ with $\operatorname{cone}(H) \subseteq \operatorname{cone}(Q)$ is a permutation matrix. This is Gillis's definition; other sources use a stronger second condition. For $X \in \mathbb{R}^{m \times n}$ of rank $r$, minimum-volume NMF is the problem $$\min \det(W^{\mathsf T} W) \quad \text{over } W \in \mathbb{R}^{m \times r},\ H \in \mathbb{R}_{\ge 0}^{r \times n} \text{ with } X = WH,\ e^{\mathsf T} H = e^{\mathsf T},$$ in which $W$ may have entries of either sign and the columns of $H$ sum to one. If $X = W_\star H_\star$ for a feasible pair with $H_\star$ sufficiently scattered, then $(W_\star, H_\star)$ is the unique optimal solution up to permutation (Fu, Ma, Huang and Sidiropoulos; Gillis). Gillis reports the conjecture that minimum-volume NMF is solvable in polynomial time when $H$ is sufficiently scattered.
Problem. The input is $X \in \mathbb{Q}^{m \times n}$, an integer $2 \le r \le \min(m, n)$ and $\tau \in \mathbb{Q}_{\ge 0}$, with the promise that $\operatorname{rank}(X) = r$ and that $X = W_\star H_\star$ for some real feasible pair $(W_\star, H_\star)$ with $H_\star$ sufficiently scattered; the factors are not given. Is there an algorithm that runs on every input in time polynomial in the total binary length of the input and, on every promised input, correctly decides, either deterministically or with probability at least $2/3$, whether some $W \in \mathbb{R}^{m \times r}$ and $H \in \mathbb{R}_{\ge 0}^{r \times n}$ satisfy $X = WH$, $e^{\mathsf T} H = e^{\mathsf T}$ and $\det(W^{\mathsf T} W) \le \tau$? The algorithm need not check the promise.
Source: Stated by OpenProblemsInNLA, after Gillis (2020), §4.3.3.6: the conjecture that minimum-volume NMF is solvable in polynomial time when H is sufficiently scattered, which Gillis attributes to Fu, Huang, Sidiropoulos and Ma (2019; cf. their §VIII).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- minimum-volume factorizations, nonnegative matrix factorizations, OpenProblemsInNLA, promise problems
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{fu2019,
author = {Fu, Xiao and Huang, Kejun and Sidiropoulos, Nicholas D. and Ma, Wing-Kin},
title = {Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications},
journal = {IEEE Signal Process. Mag.},
volume = {36},
number = {2},
year = {2019},
pages = {59--80},
doi = {10.1109/MSP.2018.2877582},
eprint = {1803.01257},
archivePrefix = {arXiv},
}
@book{gillis2020,
author = {Gillis, Nicolas},
title = {Nonnegative Matrix Factorization},
publisher = {SIAM},
address = {Philadelphia, PA},
year = {2020},
doi = {10.1137/1.9781611976410},
note = {Section 4.3.3.6, Definitions 4.15 and 4.42, Theorem 4.43},
}
@article{fu2015,
author = {Fu, Xiao and Ma, Wing-Kin and Huang, Kejun and Sidiropoulos, Nicholas D.},
title = {Blind Separation of Quasi-Stationary Sources: Exploiting Convex Geometry in Covariance Domain},
journal = {IEEE Trans. Signal Process.},
volume = {63},
number = {9},
year = {2015},
pages = {2306--2320},
doi = {10.1109/TSP.2015.2404577},
}
@misc{openproblemsinnla-nm01,
author = {Townsend, Alex},
title = {{NM-01}: Polynomial-time minimum-volume decision under sufficient scattering},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/nonnegative-and-positive-factorizations/NM-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00202, "Polynomial-time minimum-volume decision under sufficient scattering", clopen.solutions.