Exact nonnegative matrix factorization (Exact NMF) factorizes a nonnegative matrix RR of rank rr as CS⊤CS^\top with nonnegative factors of rr columns; the decomposition is generically unique only up to permutation and positive scaling of columns, and characterizing when components are identifiable is a central theoretical problem. Gillis and Rajkó (SIAM J. Matrix Anal. Appl. 44(1):27–52, 2023) initiated the rigorous study of partial identifiability — uniqueness of a subset of the columns of the factors — proving that a single column can be certified from a selective-window (anchor) condition plus a full-rank zero-region window condition, that such certificates apply sequentially, and that at rank r=3r=3 two columns can be certified simultaneously. Their concluding question — whether stronger partial identifiability theorems can be obtained for several components simultaneously under weaker conditions, generalizing the rank-3 result to larger rr and relaxing the selective-window assumption toward the sufficiently scattered condition — is the problem addressed here. It remains open: no resolution is known in the literature to date. Later work strengthens only full identifiability (expanded sufficiently scattered conditions, nonnegative Tucker decompositions) or the computational checking of the sufficiently scattered condition.

Background

Nonnegative matrix factorization (NMF) approximates a nonnegative data matrix R∈R+m×nR\in\mathbb{R}_+^{m\times n} by a product CS⊤CS^\top of two nonnegative matrices with rr columns each; it underlies topic modeling, hyperspectral unmixing, audio source separation, and multivariate curve resolution (MCR) in analytical chemistry. In Exact NMF the approximation is an equality, and — as in essentially all identifiability results, including those of the source paper — one works in the regime r=rank⁡(R)r=\operatorname{rank}(R), so both factors have full column rank. Because permuting the columns of CC and SS or rescaling them by positive diagonal matrices leaves the product unchanged, uniqueness is only meaningful up to these trivial ambiguities: an Exact NMF is identifiable (unique) when every other Exact NMF of size rr is obtained from it by such transformations. Unlike the singular value decomposition, Exact NMF is not unique in general, and a substantial literature develops sufficient conditions for uniqueness (see the monograph by Gillis, 2020).

The two best-known sufficient conditions are separability and the sufficiently scattered condition (SSC). Separability requires that each column of CC itself appear as a column of RR; in the source paper's terminology, a column of C⋆C^\star satisfies the selective window condition when some row of S⋆S^\star is a positive multiple of a unit vector — in applications this is an anchor or pure-variable assumption (a word belonging to a single topic, a wavelength at which only one chemical species absorbs). The SSC of Huang, Sidiropoulos and Swami is strictly weaker than separability: geometrically, it requires the cone generated by the columns of a factor to contain a second-order ('ice-cream') cone inscribed in the nonnegative orthant, and to be preserved by no nontrivial rotation of the orthant; if both factors satisfy the SSC, the Exact NMF is fully identifiable (Theorem 4 of the source paper). The SSC is NP-hard to check in general.

Chemometrics, through the MCR problem, long studied a finer question: when the full decomposition is not unique, are individual chemical profiles (concentration profiles or spectra — the columns of CC or SS) nevertheless uniquely determined? That literature distinguishes fractional uniqueness (a single profile of one component is unique), partial uniqueness (both profiles of one or more, but not all, components are unique), and full uniqueness. Rajkó and co-workers formalized data-based uniqueness (DBU) criteria, and Lakeh, Abdollahi and Rajkó (2022) published a restricted DBU criterion applying to a particular solution of Exact NMF rather than to the whole feasible set, but without complete proofs. Gillis and Rajkó (2023) gave the first rigorous, theorem-level treatment of this partial identifiability for Exact NMF. Their Theorem 6 (the restricted DBU theorem) certifies the kkth column of C⋆C^\star from two conditions: the full-rank zero-region window (FRZRW) condition — the rows of C⋆C^\star on which that column vanishes form a submatrix of rank r−1r-1 — and the selective window condition above. Their Theorem 7 recasts this geometrically, Theorem 8 shows that identifying pp columns reduces the problem to a smaller Exact NMF on the columns of RR disjoint from their supports (so single-column certificates can be applied sequentially), and Theorem 9 — valid only for r=3r=3 — certifies two columns of C⋆C^\star simultaneously, still assuming both satisfy the selective window condition.

The engine behind these results is the nested polytope interpretation of Exact NMF: after ℓ1\ell_1-normalization the columns of RR are points inside the polytope conv⁡(C)\operatorname{conv}(C) spanned by the columns of CC, and certifying a column of C⋆C^\star amounts to showing that every polytope nested between the data points must pin a vertex at that column, which is formalized through the minimal face of conv⁡(C⋆)\operatorname{conv}(C^\star) containing a given column. A different, local notion — rigidity of a factorization under small perturbations — was analyzed by Krone and Kubjas (2021); the source paper observes that earlier chemometric criteria implicitly targeted such local uniqueness, whereas global partial identifiability (uniqueness of a column across the entire feasible set) is the stronger notion it addresses.

What the source paper leaves open, in its own concluding paragraph, is whether these partial identifiability theorems can be strengthened: every certificate it proves is per-column and anchored (each certified column must individually pass the selective window test), the simultaneous certificate exists only at rank r=3r=3, and the SSC — the successful weak condition for full identifiability — has no partial counterpart. The paper also notes that the FRZRW condition is, column by column, a necessary condition for the SSC, suggesting that a bridge between the separability-based partial theory and the SSC-based full theory should exist.

Problem Statement

Let R=C⋆S⋆⊤R=C^\star S^{\star\top} be an Exact NMF with C⋆∈R+m×rC^\star\in\mathbb{R}_+^{m\times r}, S⋆∈R+n×rS^\star\in\mathbb{R}_+^{n\times r} and r=rank⁡(R)r=\operatorname{rank}(R). Following Definition 3 of the source paper, the kkth column of C⋆C^\star is identifiable when every Exact NMF R=CS⊤R=CS^\top of size rr contains that column up to a positive scaling (at some position); by the duality symmetry R⊤=S⋆C⋆⊤R^\top=S^\star C^{\star\top} the same notion applies to the columns of S⋆S^\star. The problem is the concluding question of Gillis and Rajkó (2023), made precise:

Main question. Give sufficient conditions — strictly weaker than the combination of the selective window condition and the full-rank zero-region window (FRZRW) condition, and not requiring each certified column to be anchored to a pure data column — under which p≥2p\geq 2 columns of C⋆C^\star (and, by duality, the corresponding columns of S⋆S^\star) are simultaneously identifiable, for arbitrary factorization rank rr, in particular for r≥4r\geq 4 beyond the reach of the rank-3 Theorem 9. Here 'strictly weaker' is meant in the implication sense: the new conditions must not require the selective-window/FRZRW combination, and conditions merely incomparable with it — such as the sufficiently scattered condition imposed on both factors, which already yields full identifiability (Theorem 4 of the source paper) — do not qualify.

A rigorous negative result of matching generality answers the same question in the opposite direction: a proof that, for every rank r≥4r\geq 4, simultaneous identifiability of two or more columns necessarily forces selective-window-type structure is by itself a complete resolution, and so is a proof that, for every rank r≥4r\geq 4, such simultaneous identifiability collapses to full identifiability of the whole factorization.

Two companion directions related to the same open agenda — a characterization of partial local uniqueness (rigidity of a subset of columns, in the sense of Krone and Kubjas) as opposed to global partial identifiability, and scalable, noise-robust certification procedures for the new conditions — are separate, related open questions.

References

  1. 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 (arXiv:2206.08022, https://arxiv.org/abs/2206.08022; source paper)
  2. Kejun Huang, Nicholas D. Sidiropoulos, and 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
  3. 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
  4. Mahsa Akbari Lakeh, Hamid Abdollahi, and Róbert Rajkó, 'Predicting the uniqueness of single non-negative profiles estimated by multivariate curve resolution methods', Analytica Chimica Acta 1199:339575, 2022. DOI: 10.1016/j.aca.2022.339575, https://doi.org/10.1016/j.aca.2022.339575
  5. Nicolas Gillis and Robert Luce, 'Checking the Sufficiently Scattered Condition using a Global Non-Convex Optimization Software', arXiv:2402.06019, 2024, https://arxiv.org/abs/2402.06019
  6. Giovanni Barbarino, Nicolas Gillis, and 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
  7. Subhayan Saha, Giovanni Barbarino, and Nicolas Gillis, 'Identifiability of Nonnegative Tucker Decompositions – Part I: Theory', arXiv:2505.12713, 2025, https://arxiv.org/abs/2505.12713
  8. Róbert Rajkó and Rabeea Razaq, 'Uniqueness in multivariate curve resolution, re-tuned', arXiv:2607.23280, 2026, https://arxiv.org/abs/2607.23280
  9. Qianqian Qi and Peter G. M. van der Heijden, 'A review of NMF, PLSA, LBA, EMA, and LCA with a focus on the identifiability issue', arXiv:2512.22282, 2025, https://arxiv.org/abs/2512.22282
  10. Nicolas Gillis, 'Nonnegative Matrix Factorization', SIAM, Philadelphia, 2020. DOI: 10.1137/1.9781611976410, https://doi.org/10.1137/1.9781611976410 (ISBN 978-1-61197-640-3)
  11. Paul-Albert Schneide, Neal Gallagher, Jesper Løve Hinrich, Rasmus Bro, and Romà Tauler, 'A unifying framework for modelling non-negative bi-linear, tri-linear and "in-between" data in chemometrics. Part I: Theoretical framework and concepts', Chemometrics and Intelligent Laboratory Systems 265:105492, 2025. DOI: 10.1016/j.chemolab.2025.105492, https://doi.org/10.1016/j.chemolab.2025.105492
  12. Alejandro C. Olivieri, 'Hazards of using multivariate curve resolution for processing first-order spectral data. A rotational ambiguity analysis', Analytica Chimica Acta 1367:344304, 2025. DOI: 10.1016/j.aca.2025.344304, https://doi.org/10.1016/j.aca.2025.344304