Source-linked AI summary
Identifiability of Nonnegative Tensor Decompositions via Positive Scattering
Haoming Wang, Ming Yuan
TL;DR
Nonnegative tensor identifiability requires information beyond linear-algebraic factor conditions because positivity prevents cancellation and constrains supports. The paper combines a Lovitz–Petrov dimension budget with positive scattering, obtaining threshold criteria for minimality and uniqueness, strict improvements on sparse examples, and exact matrix interpretations.
Problem
Linear-algebraic conditions do not capture the additional identifiability information supplied by nonnegativity, including the absence of cancellation and support constraints on competing decompositions.
Method
The paper combines the Lovitz–Petrov dimension budget with a positive scattering term and a positive splitting inequality for irreducible exchanges.
Results
The resulting criterion strictly improves dimension-based uniqueness conditions on sparse examples, including cases where Lovitz–Petrov fails after reshaping, while reducing in matrices to full-rank factorization and two-sided separability.
Takeaways & Limitations
Positive support geometry can provide a deterministic identifiability certificate beyond dimension-based conditions, with an exact graph-connectivity characterization of the scattering term.
Takeaways & Limitations
The interaction between scattering and reshaping lacks a general comparison, and the full certificate requires checking all nontrivial component subsets.
Abstract
from arXiv · showhide
Identifiability of tensor decompositions is often established through linear-algebraic conditions on the factor families. For nonnegative decompositions, however, positivity provides additional information that is not captured by dimension and independence alone: nonnegative terms cannot cancel, and their supports constrain competing decompositions. We introduce a positive scattering term that quantifies this additional source of identifiability and combine it with the dimension budget underlying the Lovitz--Petrov generalization of Kruskal's theorem. For every subset of components, we obtain two sufficient conditions: a threshold of $2|S|-2$ guarantees minimality and nonnegative rank, while the stronger threshold $2|S|-1$ guarantees uniqueness among nonnegative decompositions of the same length. The key result is a positive splitting inequality for irreducible exchanges of nonnegative rank-one tensors, which combines the dimension constraint with support-induced geometric rigidity. Although the scattering term is defined through an optimization over intermediate factor spaces, we show that its mode costs are exactly $0$, $1$, or $+\infty$, yielding an exact activation characterization in terms of graph connectivity. The resulting criterion can strictly certify sparse nonnegative tensor decompositions beyond the reach of Kruskal and Lovitz--Petrov conditions, including examples for which those conditions fail even after reshaping. In the matrix case, the two criteria reduce respectively to full-rank factorization and two-sided separability.
1 Introduction
The paper develops a deterministic identifiability theory for nonnegative tensor decompositions by combining Lovitz–Petrov dimension constraints with support geometry induced by positivity. Its thresholds certify minimality and same-length uniqueness, with strict gains over dimension-only criteria and exact matrix specializations.
- Nonnegativity constrains competing decompositions through the absence of cancellation, so observed zeros and supports provide identifiability information beyond factor independence.
- The paper combines the Lovitz–Petrov dimension budget with a positive scattering term τ(S) measuring support-geometric rigidity for component subsets.The two terms capture distinct sources of identifiability in a single certificate.
- The positive splitting inequality combines dimension control with support constraints to derive separate thresholds for shorter and inequivalent competing decompositions.Unbalanced exchanges correspond to shorter decompositions, while balanced exchanges of size at least two correspond to inequivalent minimal decompositions.
- The scattering term has an exact finite characterization: each mode cost is 0, 1, or +∞, and the required activation is determined by graph connectivity.The resulting procedure uses support tests, linear-programming vertex tests, and connectivity.
- The criterion can certify sparse nonnegative uniqueness when Lovitz–Petrov fails, including after reshaping, and reduces in matrices to full-rank factorization for minimality and two-sided separability for uniqueness.Numerical experiments report substantial gains in sparse regimes.
2 Problem Setup and Main Criterion
The main criterion augments the Lovitz–Petrov subset-wise dimension budget with a positive scattering term and applies two thresholds to nonnegative decompositions. The weaker threshold certifies minimality, while the stronger one certifies uniqueness among decompositions of the same length.
- The certificate combines β(S), the Lovitz–Petrov dimension budget, with τ(S), the additional factor-space enlargement forced by support geometry and nonnegativity.
- β(S) + τ(S) ≥ 2|S| −2 for every subset S with |S| ≥2 guarantees minimality and equality between decomposition length and nonnegative rank.
- β(S) + τ(S) ≥ 2|S| −1 for every subset S with |S| ≥2 guarantees uniqueness among nonnegative decompositions of the same length.
- The positive splitting inequality charges irreducible exchanges for both linear complexity and support constraints imposed by nonnegativity.
- Because τ(S) ≥ 0, the criterion contains Lovitz–Petrov and can strictly improve it on explicit examples, even after reshaping.
3 Positive Exchanges and the Splitting Mechanism
The paper compares nonnegative decompositions through positive exchanges, decomposes exchanges into irreducible blocks, and combines their connectedness with Lovitz–Petrov dimension bounds. This distinction yields separate thresholds for minimality and uniqueness.
- Minimality: Minimal nonnegative decompositions have linearly independent terms, because any signed relation can be perturbed to eliminate one term and produce a shorter decomposition.Nonnegativity ensures the relation has coefficients of both signs and preserves nonnegative coefficients during the perturbation.
- Positive Exchanges: Positive exchanges compare two finite sums of nonzero nonnegative rank-one tensors, and positivity rules out nonempty subexchanges with only one side.Every nonempty subexchange has nonempty index sets on both sides because nonzero nonnegative tensors have strictly positive entry sums.
- Irreducible Blocks: Every positive exchange decomposes into disjoint irreducible positive exchanges, each containing no nontrivial subexchange.The decomposition is obtained by repeatedly selecting minimal nonempty subexchanges and removing them.
- Balanced Exchanges: Blocks between two minimal decompositions are balanced, so the decompositions have equal length; inequivalent minimal decompositions therefore contain a balanced irreducible block of size at least two.An unbalanced block could replace one side with the other and contradict minimality.
- Splitting Mechanism: The Lovitz–Petrov theorem supplies the linear-algebraic dimension bound, while nonnegativity contributes a complementary support-geometry constraint to the positive splitting inequality.The argument applies Lovitz–Petrov to signed families from irreducible positive exchanges; support geometry has no analogue for arbitrary signed exchanges.
4 Support Geometry and Bridge Connectivity
Nonnegativity is encoded through intrinsic cones, facet signatures, and bridge graphs that capture support restrictions invisible to ordinary dimension. Bridge connectivity characterizes the support geometry required for irreducible exchanges.
- Intrinsic Cones: Intrinsic cones of admissible factor spaces are pointed, full-dimensional polyhedral cones whose facets are exposed by coordinate functionals.This remains true even when the cone lies in a lower-dimensional subspace of the ambient coordinate space.
- Facet Signatures: The injective facet-coordinate map sends the intrinsic cone into a nonnegative orthant, giving every nonzero nonnegative factor a nonempty positive facet signature.The signature records the facets where a selected coordinate representative is strictly positive and is invariant under positive rescaling.
- Bridge Graphs: A bridge graph connects components whose facet signatures are compatible in all but possibly one mode, corresponding to one-coordinate rook moves between signature boxes.Each component’s signature product forms a rook-connected box in the product of facet sets.
- Bridge Graphs: Bridge-graph components correspond bijectively to rook-connected components of the union of signature boxes.Thus bridge paths and rook connectivity describe the same support geometry.
- Rectangular Splitting: If the bridge graph is disconnected, rectangular support splitting produces a nontrivial subexchange, so the original exchange is reducible.This constraint arises because nonnegative product tensors have rectangular supports and cannot cancel outside those supports.
5 The Positive Scattering Term
The positive scattering term quantifies the additional identifiability supplied by support geometry, turning connectivity requirements among prescribed components into an exact finite criterion.
- Support confinement: Nonnegativity confines competing factors to coordinate support hulls, so admissible intermediate spaces must remain between prescribed spans and these hulls.This support confinement is forced by positivity in any exchange involving the selected components.
- Definition of positive scattering: Positive scattering τ(S) is the minimum total dimension added across modes to make the associated bridge graph connected.The optimization ranges over admissible intermediate factor spaces whose bridge graph connects the components.
- Tree formula: A spanning-tree reformulation separates connectivity requirements by mode and reduces the continuous subspace optimization to mode costs κ_j(F).Each mode cost measures dimensions needed to create the required facet-signature intersections for a set of pairs.
- Activation formula: The activation formula computes τ(S) by increasing the number of activated modes until the corresponding graph G_A(S) becomes connected.For fixed tensor order, postprocessing after vertex tests requires at most 2^d graph-connectivity problems, while the full subset-wise certificate need not be polynomial in R.
6 Proof of the Main Criterion
The main proof combines Lovitz–Petrov dimension control with support-induced connectivity to bound irreducible positive exchanges and derive minimality and uniqueness.
- Positive splitting inequality: The positive splitting inequality adds the scattering cost τ(S) to the Lovitz–Petrov dimension budget β(S) for every irreducible positive exchange.The exchange’s factor spaces form an admissible feasible tuple, while connectedness supplies the Lovitz–Petrov dimension constraint.
- Exchange connectedness: Irreducibility forces the signed family of exchange terms to be connected, because any disconnected partition would produce a nontrivial subexchange.This is the combinatorial step that permits the dimension-counting argument.
7 Structural Consequences
The criterion supports reshaping and appending nonnegative modes, but these operations have different guarantees: reshaping can increase dimension budgets, whereas appending preserves and strengthens the certificate.
- Reshaping: Reshaping permits subset-specific mode groupings, and the resulting grouped dimension–scattering criterion can certify minimality or uniqueness.Grouping can increase factor-span dimensions, and the partition may be chosen independently for each subset.
- Reshaping: Grouping modes can create linear independence absent from the individual modes, as illustrated by Khatri–Rao products.This explains why reshaping may strengthen the dimension component of the certificate.
- Reshaping: No general monotonicity relation is established for scattering before and after reshaping.The grouped scattering term may interact with changed factor geometry in ways not captured by dimension alone.
- Appending modes: The scattering term is superadditive across disjoint nonempty mode sets, so adding modes can only increase the combined structural-information budget.The dimension budget is additive, while the scattering term is superadditive.
- Appending modes: Appending nonnegative modes preserves whichever minimality or uniqueness condition the original decomposition satisfies.The extended decomposition retains the original certificate while gaining nonnegative contributions from the appended modes.
8 Examples
The examples show that positive scattering can certify nonnegative uniqueness even when every dimension-based Lovitz–Petrov condition fails, including after reshaping. Sparse support patterns create infinite scattering, while experiments show the criterion expands certification most strongly in sparse regimes and often finds alternatives when it fails.
- Deterministic examples: Infinite scattering certifies uniqueness for the W tensor and an arbitrary-length family because every pair has disjoint supports in at least two modes.The activation graph is disconnected, so τ(S) = +∞ for every nontrivial subset; the dimension budget alone can remain below threshold.
- Deterministic examples: The W tensor satisfies the positive-scattering uniqueness criterion despite pairwise Lovitz–Petrov thresholds of 3 failing.The same tensor has a continuum of real rank-three decompositions, so the gain is specific to nonnegative uniqueness.
- Deterministic examples: For the arbitrary-length family, β([R]) = 2R −2 < 2R −1 and every reshaping remains below the uniqueness threshold, yet nonnegative uniqueness holds.The maximum reshaped budget is 2R −2, while τ(S) = +∞ supplies the missing certificate.
- Numerical comparison: The positive-scattering criterion can only expand the certified region beyond Lovitz–Petrov, with the largest observed increase of 0.60 at (n, p) = (12, 0.04).The comparison uses exact computations on random sparse decompositions with d = 3 and R = 5; the gain is largest in sparse regimes and disappears as an infinite-cost obstruction at full support.
- Searching for alternatives: Among 5621 realizations violating (U), exact nonnegative alternatives were found in 5497 pair constructions and 10 larger-subset constructions, leaving 114 inconclusive cases.The experiment provides evidence that the criterion may be close to necessary for this sparse ensemble, but does not establish necessity.
9 Matrix Specialization
In the matrix boundary case, the dimension budget cannot certify uniqueness, so positive scattering supplies the decisive structure. The resulting criteria reduce exactly to full-rank factorization for minimality and two-sided separability for uniqueness.
- Dimension budgets: Neither the formally specialized Lovitz–Petrov budget nor Kruskal’s threshold can reach the uniqueness threshold in two modes.Thus the matrix uniqueness result comes entirely from the positivity-induced scattering term.
- Activation graphs: Mode costs are restricted to 0, 1, or +∞, and the matrix activation graphs are characterized through facet-overlap and support-overlap graphs.For example, κ1({r, t}) < +∞ exactly when {r, t} is an edge of the support-overlap graph OA(S).
- Complete characterization: For nonnegative matrix decompositions, minimality is equivalent to rank(A) = rank(B) = R, equivalently rank(X) = R.This gives the matrix criterion a directly observable full-rank interpretation.
- Complete characterization: Uniqueness among nonnegative decompositions of length R is equivalent to two-sided separability.The condition requires row-separability of both factor matrices.
- Separability: Two-sided separability is directly checkable from the factor matrices, avoiding subset enumeration and linear-programming vertex tests.Pure rows provide the separability witnesses used in the facet characterization.
10 Conclusion
The paper combines Lovitz–Petrov dimension budgets with positive scattering to obtain deterministic identifiability criteria for nonnegative tensor decompositions. Its graph-based scattering characterization strengthens certification in sparse settings, while the matrix case becomes full-rank minimality and two-sided-separable uniqueness; several algorithmic and higher-order extensions remain open.
- 10 Conclusion: The theory combines linear-algebraic dimension constraints with support-induced rigidity from nonnegativity through a positive scattering term.The scattering optimization reduces to mode costs in {0, 1, +∞} and a finite graph-activation problem.
- 10 Conclusion: The combined criterion can strictly improve dimension-based uniqueness conditions, including sparse examples where reshaping still fails to recover the Lovitz–Petrov condition.This establishes a deterministic route to certifying decompositions beyond linear-algebraic tests alone.
- 10 Conclusion: Appending nonnegative modes can only strengthen the combined dimension–scattering criterion, while reshaping changes the grouping of modes and the dimension budget.The general interaction between reshaping and scattering is not yet characterized.
- Open directions: The full certificate still requires checking all nontrivial component subsets, motivating more economical sufficient conditions and algorithms.The paper also leaves open broader higher-order analogues of matrix identifiability phenomena.