Nonnegative matrix factorization (NMF) is identifiable only up to a trivial scaling-and-permutation ambiguity, and deciding when a factorization is essentially unique is a classical open identifiability question. Krone and Kubjas (SIAM J. Matrix Anal. Appl. 42(1):134–164, 2021) recast this question in the language of rigidity theory for the case when the nonnegative rank of the matrix equals its rank: they characterize infinitesimally rigid factorizations, give an algorithm that decides local rigidity in most cases, obtain the strongest known necessary condition for uniqueness, and prove that locally rigid factorizations extend to globally rigid ones. What the framework lacks is the sufficient side: no analogue of the stress matrix of classical rigidity theory is known for NMF, and the framework yields no sufficient criterion for global rigidity (essential uniqueness of the NMF) from the factor data alone. The problem is to close this gap — to establish verifiable sufficient conditions for global rigidity of a nonnegative factorization M=ABM=AB with rank⁡(M)=rank⁡+(M)=r\operatorname{rank}(M)=\operatorname{rank}_+(M)=r.

Background

Nonnegative matrix factorization (NMF) writes a matrix MM with nonnegative entries as M=ABM=AB with nonnegative factors A∈R≥0m×rA\in\mathbb{R}_{\ge 0}^{m\times r} and B∈R≥0r×nB\in\mathbb{R}_{\ge 0}^{r\times n}; the smallest admissible inner dimension rr is the nonnegative rank rank⁡+(M)\operatorname{rank}_+(M). NMF underlies parts-based data analysis (topic modeling, spectral unmixing, chemometrics), where one wants the factors to be identifiable from the data. Since M=AB=(AC)(C−1B)M=AB=(AC)(C^{-1}B) for any invertible CC keeping the factors nonnegative, factorizations are never literally unique; the best one can hope for is uniqueness up to the trivial ambiguities, namely a positive diagonal rescaling combined with a permutation of the rank-one parts (a monomial matrix CC). Whether a given matrix has an essentially unique NMF is a largely open identifiability question. Known sufficient conditions — separability (one factor contains the identity matrix as a submatrix), sparsity assumptions, and volume-type conditions on the polytope associated with a factor (requiring, as in the standard sufficiently-scattered condition, that the columns of one factor span a cone large enough to contain a fixed second cone), surveyed by Fu, Huang, Sidiropoulos, and Ma (2019) — are either restrictive or require hypotheses beyond the factorization itself, and few necessary conditions are known; Laurberg, Christensen, Plumbley, Hansen, and Jensen (2008) showed that uniqueness forces a boundary-closed zero pattern in the factors.

Rigidity theory of bar-and-joint frameworks provides a geometric language for exactly this kind of uniqueness question: given a graph whose edges prescribe some pairwise distances between points, when is the point configuration determined up to trivial motions? A framework is infinitesimally rigid if every first-order motion preserving the prescribed edge lengths is a rigid-body motion; checking this is a rank condition on the rigidity matrix. Local rigidity means no nontrivial continuous deformation exists; global rigidity means every configuration with the same edge lengths is congruent — the analogue of uniqueness. For global rigidity the central sufficient tool is the stress matrix: an equilibrium stress is an assignment of weights to the edges whose weighted incidence sum vanishes at every vertex, and the stress matrix is the symmetric matrix built from these weights. Connelly (2005) proved that a framework in Rd\mathbb{R}^d is globally rigid if it has an equilibrium stress whose stress matrix is positive semidefinite with kernel of dimension exactly d+1d+1; Gortler, Healy, and Thurston (2010) later showed that an infinitesimal-stress condition of this type is also necessary for generic global rigidity. Singer and Cucuringu (2010) imported this viewpoint into low-rank matrix completion, where uniqueness of the completion is governed by rigidity of the associated measurement structure.

Krone and Kubjas (2021) carried this program to NMF in the case rank⁡(M)=rank⁡+(M)=r\operatorname{rank}(M)=\operatorname{rank}_+(M)=r, where every nonnegative factorization of MM with inner dimension rr is a rank factorization. They define infinitesimally, locally, and globally rigid nonnegative factorizations; global rigidity of (A,B)(A,B) is exactly essential uniqueness of the NMF of MM (every nonnegative factorization arises from (A,B)(A,B) through a monomial matrix). Because infinitesimal motions must additionally preserve nonnegativity of the factors, the linear-span condition of classical rigidity is replaced by a positive-span condition — a point must be expressible as a nonnegative combination of other points rather than merely as a real linear combination — turning a linear-algebra check into polyhedral geometry (computable with software for rational cones and polyhedra such as Normaliz). Their results include: a computable characterization of infinitesimal rigidity; purely combinatorial necessary conditions on the zero patterns of the factors, with all fifteen admissible thirteen-zero patterns (up to symmetry) realized by infinitesimally rigid factorizations for 5×55\times 5 matrices of nonnegative rank four; an algorithm that decides local rigidity of a given factorization, with a possible inconclusive output; the strongest known necessary condition for uniqueness, strengthening the Laurberg et al. condition; and an extension theorem stating that every locally rigid factorization becomes globally rigid after adjoining at most rr strictly positive rows to AA and at most rr strictly positive columns to BB. Uniqueness is also tied to the boundary of the set M≤rm×n\mathcal{M}_{\le r}^{m\times n} of matrices of nonnegative rank at most rr — a semialgebraic set, i.e. a subset of a real vector space cut out by finitely many polynomial equations and inequalities: a matrix with a unique NMF always lies on its boundary, and the paper relates boundary components to partially infinitesimally rigid factorizations (a generalization of infinitesimal rigidity, defined via the local geometry of the family of factorizations, that captures boundary matrices possessing a positive-dimensional set of factorizations), building on the classical stochastic-factorization picture of Mond, Smith, and van Straten (2003).

What the framework does not provide is the sufficient side. In classical rigidity the passage from local to global runs through the stress matrix; for NMF no analogue is known, and the authors state explicitly that developing one is the next step. The same paper poses further open directions with separate completion boundaries — a full combinatorial classification of zero patterns admitting infinitesimally rigid realizations for general r≥4r\ge 4; Question 5.12, which asks whether non-trivial boundary components of Mrm×n\mathcal{M}_r^{m\times n} for r≥4r\ge 4 contain non-isolated partially infinitesimally rigid factorizations not coming from the rank-increment construction of Proposition 5.10 or its dual; and a classification of the affine linear subspaces contained in the fiber of factorizations of the identity matrix. These adjacent questions are recorded for context but are not part of the problem below.

Problem Statement

Let M∈R≥0m×nM\in\mathbb{R}_{\ge 0}^{m\times n} with rank⁡(M)=rank⁡+(M)=r\operatorname{rank}(M)=\operatorname{rank}_+(M)=r, and let (A,B)(A,B) be a nonnegative factorization M=ABM=AB with A∈R≥0m×rA\in\mathbb{R}_{\ge 0}^{m\times r}, B∈R≥0r×nB\in\mathbb{R}_{\ge 0}^{r\times n}. Following Krone and Kubjas, (A,B)(A,B) is globally rigid if every nonnegative factorization of MM into an m×rm\times r and an r×nr\times n nonnegative matrix is obtained from (A,B)(A,B) as (AC,C−1B)(AC,C^{-1}B) for a monomial matrix CC with positive diagonal (a composition of a positive diagonal scaling and a permutation) — that is, if the NMF of MM is unique up to the trivial scaling-and-permutation ambiguity.

The framework of Krone and Kubjas decides infinitesimal rigidity, decides local rigidity in all but an explicitly inconclusive case, and provides the strongest known necessary condition for uniqueness, but it contains no sufficient criterion for global rigidity: the classical route from local to global rigidity runs through the stress matrix, and no analogue of the stress matrix exists for nonnegative factorizations, where the linear algebra of frameworks is replaced by the polyhedral geometry of positive spans. Neither existing tool discharges the objective for the given (A,B)(A,B): the local-rigidity algorithm can return an inconclusive output and in any case decides only local rigidity, and the extension theorem certifies global rigidity only after adjoining up to rr strictly positive rows to AA and up to rr strictly positive columns to BB, which changes the matrix being factorized.

The problem is to close this gap. Establish verifiable sufficient conditions under which a nonnegative factorization (A,B)(A,B) with rank⁡(M)=rank⁡+(M)=r\operatorname{rank}(M)=\operatorname{rank}_+(M)=r is globally rigid, so that essential uniqueness of the NMF can be certified from the factor data (A,B)(A,B) alone.

Completion boundary: the problem is solved by a proven theorem giving checkable sufficient conditions that certify global rigidity of nonnegative factorizations, non-vacuously and demonstrated on explicit factorizations, where the criterion must apply to the general case rank⁡(M)=rank⁡+(M)=r\operatorname{rank}(M)=\operatorname{rank}_+(M)=r (for general rr, not a single fixed size). Answers must certify global rigidity in the sense defined above; criteria whose scope is contained in instances already covered by the known sufficient conditions (separability, sparsity, or volume-type conditions) do not by themselves constitute progress on the stated objective.

References

  1. Robert Krone and Kaie Kubjas. Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory. SIAM Journal on Matrix Analysis and Applications 42(1):134–164, 2021. DOI: 10.1137/19M1279472. https://doi.org/10.1137/19M1279472
  2. Robert Connelly. Generic Global Rigidity. Discrete & Computational Geometry 33(4):549–563, 2005. DOI: 10.1007/s00454-004-1124-4. https://doi.org/10.1007/s00454-004-1124-4
  3. Steven J. Gortler, Alexander D. Healy, and Dylan P. Thurston. Characterizing generic global rigidity. American Journal of Mathematics 132(4):897–939, 2010. DOI: 10.1353/ajm.0.0132. https://doi.org/10.1353/ajm.0.0132
  4. Amit Singer and Mihai Cucuringu. Uniqueness of Low-Rank Matrix Completion by Rigidity Theory. SIAM Journal on Matrix Analysis and Applications 31(4):1621–1641, 2010. DOI: 10.1137/090750688. https://doi.org/10.1137/090750688
  5. Hans Laurberg, Mads Græsbøll Christensen, Mark D. Plumbley, Lars Kai Hansen, and Søren Holdt Jensen. Theorems on Positive Data: On the Uniqueness of NMF. Computational Intelligence and Neuroscience, vol. 2008, Article 764206, pp. 1–9, 2008. DOI: 10.1155/2008/764206. https://doi.org/10.1155/2008/764206
  6. Xiao Fu, Kejun Huang, Nicholas D. Sidiropoulos, and 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. https://doi.org/10.1109/MSP.2018.2877582
  7. Nicolas Gillis and 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 (preprint: arXiv:2206.08022)
  8. Kristen Dawson, Serkan Hoşten, Kaie Kubjas, and Lilja Metsälampi. Uniqueness of size-2 positive semidefinite matrix factorizations. arXiv:2410.18891, 2024. https://arxiv.org/abs/2410.18891
  9. David Mond, Jim Smith, and Duco van Straten. Stochastic factorizations, sandwiched simplices and the topology of the space of explanations. Proceedings of the Royal Society of London. Series A 459(2039):2821–2845, 2003. DOI: 10.1098/rspa.2003.1150. https://doi.org/10.1098/rspa.2003.1150
  10. Max Pfeffer and Jose Alejandro Samper. The cone of 5×55\times 5 completely positive matrices. arXiv:2108.11928, 2021. https://arxiv.org/abs/2108.11928
  11. Kaie Kubjas and Lilja Metsälampi. Geometry of low nonnegative rank matrix completion. arXiv:2601.07658, 2026. https://arxiv.org/abs/2601.07658