Conceptio › Archive › arXiv CS

arXiv CSopen access

Identifiability of Nonnegative Tensor Decompositions via Positive Scattering

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Identifiability of Nonnegative Tensor Decompositions via Positive Scattering

arXiv:2609.11606v1 [stat.ML] 10 Sep 2026

Haoming Wang and Ming Yuan Columbia University September 11, 2026

Abstract 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 +∞, 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. Keywords: Nonnegative tensor decomposition, identifiability, tensor rank, nonnegative matrix factorization

Introduction

Identifiability asks whether observable multilinear data uniquely determine their latent rank-one components, up to the unavoidable permutation and scaling ambiguities. This question is central whenever a tensor decomposition is used as a structural model rather than merely as a numerical approximation. Tensor methods, for example, turn low-order observable moments into latentcomponent recovery procedures in mixture, topic, and other latent-variable models (Allman et al., 2009; Anandkumar et al., 2014, 2015). Nonnegative tensor decompositions arise in such models when the latent components represent quantities that are intrinsically nonnegative. Nonnegative tensor decompositions also arise naturally in signal processing. They have been used, for example, for blind audio source separation (Barker and Virtanen, 2016) and multilinear spectral unmixing of hyperspectral data (Veganzones et al., 2016). More broadly, tensor decompositions provide identifiability in blind source separation and related multilinear inverse problems. Deterministic uniqueness conditions for canonical polyadic decompositions have therefore been developed to exploit additional structure in signal-processing models, including known, orthonormal, 1

or partially Hermitian factors (Sørensen and De Lathauwer, 2015). Nonnegativity provides a different form of structural information: unlike orthogonality or symmetry, it constrains competing decompositions through the absence of cancellation. Zeros and supports in the observed tensor therefore carry information about which alternative components are possible. A substantial literature studies uniqueness and identifiability of tensor decompositions through linear-algebraic properties of their factor families. Kruskal’s theorem uses the Kruskal ranks of the factors (Kruskal, 1977), while the Lovitz–Petrov theorem replaces these global conditions by a subset-wise dimension budget and strictly generalizes the Kruskal condition (Lovitz and Petrov, 2023). For nonnegative tensors, related work has established existence of best nonnegative lowrank approximations (Lim and Comon, 2009) and generic uniqueness of such approximations (Qi et al., 2016). These results leave open a different deterministic question: given a specified exact nonnegative decomposition, how much additional identifiability can be obtained from nonnegativity itself, beyond what is captured by the dimensions of the factor spans? This paper develops a deterministic answer to this question. Our main idea is to separate two sources of identifiability. The first is linear-algebraic and is measured by the Lovitz–Petrov dimension budget β(S) =

d X

dj (S) − 1 ,

j=1

for subsets S of components. The second comes from positivity and support geometry. We quantify it by a positive scattering term τ (S), whose formal definition is given in Section 5. Informally, τ (S) measures the minimum additional factor-space dimension required to connect the prescribed components through the support geometry imposed by nonnegativity. Thus β(S) and τ (S) capture two distinct sources of identifiability that can be combined in a single certificate. Our main result gives two deterministic sufficient conditions. If β(S) + τ (S) ≥ 2|S| − 2 for every S ⊆ [R] with |S| ≥ 2, then the prescribed decomposition is minimal and its number of terms equals the nonnegative rank. If the threshold is strengthened by one, to β(S) + τ (S) ≥ 2|S| − 1, then the decomposition is unique among nonnegative decompositions of the same length. The key structural result is a positive splitting inequality: for every irreducible exchange between p prescribed nonnegative rank-one terms and q competing terms, β(S) + τ (S) ≤ p + q − 2. The extra term τ (S) arises because an irreducible positive exchange must remain connected under the support geometry of the factor spaces, while the Lovitz–Petrov argument controls the corresponding linear dimension. The two identifiability thresholds then follow by contradiction from the fact that a shorter competing decomposition creates an unbalanced exchange, whereas an inequivalent minimal decomposition creates a balanced exchange of size at least two. Although τ (S) is introduced through a seemingly continuous optimization over intermediate factor spaces, it admits an exact finite characterization. We show that the cost associated with each mode is always 0, 1, or +∞, and that τ (S) is the minimum number of modes that must be activated to make an associated graph connected. This yields an exact computational procedure based on support tests, linear-programming vertex tests, and graph connectivity. The resulting 2

criterion is strictly stronger than the corresponding dimension-based criteria: we give deterministic families for which the new condition certifies nonnegative uniqueness even though the Lovitz– Petrov condition fails, including after reshaping, and numerical experiments show substantial gains in sparse regimes. The theory also clarifies the matrix boundary case. For order two, the minimality criterion reduces exactly to full column rank of the two factors, or equivalently to rank(X) = R, while the uniqueness criterion reduces exactly to two-sided separability. Thus the same positive-scattering mechanism that strengthens tensor identifiability specializes to a classical nonnegative matrix identifiability condition. The remainder of the paper is organized as follows. Section 2 states the problem and the main criterion at a high level. Section 3 develops positive exchanges and the Lovitz–Petrov splitting mechanism. Section 4 develops the support geometry and bridge connectivity induced by nonnegativity. Section 5 gives the formal definition of the positive scattering term and derives its exact activation characterization. Section 6 proves the positive splitting inequality and the main identifiability result. Section 7 develops reshaping and appending-mode consequences, Section 8 gives deterministic and numerical examples, and Section 9 specializes the theory to matrices.

Problem Setup and Main Criterion

Write [n] = {1, . . . , n}. Fix d ≥ 2 and dimensions n1 , . . . , nd ≥ 1, and consider a nonnegative decomposition T =

R X

Pr ,

(d) Pr = a(1) r ⊗ · · · ⊗ ar ,

j a(j) r ∈ R≥0 \ {0}.

(1)

r=1

The nonnegative rank rank+ (T ) is the smallest number of nonzero nonnegative rank-one tensors whose sum is T ; a nonnegative decomposition is minimal if its length equals rank+ (T ). For d = 2, this additive rank-one representation is equivalent to the usual nonnegative matrix factorization formulation (Cohen and Rothblum, 1993, p. 152). Two nonnegative decompositions of the same length are equivalent if their multisets of rank-one terms coincide. The support of a vector x ∈ Rn is supp(x) = {i ∈ [n] : xi ̸= 0}; the support of a tensor is defined coordinatewise in the same way. For a nonzero nonnegative tensor, the sum of all entries, called the entry sum, is strictly positive. We will use repeatedly the elementary fact that a sum of nonzero nonnegative tensors is never zero. For a nonempty subset S ⊆ [R] and each mode j, put Uj (S) = span{a(j) r : r ∈ S},

dj (S) = dim Uj (S) ≥ 1,

and define the Lovitz–Petrov dimension budget (Lovitz and Petrov, 2023, Theorem 2) β(S) =

d X

dj (S) − 1 ≥ 0.

j=1

The main result augments this dimension budget with a positive scattering term τ (S). We defer its formal definition to Section 5. Informally, τ (S) measures the additional factor-space enlargement forced by nonnegativity to connect the prescribed components through their support geometry. Thus β(S) captures linear-algebraic information, while τ (S) captures additional rigidity arising from positivity and support geometry. 3

We use the following two conditions: β(S) + τ (S) ≥ 2|S| − 2,

for every S ⊆ [R] with |S| ≥ 2,

(M)

β(S) + τ (S) ≥ 2|S| − 1,

for every S ⊆ [R] with |S| ≥ 2.

(U)

and The first threshold rules out shorter competing nonnegative decompositions, while the stronger threshold also rules out competing decompositions of the same length. Theorem 1 (Positive Lovitz–Petrov criterion). Let (1) be a nonnegative decomposition. If condition (M) holds, then rank+ (T ) = R, so that (1) is minimal and its terms are linearly independent. If the stronger condition (U) holds, then every nonnegative decomposition of T of length R is equivalent to (1). The structural result behind Theorem 1 is a positive splitting inequality. For an irreducible positive exchange involving p prescribed terms and q competing nonnegative rank-one terms, it gives β(S) + τ (S) ≤ p + q − 2. The formal statement and proof are given in Section 6. The key point is that the usual Lovitz– Petrov dimension argument controls the linear complexity of the exchange, while nonnegativity imposes additional support constraints that must be paid for through τ (S). The criterion automatically contains the Lovitz–Petrov criterion because τ (S) ≥ 0. The improvement can be strict: Section 8 gives explicit nonnegative decompositions satisfying (U) for which the Lovitz–Petrov condition fails, even after reshaping the tensor. For comparison, the three criteria considered in this paper differ in the structural information they use:

Criterion

Information used

Guarantee

Kruskal Lovitz–Petrov This paper

Kruskal ranks subset-wise factor dimensions dimensions + support geometry

CP uniqueness CP uniqueness nonnegative minimality/uniqueness

Positive Exchanges and the Splitting Mechanism

This section develops the algebraic mechanism underlying the main identifiability result. We first record two elementary facts about nonnegative rank-one tensors. We then introduce positive exchanges and decompose them into irreducible blocks. Finally, we encode an exchange as a signed family of product tensors and recall the Lovitz–Petrov splitting theorem. The latter provides the linear-algebraic part of the argument; the additional constraint induced by nonnegativity will be developed through support geometry in the next sections.

3.1

Basic Facts for Nonnegative Decompositions

We begin with two elementary facts about product tensors. The first gives the usual uniqueness of factorization up to rescaling, while the second shows that a nonnegative rank-one tensor always admits nonnegative factors. 4

Lemma 1 (Product tensors). (i) If xj , yj ∈ Rnj satisfy x1 ⊗ · · · ⊗ xd = y1 ⊗ · · · ⊗ yd ̸= 0, then there exist nonzero scalars Q λ1 , . . . , λd with yj = λj xj for every j and dj=1 λj = 1. If in addition all the vectors xj , yj are nonnegative, then every λj is positive. (ii) Every nonzero nonnegative rank-one tensor is a tensor product of nonzero nonnegative vectors. Proof. Part (i). Write X = x1 ⊗ · · · ⊗ xd . Since X ̸= 0, there is a multi-index (i∗1 , . . . , i∗d ) with Q Xi∗1 ···i∗d ̸= 0. The entries of X are the products dj=1 xj (ij ), so xj (i∗j ) ̸= 0 for every j, and likewise yj (i∗j ) ̸= 0 for every j. Fix a mode j and let i ∈ [nj ] be arbitrary. Comparing the entry of the two product tensors whose jth index is i and whose lth index is i∗l for every l ̸= j gives xj (i)

xl (i∗l ) = yj (i)

l̸=j

yl (i∗l ).

l̸=j

The two products over l ̸= j are nonzero constants independent of i. Hence yj = λj xj with Q

∗ l̸=j xl (il ) ∗ ̸= 0. l̸=j yl (il )

λj = Q Substituting back, y1 ⊗ · · · ⊗ yd =

d Y

λj x1 ⊗ · · · ⊗ xd ,

j=1

and since this equals X ̸= 0 we obtain j=1 λj = 1. Now suppose all vectors are nonnegative. Choose i with yj (i) > 0. Then λj xj (i) = yj (i) > 0 forces xj (i) ̸= 0, hence xj (i) > 0 and λj > 0. Part (ii). Let X = b1 ⊗ · · · ⊗ bd ̸= 0 be entrywise nonnegative, with real factors bj . Choose a multi-index (i∗1 , . . . , i∗d ) with Xi∗1 ···i∗d =

d Y

bj (i∗j ) > 0.

j=1

In particular bj (i∗j ) ̸= 0 for all j, and the number of indices j for which bj (i∗j ) < 0 is even. Multiplying an even number of factors by −1 leaves the product tensor unchanged, so after flipping signs in pairs we may assume bj (i∗j ) > 0 for every j. We claim that then each bj is nonnegative. Fix j and i ∈ [nj ], and consider the entry of X whose jth index is i and whose other indices are i∗l : 0 ≤ Xi∗1 ···i···i∗d = bj (i)

bl (i∗l ),

l̸=j

where the product over l ̸= j is strictly positive. Hence bj (i) ≥ 0. Each bj is also nonzero, since X ̸= 0.

Convention 1. By Lemma 1 (ii), we may and will choose nonnegative factors for every nonzero nonnegative rank-one tensor under consideration. By Lemma 1 (i), this choice is unique up to positive rescalings whose product is one. All subsequent quantities are invariant under these rescalings. The next lemma records a basic consequence of nonnegativity that will also be used in the proof of the main criterion. Lemma 2. The terms of a minimal nonnegative decomposition are linearly independent. Proof. Let T =

R X

r=1

be minimal and suppose that R X

cr Pr = 0

r=1

is a nontrivial linear relation. The nonzero coefficients cannot all have the same sign. Indeed, after negating the relation if necessary we may assume that all nonzero cr are positive. Taking the entry sum of both sides then gives X cr (entry sum of Pr ) > 0, 0= r

a contradiction, since the entry sum of each Pr is positive. Hence, after negating the relation if necessary, at least one coefficient is positive and at least one is negative. Put 1 ε = min > 0, r: cr >0 cr attained at some index r0 . For every r the coefficient 1 − εcr is nonnegative: this is clear when cr ≤ 0, and when cr > 0 it follows from εcr ≤ 1. Moreover, 1 − εcr0 = 0. Consequently, T =

R X r=1

Pr − ε

R X

cr Pr =

R X

(1 − εcr )Pr

r=1

is a sum of at most R − 1 nonzero nonnegative rank-one tensors, after absorbing each positive coefficient into one factor and discarding terms with coefficient zero. This contradicts the minimality of R.

3.2

Positive Exchanges and Irreducible Blocks

We now introduce the basic object used to compare two nonnegative decompositions. Definition 1 (Positive exchange). A positive exchange is an equality X

Xi =

i∈I

s∈J

between two finite sums of nonzero nonnegative rank-one tensors, indexed by finite sets I and J. A subexchange of it is a pair (I ′ , J ′ ) with I ′ ⊆ I, J ′ ⊆ J and X

Xi =

i∈I ′

X s∈J ′

Ys .

The pairs (∅, ∅) and (I, J) are called the empty and full subexchanges, respectively. A subexchange is proper if it is different from the full subexchange and nontrivial if it is neither empty nor full. The exchange is irreducible if it has no nontrivial subexchange, and reducible otherwise. The positivity assumption immediately rules out one-sided subexchanges. Remark 1. A nonempty subexchange cannot have exactly one empty side. If, say, I ′ ̸= ∅ and J ′ = ∅, then X Xi = 0, i∈I ′

which is impossible because the entry sum of the left side is positive. Consequently every nonempty subexchange has both sides nonempty. The complement (I \ I ′ , J \ J ′ ) of any subexchange, obtained by subtracting it from the full exchange, is again a subexchange. If the original subexchange is nonempty and proper, then its complement is also nonempty and hence has both sides nonempty. Every exchange can be decomposed into irreducible pieces. Lemma 3 (Block decomposition). (i) Every positive exchange decomposes as a disjoint union of irreducible positive exchanges: there are partitions I = I1 ⊔ · · · ⊔ Im , J = J1 ⊔ · · · ⊔ Jm , such that each pair (Ik , Jk ) is an irreducible positive exchange. (ii) If the two sides of the exchange are minimal nonnegative decompositions of the same tensor, then every block is balanced, |Ik | = |Jk |; in particular, the two decompositions have equal length. Proof. Part (i). Let S be the set of all subexchanges other than the empty subexchange (∅, ∅). This finite set is nonempty because it contains the full subexchange (I, J). Order S by componentwise inclusion and choose a minimal element (I1 , J1 ). By Remark 1, both I1 and J1 are nonempty. The exchange X X Xi = Ys i∈I1

s∈J1

is irreducible. Indeed, a nontrivial subexchange of this block would be a nonempty subexchange of the original exchange that is strictly smaller than (I1 , J1 ), contrary to the choice of (I1 , J1 ). By Remark 1, the complement (I \ I1 , J \ J1 ) is again a subexchange. If it is empty, we are done. Otherwise we apply the same argument to the complementary exchange. At every step the total number of remaining indices strictly decreases, so the process terminates after finitely many steps. Part (ii). Let X X T = Xi = Ys i∈I

s∈J

with both decompositions minimal, and let (Ik , Jk ) be any block from part (i). Suppose |Ik | > |Jk |. Replacing the terms {Xi : i ∈ Ik } by {Ys : s ∈ Jk } leaves the sum unchanged, because the block is a subexchange. The resulting decomposition has length |I| − |Ik | + |Jk | < |I|, contradicting the minimality of the first decomposition. The case |Ik | < |Jk | is symmetric, using the minimality of the second decomposition. Hence every block is balanced, and summing over the blocks gives |I| = |J|. Thus an exchange witnessing failure of minimality must contain an unbalanced irreducible block, whereas an exchange between two different minimal decompositions contains a balanced irreducible block of size at least two. This distinction is what ultimately produces the two thresholds in Theorem 1.

3.3

Connectedness and the Lovitz–Petrov Splitting Theorem

The next step is to encode a positive exchange as a signed family of product tensors. Irreducibility of the exchange will then translate into connectedness of this signed family. Definition 2 (Splitting and connectedness). Following Lovitz and Petrov (2023, Definition 3), a finite multiset E of nonzero vectors in a real vector space splits if it has a nonempty proper submultiset F such that span E = span F ⊕ span(E \ F ). We call E connected if it does not split. A multiset with a single element is connected. The following theorem is the linear-algebraic ingredient in our argument. Theorem 2 (Lovitz–Petrov splitting theorem). Let E = {xa,1 ⊗ · · · ⊗ xa,d : a ∈ [N ]} be a finite multiset of nonzero product tensors over a field. For each mode put rj = dim span{xa,j : a ∈ [N ]}. If dim span E ≤

d X

(rj − 1),

j=1

then E splits. We will apply Theorem 2 only over R, to signed families obtained from irreducible positive exchanges. The resulting dimension bound is the linear-algebraic component of the positive splitting inequality. The complementary component, which has no analogue for arbitrary signed exchanges, comes from the support geometry imposed by nonnegativity and is developed in Sections 4–5.

Support Geometry and Bridge Connectivity

The previous section developed the linear-algebraic component of the identifiability argument through the Lovitz–Petrov splitting theorem. We now develop the complementary structure created by nonnegativity. The basic observation is that the nonnegative vectors in a factor space form an intrinsic polyhedral cone. Its facets record support information that is invisible to ordinary linear dimension. We use these facets to associate a signature to each factor, then combine the signatures across modes into a bridge graph. The final result of the section shows that if this bridge graph is disconnected, then a positive exchange must itself decompose into smaller exchanges.

4.1

Intrinsic Cones and Facet Signatures

Let W be a linear subspace of Rn . Call W admissible if it is spanned by its nonnegative vectors, i.e., W = span W ∩ Rn≥0 . For admissible W , define the intrinsic cone C(W ) = W ∩ Rn≥0 . Throughout this section, W is admissible with dim W ≥ 1; this is the only case needed below, since all factor spaces considered later contain nonzero nonnegative vectors. The following lemma identifies the facet structure of the intrinsic cone. In particular, although C(W ) may lie in a lower-dimensional subspace of Rn , every facet is still exposed by one of the original coordinate functionals. Lemma 4 (Structure of the intrinsic cone). Let W ⊆ Rn be admissible with dim W ≥ 1. Then: (i) C(W ) is a polyhedral cone that is pointed and full-dimensional in W ; (ii) every facet F of C(W ) has the form F = C(W ) ∩ {x ∈ Rn : xi = 0} for at least one coordinate i whose functional x 7→ xi is not identically zero on W ; (iii) if a facet F satisfies F = C(W ) ∩ {xi = 0} = C(W ) ∩ {xk = 0} for two coordinates i, k, then the restrictions of xi and xk to W are positive multiples of one another; (iv) choosing for every facet F one coordinate i(F ) as in (ii), one has

C(W ) = x ∈ W : xi(F ) ≥ 0 for every facet F of C(W ) . Proof. (i). The cone C(W ) is the intersection of the subspace W with the finitely many closed halfspaces {x ∈ Rn : xi ≥ 0}, i ∈ [n], and is therefore polyhedral. It is pointed because C(W ) ∩ (−C(W )) ⊆ Rn≥0 ∩ (−Rn≥0 ) = {0}. 9

It is full-dimensional in W because admissibility gives span C(W ) = W. (ii). Let Z = {i ∈ [n] : xi = 0 for all x ∈ W } be the set of coordinates that vanish identically on W . Let F be a facet of C(W ) and choose z ∈ relint F . We claim that zi = 0 for some i ∈ / Z. Otherwise zi > 0 for every i ∈ / Z. Since there are only finitely many such coordinates, all these inequalities remain strict in a neighborhood of z in W , while the coordinates in Z vanish identically on W . Hence z ∈ relint C(W ), contradicting the fact that a point in the relative interior of a proper face cannot lie in the relative interior of the full-dimensional polyhedron (Rockafellar, 1970, Theorem 6.2, Corollary 18.1.3). Thus choose i ∈ / Z with zi = 0 and set G = C(W ) ∩ {xi = 0}. The functional x 7→ xi is nonnegative on C(W ), so G is an exposed face. Since i ∈ / Z, this functional is not identically zero on W , hence it is positive at some point of C(W ) and therefore G ̸= C(W ). We next show that F ⊆ G. The functional φ(x) = xi is nonnegative on C(W ) and vanishes at z ∈ relint F . For any y ∈ F , the relative interior property implies that the segment from y to z can be extended beyond z while remaining in F (Rockafellar, 1970, Theorem 6.4). Hence there exist y ′ ∈ F and µ ∈ (0, 1) such that z = µy + (1 − µ)y ′ . Since φ(y), φ(y ′ ) ≥ 0 and φ(z) = 0, we obtain φ(y) = 0, so y ∈ G. Finally, F = G. Since F is a facet, dim F = dim W − 1. Moreover F ⊆ G ⊊ C(W ), so dim G ≤ dim W − 1. Since F ⊆ G, dim G ≥ dim F , and therefore dim G = dim F . Thus F = G = C(W ) ∩ {xi = 0}. (iii). Let H = span F . Since F is a facet of the full-dimensional cone C(W ), H is a hyperplane of W . The restrictions φi = xi |W , φk = xk |W both vanish on F and hence on H. Neither is identically zero on W , because each corresponding coordinate defines a proper face. Their kernels therefore equal the hyperplane H, so the two functionals are proportional: φk = λφi for some λ ̸= 0. Choose c ∈ C(W ) with φi (c) > 0. Since φk (c) ≥ 0, we obtain λ > 0. (iv). The inclusion “⊆” is immediate. For the converse, observe that C(W ) is a pointed, fulldimensional polyhedral cone in W . Hence it is the intersection of the halfspaces defined by its facets (Schrijver, 1986, Theorem 8.1). By parts (ii)–(iii), each facet halfspace can be represented by a coordinate functional x 7→ xi(F ) restricted to W . Thus

C(W ) = x ∈ W : xi(F ) ≥ 0 for every facet F .

The preceding lemma shows that the facet structure of C(W ) can be represented entirely by coordinate functionals. Although several coordinates may define the same facet, Lemma 4(iii) shows that such representatives differ only by positive scaling. This allows us to record which facets are strictly positive for a given vector. Let F(W ) denote the finite set of facets of C(W ) and choose, for each F ∈ F (W ), one coordinate representative i(F ). Define the facet-coordinate map LW : W −→ RF (W ) ,

LW x = xi(F ) F ∈F (W ) .

By Lemma 4(iii), changing the representative of a facet only rescales the corresponding coordinate by a positive constant. Lemma 5. The map LW is linear and injective, and it maps C(W ) into the nonnegative orthant F (W ) R≥0 . In particular, every nonzero x ∈ C(W ) has a nonempty positive facet signature AW (x) = {F ∈ F(W ) : xi(F ) > 0} = supp(LW x) ̸= ∅,

(2)

and AW (λx) = AW (x)

for every λ > 0.

Proof. Linearity is immediate, and LW x is entrywise nonnegative whenever x ∈ C(W ). Suppose LW x = 0 for some x ∈ W . Then xi(F ) = 0 for every facet F . By Lemma 4(iv), both x and −x satisfy all facet inequalities, so x ∈ C(W ) ∩ (−C(W )) = {0}. Thus LW is injective. In particular, LW x ̸= 0 whenever x ̸= 0, which proves that every nonzero x ∈ C(W ) has a nonempty signature. Invariance under positive rescaling is immediate. The signature AW (x) records the facets on which x has a strictly positive coordinate representative. Two nonzero vectors in the same intrinsic cone may nevertheless have disjoint signatures; Figure 1 illustrates this phenomenon. This observation motivates the notion of facet-opposite factors used below.

4.2

Bridge Graphs and Rectangular Splitting

We now combine facet signatures across modes. Fix a finite index set S and, for each mode j, a family of nonzero nonnegative vectors n

j x(j) r ∈ R≥0 ,

r ∈ S,

together with an admissible subspace Wj ⊆ Rnj containing all of them. Write Aj (r) = AWj x(j) ⊆ F(Wj ), r

r ∈ S.

These signatures are nonempty by Lemma 5. Definition 3 (Bridge graph). Two indices r, s ∈ S are facet-opposite in mode j with respect to Wj if Aj (r) ∩ Aj (s) = ∅. The bridge graph Γ = Γ (Wj )j

has vertex set S and an edge {r, s} whenever r ̸= s are facet-opposite in at most one mode. 11

(a)F = C(U ) ∩ {x = 0}

(b)

F4 : {x4 = 0}

e1 +e3 : {F1 , F3 }

{F1 , F2 , F3 } F1 {x1 = 0}

F2 {x2 = 0}

fa c

C(U )

os it e

y = (0, 1, 1)

et -o

{F1 , F2 , F3 , F4 }

x = (1, 1, 0) x1

Fx = C(U ) ∩ {x3 = 0}

e2 +e4 : {F2 , F4 }

F3 : {x3 = 0}

Figure 1: Intrinsic cones, facets and signatures. (a) The intrinsic cone C(U ) = U ∩ R3≥0 of the admissible plane U = span{x, y} with x = (1, 1, 0), y = (0, 1, 1): a pointed two-dimensional cone whose facets are its extreme rays, each cut out by a coordinate as in Lemma 4(ii). Each generator, x and y, lies on its own facet, so its coordinate i(F ) vanishes there and the signatures are AU (x) = {Fy } and AU (y) = {Fx }, which are disjoint. (b) The cross-section {x1 +x2 = x3 +x4 = 1} of the three-dimensional intrinsic cone of the admissible space W = {x ∈ R4 : x1 + x2 = x3 + x4 }: a cone over a square with the four facets Fi = C(W ) ∩ {xi = 0}, i(Fi ) = i. Sample points are labeled by their signatures AW (·): full in the relative interior, smaller on proper faces. The two marked corners have disjoint signatures although they lie in one and the same intrinsic cone. Thus an edge of the bridge graph means that the two components have compatible facet signatures in all but possibly one mode. This definition is chosen precisely so that bridge edges correspond to one-coordinate moves in the product of the facet sets. For each r ∈ S, define the facet box Br = A1 (r) × · · · × Ad (r) ⊆ F (W1 ) × · · · × F(Wd ) =: Ω. The box is nonempty because every factor signature is nonempty. On Ω, call two points rookadjacent if they differ in at most one coordinate. A subset of Ω is rook-connected if every two of its points can be joined by a path of rook-adjacent points lying inside the subset. Every box Br is rook-connected, since its coordinates may be changed one at a time without leaving the box. Lemma 6 (Bridges and rooks). Let U=

[

Bt ⊆ Ω.

t∈S

Two indices r, s ∈ S lie in the same connected component of the bridge graph Γ if and only if Br and Bs lie in the same rook-connected component of U . Consequently, the assignment r 7−→ the rook component of U containing Br induces a bijection between the connected components of Γ and the rook components of U . Proof. Each box Bt is rook-connected and hence is contained in a single rook component of U . The resulting assignment from bridge-graph vertices to rook components is therefore well defined and surjective. It remains to prove that two vertices belong to the same component on one side if and only if their boxes belong to the same component on the other. 12

Bridge path ⇒ same rook component. It suffices to consider a single bridge edge {r, s}. If the signatures intersect in every mode, choose fj ∈ Aj (r) ∩ Aj (s)

for all j.

Then (f1 , . . . , fd ) ∈ Br ∩ Bs , so the two boxes lie in the same rook component. Otherwise there is a unique exceptional mode j0 in which the signatures are disjoint. For every j ̸= j0 , choose fj ∈ Aj (r) ∩ Aj (s), and choose arbitrary gj0 ∈ Aj0 (s).

fj0 ∈ Aj0 (r), Then

u = (f1 , . . . , fd ) ∈ Br , while v = (f1 , . . . , fj0 −1 , gj0 , fj0 +1 , . . . , fd ) ∈ Bs . The two points differ only in coordinate j0 , so they are rook-adjacent. Since both boxes are rookconnected, they belong to the same rook component. Concatenating along a bridge path proves the implication. Same rook component ⇒ bridge path. Let u0 , u1 , . . . , um be a rook path in U with u0 ∈ Br and um ∈ Bs . For each k choose tk ∈ S such that uk ∈ Btk , taking t0 = r and tm = s. For a fixed k, the points uk and uk+1 agree in every coordinate except possibly one, say mode j0 . Therefore, for every j ̸= j0 , (uk )j = (uk+1 )j ∈ Aj (tk ) ∩ Aj (tk+1 ). Thus tk and tk+1 are facet-opposite in at most one mode. Hence either tk = tk+1 or {tk , tk+1 } is a bridge edge. The sequence t0 , . . . , tm therefore gives a walk from r to s in Γ. Figure 2 gives a three-mode illustration. The key point is that bridge edges correspond exactly to rook-compatible transitions between facet boxes, whereas a disconnected bridge graph causes the union of the boxes to separate into distinct rook components. Lemma 7 (Rectangular splitting). Let X

Xr =

r∈S

s∈J

be a positive exchange. Choose nonnegative factors (d) Xr = x(1) r ⊗ · · · ⊗ xr ,

Ys = ys(1) ⊗ · · · ⊗ ys(d)

according to Convention 1. Suppose that for every mode j there is an admissible subspace Wj ⊆ Rnj (j) containing all mode-j factors of both sides. If the bridge graph of the family (xr )r∈S with respect to (Wj )j is disconnected, then the exchange is reducible. 13

(a)

(b)

Γ: edge 1 2

Γ: no edge 1 2

K2 B2 B2 B1

mode 3

rook step: coordinate 1 mode 2

mode 2 K1 mode 1

mode 1

Figure 2: Boxes and rooks in the signature space Ω, for two indices r ∈ {1, 2} with facet boxes B1 = {1, 2} × {1, 2} × {1} (blue) and an orange box B2 . (a) B2 = {3} × {2} × {1, 2}: the mode-1 signatures {1, 2} and {3} are disjoint, but the signatures intersect in modes 2 and 3, so the pair is facet-opposite in exactly one mode, i.e. a bridge edge (Definition 3). Correspondingly, one rook step changing only the first coordinate crosses from B1 to B2 , as in the proof of Lemma 6: the boxes lie in a single rook component. (b) B2 = {3} × {3} × {1, 2}: the signatures are disjoint in modes 1 and 2, no bridge edge exists, and every step between the boxes would have to change two coordinates at once; the union splits into two rook components K1 ⊔ K2 . Since nonnegative entries cannot cancel, the support of the exchanged tensor is the union of all boxes, each competing box Bs′ (grey) lies inside a single component, and restricting the exchange to K1 and K2 produces the subexchanges of Lemma 7: the exchange is reducible. Proof. All factors are nonnegative vectors in Wj , hence belong to C(Wj ). Consider the tensorproduct map Λ = LW1 ⊗ · · · ⊗ LWd : W1 ⊗ · · · ⊗ Wd −→ RF (W1 ) ⊗ · · · ⊗ RF (Wd ) ∼ = RΩ . Each LWj is injective by Lemma 5, so Λ is injective. For a product tensor z (1) ⊗ · · · ⊗ z (d) , z (j) ∈ C(Wj ) \ {0}, we have Λ z (1) ⊗ · · · ⊗ z (d) = LW1 z (1) ⊗ · · · ⊗ LWd z (d) .

This is entrywise nonnegative on Ω, and its support is the box supp(LW1 z (1) ) × · · · × supp(LWd z (d) ). In particular, supp(ΛXr ) = Br , and supp(ΛYs ) = Bs′ :=

d Y

AWj ys(j) ,

j=1

where all these boxes are nonempty. Applying Λ to the exchange gives M :=

ΛXr =

r∈S

X s∈J

ΛYs .

Since both sides are sums of entrywise nonnegative tensors, no cancellation can occur, and therefore supp M =

[

Br =

r∈S

[

Bs′ =: U.

s∈J

In particular, every competing box Bs′ is contained in U . Now decompose U = K1 ⊔ · · · ⊔ Kc into rook-connected components. Since the bridge graph is disconnected, Lemma 6 gives c ≥ 2. Every prescribed box Br and every competing box Bs′ is rook-connected, so each is contained in a single component. Define Sℓ = {r ∈ S : Br ⊆ Kℓ },

Jℓ = {s ∈ J : Bs′ ⊆ Kℓ },

ℓ = 1, . . . , c.

These sets partition S and J. Each Sℓ is nonempty because every point of Kℓ belongs to some prescribed box Br , and that entire box is rook-connected and hence contained in Kℓ . For each ℓ, put X X ΛYs . ΛXr , Nℓ = Mℓ = s∈Jℓ

r∈Sℓ

Both tensors are supported in Kℓ . At every point of Kℓ , all terms belonging to other components vanish, so Mℓ = M = N ℓ on Kℓ ; both sides vanish outside Kℓ . Hence Mℓ = Nℓ on all of Ω. Moreover Jℓ ̸= ∅. Otherwise Nℓ = 0, whereas [

supp Mℓ =

Br ̸= ∅,

r∈Sℓ

a contradiction. Since Λ is injective, X r∈Sℓ

Xr =

Ys ,

ℓ = 1, . . . , c.

s∈Jℓ

Because c ≥ 2, at least one such pair is nonempty and proper. It is therefore a nontrivial subexchange, so the original exchange is reducible. The significance of Lemma 7 is that irreducibility imposes a connectivity requirement on the factor signatures. This requirement is independent of linear dimension: it arises solely because nonnegative product tensors have rectangular supports in the signature space and cannot cancel outside those supports. In the next section, we quantify the amount of additional factor-space dimension needed to satisfy this connectivity requirement.

The Positive Scattering Term

The preceding section showed that irreducibility of a positive exchange forces connectivity of the associated bridge graph. This suggests measuring how far the minimal factor spaces are from being connected: how many additional factor-space dimensions are needed to reconnect the prescribed components while remaining inside the support hulls allowed by nonnegativity? The positive scattering term makes this quantity precise. 15

5.1

Support Confinement and the Definition of τ

Return to the decomposition (1) and fix S ⊆ [R] with |S| ≥ 2. For each mode define the support hull [ Nj (S) = supp a(j) ⊆ [nj ], Hj (S) = span{ei : i ∈ Nj (S)}, r r∈S

and write hj (S) = dim Hj (S) = |Nj (S)|. Then Uj (S) ⊆ Hj (S), and Hj (S) is admissible because it is spanned by standard basis vectors. The first observation is that the support hull is not merely a convenient restriction: it is forced by any nonnegative exchange involving the components indexed by S. Lemma 8 (Support confinement). Let X

cr Pr =

s∈J

r∈S

be a positive exchange with cr > 0, and write (d) Qs = b(1) s ⊗ · · · ⊗ bs

with nonnegative factors. Then supp b(j) ⊆ Nj (S), s

s ∈ J,

j ∈ [d].

Equivalently, b(j) s ∈ Hj (S)

for all s ∈ J, j ∈ [d].

Proof. Suppose, to the contrary, that for some s ∈ J and some mode j there is i0 ∈ supp b(j) \ Nj (S). s

For every mode l ̸= j, choose il ∈ supp b(l) s ,

which is possible because the factors are nonzero. Consider the entry of the exchange indexed by (i1 , . . . , id ). The term Qs contributes b(j) s (i0 )

b(l) s (il ) > 0,

l̸=j

so the right-hand side is strictly positive. On the left, every term cr Pr vanishes at this index because (j) i0 ∈ / Nj (S) implies ar (i0 ) = 0 for every r ∈ S. This is a contradiction. Thus every competing nonnegative factor in an exchange involving S is confined to the coordinate subspaces Hj (S). We therefore measure connectivity only through intermediate spaces lying between the prescribed factor spans and these support hulls. Call a tuple of subspaces (W1 , . . . , Wd ) 16

admissible for S if, for every j, Uj (S) ⊆ Wj ⊆ Hj (S) and Wj is admissible. Call the tuple feasible for S if its associated bridge graph, as defined in Section 4.2, is connected. Definition 4 (Positive scattering). The positive scattering term of S is τ (S) = min

 d X 

dim Wj − dj (S) : (W1 , . . . , Wd ) is feasible for S

 

(3)



j=1

with τ (S) = +∞ if no feasible tuple exists. The interpretation is straightforward. The minimal choice Wj = Uj (S) uses no additional dimensions and gives the original bridge graph Γ0 (S). Enlarging Wj can create new facet intersections and thereby add bridge edges. The quantity τ (S) is the minimum total number of dimensions that must be added across the modes before the bridge graph becomes connected. Remark 2 (Well-definedness and invariance). Whenever a feasible tuple exists, the minimum in (3) is attained because the possible costs are nonnegative integers bounded above by d X

hj (S) − dj (S) .

j=1

The value τ (S) is invariant under positive rescaling of the factors: such rescaling changes neither the spaces Uj (S) and Hj (S) nor the facet signatures. It is also invariant under relabeling of the components and under permutations of coordinates within a mode. Finally, ambient coordinates that are identically zero do not affect τ (S), because support confinement restricts attention to the support hulls. The remainder of this section gives an exact finite characterization of (3). The key observation is that connectivity can be built edge by edge, so the continuous optimization over subspaces can first be separated by mode and then reduced to spanning trees.

5.2

Mode Costs and the Tree Formula

Fix a mode j and a finite set F of unordered pairs of elements of S. Define n

κj (F ) = min dim W − dj (S) : W admissible, Uj (S) ⊆ W ⊆ Hj (S), AW a(j) ∩ AW a(j) ̸= ∅ r s

for every {r, s} ∈ F ,

with κj (F ) = +∞ if no such W exists, and κj (∅) = 0. The quantity κj (F ) is the minimum number of dimensions that must be added in mode j in order to make all pairs in F have intersecting facet signatures. The following lemma gives the first simplification. 17

Lemma 9 (Finiteness of κj (F )). For every finite set F of pairs, κj (F ) < ∞ if and only if supp a(j) ∩ supp a(j) ̸= ∅ r s

for every {r, s} ∈ F . When finite, 0 ≤ κj (F ) ≤ hj (S) − dj (S). Proof. Suppose first that κj (F ) < ∞, and let W be admissible for which all required signature intersections are nonempty. For {r, s} ∈ F , choose F0 ∈ AW a(j) ∩ AW a(j) r s .

The corresponding coordinate is strictly positive for both factors, so their ordinary supports intersect. Conversely, suppose all required pairs have intersecting ordinary supports. Take W = Hj (S). Then C(W ) is the full nonnegative orthant on the support coordinates Nj (S), and its facets are exactly the coordinate hyperplanes xi = 0, i ∈ Nj (S). Hence facet signatures coincide with ordinary supports. All required signature intersections therefore hold, and the cost is hj (S) − dj (S). The lower bound is immediate from W ⊇ Uj (S). It is useful to view a pair as being resolved in a mode when its two signatures intersect. The next result shows that only a spanning tree of such pairwise requirements is needed. For a spanning tree T of the complete graph on S and a map ε : E(T ) → [d], call ε(e) the exempted mode of edge e. Define Fj (T, ε) = {e ∈ E(T ) : ε(e) ̸= j}. Thus mode j is required to resolve every tree edge except those exempted to j. Proposition 1 (Tree formula). For every S ⊆ [R] with |S| ≥ 2, τ (S) = min (T,ε)

d X

κj Fj (T, ε) ,

(4)

j=1

where (T, ε) ranges over all spanning trees of the complete graph on S and all exemption maps. Both sides may equal +∞. Proof. Let ρ denote the right-hand side. ρ ≤ τ (S). Assume τ (S) < ∞ and let (Wj )j be a feasible tuple attaining the minimum. Its bridge graph is connected, so it contains a spanning tree T . For every edge e = {r, s} ∈ E(T ),

choose an exempted mode ε(e) in which r, s are allowed to be facet-opposite. Such a mode exists because e is a bridge edge. Hence, for every j ̸= ε(e), AWj a(j) ∩ AWj a(j) ̸= ∅. r s

Thus Wj is admissible in the definition of κj (Fj (T, ε)), and κj (Fj (T, ε)) ≤ dim Wj − dj (S). Summing over j gives ρ ≤ τ (S). τ (S) ≤ ρ. Suppose ρ < ∞ and fix (T, ε) attaining the minimum. For each mode choose an admissible Wj attaining κj (Fj (T, ε)). (j)

(j)

For every edge e = {r, s} ∈ E(T ) and every j ̸= ε(e), the signatures of ar and as intersect. Thus e is facet-opposite in at most the one mode ε(e), so every edge of T is a bridge edge for the tuple (Wj )j . The resulting bridge graph contains the spanning tree T and is therefore connected. Hence the tuple is feasible and τ (S) ≤

d X

dim Wj − dj (S) = ρ.

j=1

For two components, the formula takes a particularly simple form. If S = {r, s}, the unique spanning tree consists of the single edge e = {r, s}. Exempting mode j0 gives (

Fj =

{e}, ∅,

j ̸= j0 , j = j0 ,

and therefore τ ({r, s}) = min

j0 ∈[d]

5.3

κj {e} .

(5)

j̸=j0

Exact Mode Costs

The remaining question is how difficult the mode costs κj (F ) are to compute. The answer is particularly simple: for each pair, the cost is always 0, 1, or +∞. We establish this in one mode and suppress the mode index and the set S. Delete coordinates that vanish identically on the support hull and write H = Rm ,

U = span{ar : r ∈ S} ⊆ H,

ar .

r∈S

By construction, i ∈ [m].

pi > 0, For an intermediate space U ⊆ W ⊆ H, define

E(W ) = {i ∈ [m] : C(W ) ∩ {xi = 0} is a facet of C(W )}. If several coordinates define the same facet, all such coordinates belong to E(W ). 19

Lemma 10 (Automatic admissibility). Every intermediate subspace U ⊆W ⊆H is admissible. Proof. Let w ∈ W . Since every coordinate of p is strictly positive, there is t > 0 such that tpi + wi ≥ 0, For example, one may take t ≥ max

i: wi <0

i ∈ [m]. −wi , pi

with the maximum over the empty set interpreted as zero. Then both tp and tp + w belong to W ∩ Rm ≥0 , and w = (tp + w) − tp. Thus every vector of W lies in the linear span of its nonnegative part. For each coordinate, define the normalized functional ∗ ℓW i = ei |W ,

qiW =

ℓW i . pi

Since qiW (p) = 1, all such functionals lie in the affine hyperplane {f ∈ W ∗ : f (p) = 1}. Proposition 2 (Normalized dual polytope). Let U ⊆ W ⊆ H. (i) C(W )∗ = cone{ℓW i : i ∈ [m]}. (ii) The section P (W ) = {f ∈ C(W )∗ : f (p) = 1} satisfies P (W ) = conv{qiW : i ∈ [m]}. (iii) A coordinate i belongs to E(W ) if and only if qiW is a vertex of P (W ). (iv) For nonzero x, y ∈ C(W ), AW (x) ∩ AW (y) ̸= ∅

⇐⇒

E(W ) ∩ supp(x) ∩ supp(y) ̸= ∅.

Proof. (i). The inclusion ∗ cone{ℓW i : i ∈ [m]} ⊆ C(W )

is immediate because each coordinate functional is nonnegative on C(W ). For the reverse inclusion, let K = cone{ℓW i : i ∈ [m]}

and suppose f ∈ C(W )∗ \ K. Since K is a closed polyhedral cone, there exists x ∈ W such that g(x) ≥ 0

for all g ∈ K,

f (x) < 0.

In particular, xi = ℓW i (x) ≥ 0

for all i,

so x ∈ C(W ). This contradicts f ∈ C(W )∗ . Hence C(W )∗ = K. (ii). Write X f= αi ℓW αi ≥ 0. i , i

Since f (p) = 1, 1=

αi pi .

Putting βi = αi pi gives βi ≥ 0,

i βi = 1, and

βi qiW .

Thus P (W ) = conv{qiW : i ∈ [m]}. (iii). Because every coordinate of p is strictly positive, p lies in relint C(W ). Hence every nonzero element of C(W )∗ is strictly positive at p, and the section P (W ) meets each nonzero ray of C(W )∗ exactly once. Under this correspondence, extreme rays of C(W )∗ are precisely the vertices of P (W ). Since facets of the full-dimensional pointed cone C(W ) correspond to extreme rays of its dual cone, and the coordinate ray generated by ℓW i defines a facet exactly when i ∈ E(W ), the equivalence follows. (iv). A facet belongs to both signatures precisely when some coordinate representative i ∈ E(W ) is strictly positive for both x and y. If multiple coordinates define the same facet, their restrictions to W are positive multiples of one another by Lemma 4(iii), so the condition is independent of the representative. The key geometric fact is that, once U is enlarged at all, one additional dimension is enough to make every effective coordinate define a facet. Geometrically, the normalized coordinate functionals form a finite configuration in an affine hyperplane. One additional height coordinate can be chosen so that all relevant points become exposed vertices of the lifted convex hull. This is what turns the apparently continuous enlargement problem into the discrete 0/1/ + ∞ trichotomy below. Proposition 3 (One-dimensional facet saturation). If U ⊊ H, there exists z ∈ H \ U such that W = U + Rz satisfies dim W = dim U + 1

and

E(W ) = [m].

Proof. Put k = dim U and consider the affine hyperplane A = {b ∈ U ∗ : b(p) = 1}. For each coordinate define bi =

e∗i |U ∈ A. pi

These points affinely span A. Let Aff(A) denote the vector space of real affine functions on A. Indeed, the map Φ : U −→ Aff(A), Φ(u)(b) = b(u), is injective: if Φ(u) = 0, then 0 = bi (u) =

ui pi

for every i, hence u = 0. Since both spaces have dimension k, Φ is an isomorphism. Thus a nonzero affine function cannot vanish at every bi , which proves that the bi affinely span A. Let b(1) , . . . , b(g) be the distinct points among the bi . Since they affinely span the (k − 1)-dimensional space A, we have g ≥ k. Assign heights hi and set zi = pi hi . If z ∈ / U , then W = U ⊕ Rz. Under the identification {f ∈ W ∗ : f (p) = 1} ∼ = A × R, the normalized coordinate functional qiW corresponds to the lifted point (bi , hi ). If g > k, choose an inner product on A and set h0α = ∥b(α) ∥2 . For each α, the affine function Lα (x) = 2⟨b(α) , x⟩ − ∥b(α) ∥2 satisfies ∥b(β) ∥2 − Lα (b(β) ) = ∥b(β) − b(α) ∥2 > 0,

β ̸= α.

Thus every lifted point (b(α) , h0α ) is strictly exposed from below. If these heights are already nonaffine in the base points, we are done. Otherwise, choose a class-height perturbation δ = (δα ) outside the space of affine height vectors and put hα = h0α + εδα

for sufficiently small ε > 0. The strict exposure inequalities persist, while the perturbed heights are no longer affine. If g = k, then the distinct base points are affinely independent. Since U ⊊ H, we have m > k, so some base point occurs for at least two coordinates; say bi0 = bi1 . Set hi = 0

hi0 = 1,

(i ̸= i0 ).

The distinct lifted points are then (b(1) , 1),

(b(1) , 0),

(b(2) , 0), . . . , (b(k) , 0),

after relabeling. Their difference vectors are linearly independent, so they are the vertices of a k-simplex. Again the heights are not affine. In either case, z ∈ / U and every normalized coordinate functional is a vertex of P (W ). Proposition 2 therefore gives E(W ) = [m].

Proposition 4 (Exact mode-cost trichotomy). For every finite set F of unordered pairs,

κ(F ) =

  +∞,  

if some {r, s} ∈ F has disjoint ordinary supports,

   

otherwise.

if AU (ar ) ∩ AU (as ) ̸= ∅ for every {r, s} ∈ F,

Here κ(∅) = 0. Proof. If some required pair has disjoint ordinary supports, Lemma 9 gives κ(F ) = +∞. If all required signatures already intersect in U , then W = U is feasible with cost zero, so κ(F ) = 0. It remains to consider the case in which every required pair has nonempty ordinary support intersection but at least one pair has disjoint signatures in U . Then cost zero is impossible because a zero-cost space must equal U . Moreover U ̸= H: if U = H, the signatures in U are simply ordinary supports, contradicting the assumption that some required pair has disjoint signatures. Hence Proposition 3 provides a one-dimensional extension with E(W ) = [m]. Every pair with intersecting ordinary supports then has intersecting signatures by Proposition 2, so κ(F ) = 1. Since the only finite values are 0 and 1, the cost for a collection of pairs is determined by the worst pair: κj (F ) = max κj (e), F ̸= ∅, (6) e∈F

where κj (e) = κj ({e}) ∈ {0, 1, +∞}.

5.4

The Activation Formula

The tree formula and the trichotomy together turn the definition of τ (S) into a finite graph problem. For A ⊆ [d], interpret the modes in A as activated: in an activated mode we allow the onedimensional extension supplied by Proposition 3. Define GA (S) to be the graph on S in which e = {r, s} is an edge whenever o

# j ∈ [d] : κj (e) = +∞ or κj (e) = 1 and j ∈ /A

≤ 1.

Thus a pair is a bridge precisely when, after activation of the modes in A, there is at most one mode in which its connectivity remains unresolved. Theorem 3 (Activation formula). Let S ⊆ [R] with |S| ≥ 2. (i)

τ (S) = min |A| : A ⊆ [d], GA (S) is connected , with the minimum over an empty family interpreted as +∞. (ii) G∅ (S) = Γ0 (S), and hence τ (S) = 0

⇐⇒

Γ0 (S) is connected.

(iii) τ (S) < ∞ if and only if G[d] (S) is connected. In particular, τ (S) ≤ #{j : Uj (S) ̸= Hj (S)} ≤ d whenever τ (S) < ∞. Proof. Part (i). Suppose GA (S) is connected. For every inactive mode j ∈ / A, take Wj = Uj (S). For every active mode j ∈ A with Uj (S) ⊊ Hj (S), choose a one-dimensional saturated extension from Proposition 3; if Uj (S) = Hj (S), retain Wj = Uj (S). The resulting tuple has cost at most |A|. In an inactive mode, a pair with κj (e) = 0 has intersecting signatures, while a pair with κj (e) ≥ 1 is facet-opposite. In an active mode, saturation resolves every pair having nonempty ordinary support intersection, leaving only pairs with κj (e) = +∞. Therefore the bridge graph of the constructed tuple is exactly GA (S) and is connected. Hence τ (S) ≤ |A|. Minimizing over connected GA (S) gives τ (S) ≤ min{|A| : GA (S) connected}. Conversely, let (Wj )j be a feasible tuple and define A = {j : Wj ̸= Uj (S)}. 24

Every active mode contributes at least one dimension, so |A| ≤

dim Wj − dj (S) .

Replace each active space by a one-dimensional saturated extension of Uj (S). This cannot destroy any bridge edge: if a pair had intersecting signatures in the original space, its ordinary supports intersect, and saturation preserves that intersection; if its ordinary supports are disjoint, no admissible extension can resolve the pair. Hence the resulting bridge graph is GA (S) and remains connected. Therefore min{|A| : GA (S) connected} ≤

dim Wj − dj (S) .

Minimizing over feasible tuples proves (i). Part (ii). By the trichotomy, κj (e) = 0 (j) (j) holds exactly when the signatures of ar and as intersect in the minimal space Uj (S).

Consequently an edge of G∅ (S) is precisely a pair that is facet-opposite in at most one mode, which is the definition of an edge of Γ0 (S). Part (iii). When A = [d], the cost-one obstruction is always activated, so an edge fails to occur only if κj (e) = +∞ in at least two modes. By Lemma 9, this is exactly the case in which the ordinary supports are disjoint in at least two modes. Thus G[d] (S) is the graph obtained by requiring ordinary support intersections in all but at most one mode. If τ (S) < ∞, then some GA (S) is connected, hence so is G[d] (S) because the graphs are monotone in A. Conversely, suppose G[d] (S) is connected and put A∗ = {j : Uj (S) ̸= Hj (S)}. If Uj (S) = Hj (S), then the signatures in mode j equal ordinary supports, so no pair has κj (e) = 1 in that mode. Therefore GA∗ (S) = G[d] (S), which is connected. Part (i) gives τ (S) ≤ |A∗ | = #{j : Uj (S) ̸= Hj (S)} ≤ d.

Remark 3 (Exact computation). Theorem 3 gives an exact finite procedure for computing τ (S). First, for each mode, ordinary support intersections determine which pair costs are +∞. For a support-intersecting pair, the distinction between costs 0 and 1 is determined by whether the corresponding normalized coordinate functionals are vertices of P (Uj (S)), by Proposition 2. After this preprocessing, τ (S) is obtained by checking activation sets A ⊆ [d] in increasing order of cardinality until GA (S) becomes connected. For rational input data, the vertex tests can be formulated as linear programming feasibility problems. Thus, for fixed tensor order d, the postprocessing after the vertex tests consists of at most 2d graph connectivity problems and is polynomial in |S|. The full identifiability certificate still quantifies over all subsets S ⊆ [R], so the criterion as a whole need not be polynomial-time in R. 25

The resulting computation is summarized in Algorithm 1. The algorithm first determines the facet-coordinate sets for the minimal spaces Uj (S), then computes the pair costs κj (e), and finally searches over activation sets. Algorithm 1 Exact computation of τ (S) (j)

Require: S ⊆ [R], |S| ≥ 2, and the factors ar . Ensure: τ (S). 1: for j ∈ [d] do P (j) (j) (j) 2: p(j) ← r∈S ar and qi ← (e∗i |Uj (S) )/pi for i ∈ Nj (S). 3:

(j)

Group equal qi ’s and determine, by LP vertex tests, (j) (j) Ej ← {i ∈ Nj (S) : qi ∈ vert conv{qℓ : ℓ ∈ Nj (S)}}. for all e = {r, s} ∈ S2 do (j)

(j)

Ij (e) ← supp(a r ) ∩ supp(as ).    +∞, Ij (e) = ∅, 6: κj (e) ← 0, Ij (e) ∩ Ej ̸= ∅,   1, otherwise. 7: end for 8: end for 9: for all A ⊆ [d], in nondecreasing order of |A| do 10: GA (S) ← S, {e ∈ S2 : bA (e) ≤ 1} , where bA (e) = #{j : κj (e) = +∞ or (κj (e) = 1 and j ∈ / A)}. 11: if GA (S) is connected then 12: return |A|. 13: end if 14: end for 15: return +∞. 5:

Proof of the Main Criterion

The proof of Theorem 1 combines the two mechanisms developed above. The Lovitz–Petrov splitting theorem gives a constraint on the linear dimension of an irreducible exchange, while the support geometry forces the factor spaces of that exchange to pay the additional scattering cost τ (S). The two effects combine in the positive splitting inequality below. The minimality and uniqueness statements then follow by applying this inequality to an irreducible block of a competing decomposition.

6.1

The Positive Splitting Inequality

Fix S ⊆ [R] with |S| ≥ 2 and consider an irreducible positive exchange X r∈S

cr Pr =

Qs ,

cr > 0,

(7)

s∈J

where the left-hand side consists of positive multiples of the prescribed terms indexed by S and the right-hand side consists of nonzero nonnegative rank-one tensors (d) Qs = b(1) s ⊗ · · · ⊗ bs

with nonnegative factors. Put U = span{Pr : r ∈ S},

V = span{Qs : s ∈ J},

h = dim(U ∩ V ),

and, for each mode, Vj = span{b(j) s : s ∈ J},

Wj = Uj (S) + Vj .

(j)

By the support-confinement lemma, every bs belongs to Hj (S). Hence Uj (S) ⊆ Wj ⊆ Hj (S). Moreover, each Wj is admissible because it is spanned by nonnegative vectors. Thus (Wj )j is an admissible tuple for S. Finally, h ≥ 1: the common value of the two sides of (7) is a nonzero nonnegative tensor and therefore belongs to both U and V . Theorem 4 (Positive splitting inequality). For every irreducible positive exchange (7), β(S) + τ (S) ≤ dim U + dim V − 2.

(8)

In particular, if the two sides contain p = |S| and q = |J| terms, respectively, then β(S) + τ (S) ≤ p + q − 2. Proof of Theorem 4. Step 1: Irreducibility implies connectedness. Absorb a minus sign into one factor of each Qs , say the mode-1 factor, and consider the signed multiset of nonzero product tensors E = {cr Pr : r ∈ S} ∪ {−Qs : s ∈ J}. The sum of all elements of E is zero. We claim that E is connected in the sense of Definition 2. Suppose instead that E = E1 ⊔ E2 ,

span E = span E1 ⊕ span E2 ,

with both E1 and E2 nonempty. Let σk denote the sum of the elements of Ek . Then σk ∈ span Ek .

σ1 + σ2 = 0, Since the sum is direct,

σ1 = σ2 = 0. Let Ik ⊆ S and Jk ⊆ J be the indices of the terms of Ek originating from the two sides of the exchange. Then X X cr Pr = Qs , k = 1, 2. r∈Ik

s∈Jk

Neither Ek can contain terms from only one side: if, for instance, J1 = ∅, then X

cr Pr = 0,

r∈I1

which is impossible because all terms are nonzero and nonnegative. Thus I1 , J1 , I2 , J2 ̸= ∅. 27

Consequently (I1 , J1 ) is a nontrivial subexchange of (7), contradicting irreducibility. Hence E is connected. Step 2: The exchange pays the scattering cost. (1) (j) The mode-j factors of the left side of (7) may be taken to be cr ar in mode 1 and ar in (j) the remaining modes. Together with the factors bs on the right, they all belong to Wj . Positive rescaling does not change facet signatures. If the bridge graph of the prescribed factors with respect to (Wj )j were disconnected, the rectangular splitting lemma (Lemma 7) would imply that the exchange is reducible. Hence this bridge graph is connected, so (Wj )j is feasible for S. By the definition of τ (S), τ (S) ≤

d X

dim Wj − dj (S) .

(6.1)

j=1

Step 3: Dimension counting. The span of the signed family E is span E = U + V. In each mode, the factors appearing in E span exactly Wj , so the mode-j rank of E is rj = dim Wj . Since E is connected, it does not split. The contrapositive of the Lovitz–Petrov splitting theorem therefore gives dim span E >

d X

(rj − 1) =

d X

(dim Wj − 1).

j=1

All quantities are integers, hence d X

(dim Wj − 1) ≤ dim(U + V ) − 1.

j=1

Using dim(U + V ) = dim U + dim V − h, we obtain

d X

(dim Wj − 1) ≤ dim U + dim V − h − 1.

j=1

Since β(S) =

d X

(dj (S) − 1),

j=1

this can be rewritten as β(S) +

d X

dim Wj − dj (S) ≤ dim U + dim V − h − 1.

j=1

Combining this with (6.1) and h ≥ 1 gives β(S) + τ (S) ≤ dim U + dim V − h − 1 ≤ dim U + dim V − 2, 28

which proves (8). Since dim U ≤ |S| = p,

dim V ≤ |J| = q,

the final bound follows. Remark 4 (Mechanism). The positive splitting inequality combines two distinct obstructions to an irreducible exchange. The Lovitz–Petrov argument bounds the linear dimension of a connected family of product tensors and produces the dimension budget β(S). Nonnegativity provides a second obstruction: support confinement restricts the competing factors to the support hulls, and irreducibility forces the corresponding bridge graph to be connected. The minimum dimension increment needed to achieve this connectivity is exactly τ (S). Finally, positivity implies that the two sides of the exchange have a common nonzero tensor, so h = dim(U ∩ V ) ≥ 1, producing the additional unit in the final bound.

6.2

Minimality and Uniqueness

Proof of Theorem 1. Part (i): Minimality. Suppose, to the contrary, that rank+ (T ) < R. Let T =

q X

s=1

be a minimal nonnegative decomposition, where q < R. Then R X

Pr =

r=1

q X

s=1

is a positive exchange. Decompose it into irreducible blocks (Ik , Jk ),

k = 1, . . . , m,

using Lemma 3(i). Every Jk is nonempty by Remark 1. Since m X

|Ik | = R > q =

k=1

m X

|Jk |,

k=1

there exists a block for which pk := |Ik | > |Jk | =: qk . In particular, pk ≥ 2. Applying Theorem 4 to this irreducible block gives β(Ik ) + τ (Ik ) ≤ pk + qk − 2 ≤ 2pk − 3. On the other hand, condition (M) applied to S = Ik gives β(Ik ) + τ (Ik ) ≥ 2pk − 2, 29

a contradiction. Hence rank+ (T ) = R. The prescribed decomposition is therefore minimal, and its terms are linearly independent by Lemma 2. Part (ii): Uniqueness. Assume condition (U). Since 2|S| − 1 ≥ 2|S| − 2, condition (M) also holds, so Part (i) implies rank+ (T ) = R. Let T =

R X

s=1

be any nonnegative decomposition of length R. It is minimal, as is the prescribed decomposition. Hence Lemma 3(ii) implies that every irreducible block (Ik , Jk ) in the exchange R X

Pr =

R X

s=1

r=1

is balanced: |Ik | = |Jk | =: pk . If some block had pk ≥ 2, then Theorem 4 would yield β(Ik ) + τ (Ik ) ≤ 2pk − 2, whereas condition (U) requires β(Ik ) + τ (Ik ) ≥ 2pk − 1. This is impossible. Hence every irreducible block is a singleton: Pr = Qs(r) for a bijection r 7→ s(r). The two decompositions therefore have the same multiset of rank-one terms and are equivalent. Remark 5 (The two thresholds). The two parts of Theorem 1 differ only in the possible size of an irreducible competing block. A shorter decomposition necessarily produces an unbalanced block with |Jk | ≤ |Ik | − 1, so the positive splitting inequality yields the upper bound β(Ik ) + τ (Ik ) ≤ 2|Ik | − 3. For two decompositions of the same minimal length, every block is balanced; a nontrivial block then has β(Ik ) + τ (Ik ) ≤ 2|Ik | − 2. This is why the minimality and uniqueness thresholds differ by exactly one. 30

Structural Consequences

The positive-scattering criterion is compatible with several natural structural operations on a tensor decomposition. We first consider reshaping, which changes the grouping of the tensor modes and can increase the dimension budget. We then consider appending modes, which adds nonnegative factors and yields a monotonicity property for the combined dimension–scattering criterion.

7.1

Reshaping

Fix, for each S ⊆ [R], a partition G1 ⊔ · · · ⊔ Gt = [d],

Gℓ ̸= ∅,

where the partition may depend on S. Group the factors within each block: b(ℓ) a r =

Nℓ a(j) r ∈ R≥0 \ {0},

Nℓ =

nj .

j∈Gℓ

Under the canonical isomorphism d O

nj ∼

t O

j=1

RNℓ ,

ℓ=1

the tensor therefore admits the t-mode nonnegative decomposition T =

R X

b(1) b(t) a r ⊗ ··· ⊗ a r .

r=1

Because every grouped factor is nonzero and nonnegative, the theory of Sections 4–5 applies verbatim to the reshaped tensor whenever t ≥ 2. For the partition chosen for a given S, write βbS (·),

τbS (·)

for the corresponding dimension budget and scattering term. The following corollary allows the partition used to certify a given subset S to be chosen independently of the partitions used for other subsets. Corollary 1 (Reshaped positive criterion). Suppose that for every S ⊆ [R] with |S| ≥ 2, there exists a partition of the modes into t ≥ 2 nonempty groups such that βbS (S) + τbS (S) ≥ 2|S| − 2. Then rank+ (T ) = R. If the partitions can moreover be chosen so that βbS (S) + τbS (S) ≥ 2|S| − 1, then the decomposition (1) is unique among nonnegative decompositions of length R.

Proof. Suppose first that rank+ (T ) < R. By the block decomposition lemma, there is an irreducible positive exchange X r∈S

cr Pr =

Qs ,

cr > 0,

|S| ≥ 2,

|J| ≤ |S| − 1.

s∈J

Group the modes according to the partition chosen for this set S. The equality of the two sums is unchanged by this regrouping, and every term remains a nonzero nonnegative rank-one tensor in the reshaped tensor format. Moreover, irreducibility is a property of the exchange as an equality of sums and is therefore unchanged by regrouping the modes. Applying Theorem 4 in the grouped tensor format gives βbS (S) + τbS (S) ≤ |S| + |J| − 2 ≤ 2|S| − 3, contradicting the assumed lower bound βbS (S) + τbS (S) ≥ 2|S| − 2. Hence rank+ (T ) = R. Now assume the stronger hypothesis and suppose that T =

R X

s=1

is a nonnegative decomposition of length R that is not equivalent to (1). By the first part, the prescribed decomposition is minimal, and the competing decomposition is also minimal. Hence their exchange decomposes into irreducible balanced blocks. Inequivalence implies that at least one block (S, J) satisfies |J| = |S| ≥ 2. Regroup the modes according to the partition chosen for this S. Applying Theorem 4 in the grouped format yields βbS (S) + τbS (S) ≤ |S| + |J| − 2 = 2|S| − 2, contradicting the assumed bound βbS (S) + τbS (S) ≥ 2|S| − 1. Therefore every nonnegative length-R decomposition is equivalent to (1). Thus the certificate need not be evaluated in only the original tensor format: different subsets S may use different groupings of the modes. This is useful because grouping can increase the dimensions of the grouped factor spans even when the individual mode spans are relatively small. Remark 6 (The one-block partition). The restriction t ≥ 2 is natural but causes no loss in the criterion. If all modes are grouped into a single block, then the grouped factors are the rank-one tensors Pr themselves. The resulting one-mode budget is at most |S| − 1, while the bridge graph is complete because, with only one mode, every pair is facet-opposite in at most one mode. Thus the scattering term is zero and βbS (S) + τbS (S) ≤ |S| − 1 < 2|S| − 2

(|S| ≥ 2).

Hence the one-block grouping can never by itself certify either main criterion. 32

Reshaping can genuinely strengthen the dimension budget. A standard example comes from the Khatri–Rao product, namely the columnwise product of two matrices (Khatri and Rao, 1968, pp. 169–170). Recall that the Kruskal rank of a matrix is the largest integer k such that every set of k columns is linearly independent (Kruskal, 1977, p. 102). If two factor matrices with R columns have Kruskal ranks whose sum is at least R + 1, then their Khatri–Rao product has full column rank (Sidiropoulos and Bro, 2000, Lemma 1); this may occur even when neither factor matrix has full column rank. Thus grouping modes can create linear independence that is not visible in the individual modes. We do not establish a general monotonicity relation between the scattering term before and after reshaping. In particular, the grouped scattering term may interact with the changed factor geometry in ways that are not captured by the dimension budget alone.

7.2

Appending Modes

The effect of adding new nonnegative modes is different. Here the original modes are retained, while additional factor vectors are appended to each term: ′

(d) (d+1) ) Per = a(1) ⊗ · · · ⊗ a(d r ⊗ · · · ⊗ ar ⊗ ar r ,

where

j = d + 1, . . . , d′ .

j a(j) r ∈ R≥0 \ {0},

Write βM (S) and τM (S) for the budget and scattering term computed using only the modes in a nonempty set M ⊆ [d′ ]. The dimension budget is additive across disjoint sets of modes. More importantly, the scattering term is superadditive. Proposition 5 (Superadditivity of scattering). Let I, J ⊆ [d′ ] be disjoint and nonempty. Then, for every S ⊆ [R] with |S| ≥ 2, βI∪J (S) = βI (S) + βJ (S) and τI∪J (S) ≥ τI (S) + τJ (S). Consequently,

βI∪J (S) + τI∪J (S) ≥ βI (S) + τI (S) + βJ (S) + τJ (S) . Proof. The identity for β follows immediately from its definition. For the scattering term, suppose first that τI∪J (S) < ∞ and let (Wj )j∈I∪J be a feasible tuple attaining τI∪J (S). Its bridge graph ΓI∪J is connected. Restrict this tuple to the modes in I. Any edge of ΓI∪J is facet-opposite in at most one mode among I ∪ J, and hence also in at most one mode among I. Therefore the bridge graph ΓI of the restricted tuple contains ΓI∪J and is connected. Thus the restricted tuple is feasible for I, and τI (S) ≤

dim Wj − dj (S) .

j∈I

The same argument for J gives τJ (S) ≤

dim Wj − dj (S) .

j∈J

Adding, X

τI (S) + τJ (S) ≤

dim Wj − dj (S) = τI∪J (S).

j∈I∪J

If τI∪J (S) = +∞, the inequality is immediate. This yields the following monotonicity result. Corollary 2 (Appending nonnegative modes). Suppose the decomposition (1) satisfies condition (M), respectively condition (U). Extend each term by nonzero nonnegative factors in new modes d + 1, . . . , d′ as above. Then the extended decomposition Te =

R X

Per

r=1

satisfies the same condition. Consequently, rank+ (Te ) = R under (M), while under (U) the extended decomposition is unique among nonnegative decompositions of length R. Proof. Fix S ⊆ [R] with |S| ≥ 2 and put I = [d],

J = {d + 1, . . . , d′ }.

By Proposition 5,

β[d′ ] (S) + τ[d′ ] (S) ≥ β[d] (S) + τ[d] (S) + βJ (S) + τJ (S) . Since βJ (S) ≥ 0,

τJ (S) ≥ 0,

we obtain β[d′ ] (S) + τ[d′ ] (S) ≥ β[d] (S) + τ[d] (S). Thus whichever of the two thresholds is satisfied by the original decomposition is also satisfied by the extended decomposition. Applying Theorem 1 proves the result. The superadditivity result gives a precise sense in which additional nonnegative modes can only increase the amount of structural information available to the criterion. Unlike reshaping, which changes the mode structure and therefore requires a fresh geometric analysis, appending a mode preserves the existing certificate and adds a nonnegative contribution to the combined dimension–scattering budget.

Examples

This section illustrates the two principal consequences of the positive-scattering criterion. We first give explicit deterministic families showing that the new criterion can certify nonnegative uniqueness where every dimension-based Lovitz–Petrov criterion fails, even after reshaping. We then examine the size of this gain on random sparse decompositions and search empirically for nonnegative alternatives when the criterion fails. 34

8.1

Explicit Strictness Examples

We begin with two families for which the scattering term is infinite. Thus the identifiability certificate is driven entirely by support geometry: the dimension budget may fall strictly below the Lovitz–Petrov threshold, but nonnegative decompositions cannot exchange mass across the disconnected support pattern. Example 1 (W tensor). Let n1 = n2 = n3 = 2 and T = e1 ⊗ e1 ⊗ e2 + e1 ⊗ e2 ⊗ e1 + e2 ⊗ e1 ⊗ e1 . This is, up to normalization, the three-qubit W state (Dür et al., 2000, Eq. (2)). For every pair S of terms, two factor vectors are parallel in one mode and span a two-dimensional space in the other two modes. Hence β(S) = 0 + 1 + 1 = 2, so the pairwise Lovitz–Petrov uniqueness threshold 2|S| − 1 = 3 fails. For the full set, dj ([3]) = 2,

j = 1, 2, 3,

and therefore β([3]) = 3 < 5. The scattering contribution is instead infinite. The three terms are coordinate tensors with labels (1, 1, 2), (1, 2, 1), (2, 1, 1). Any two labels differ in exactly two coordinates. Hence every pair of terms has disjoint supports in two modes. By Theorem 3(iii), the fully activated graph G[d] (S) has no edges for every S with |S| ≥ 2, so τ (S) = +∞. Consequently condition (U) holds for every nontrivial subset S, and Theorem 1 gives rank+ (T ) = 3 and uniqueness among nonnegative decompositions of length three. The failure of all reshaped Lovitz–Petrov conditions can also be checked explicitly. For a pair, every partition of the three modes produces a grouped dimension budget at most 2 < 3. For the full set, the three two-block partitions produce grouped budgets at most 3 < 5, while grouping all three modes gives budget 2 < 5. Thus no reshaping recovers the Lovitz–Petrov uniqueness threshold. The distinction is genuinely caused by nonnegativity. Over R, the decomposition is not unique. Indeed, (e1 + te2 )⊗3 − (e1 − te2 )⊗3 = 2t T + 2t3 e⊗3 2 , and hence, for every t > 0, T =

1 1 (e1 + te2 )⊗3 − (e1 − te2 )⊗3 − t2 e⊗3 2 . 2t 2t

Thus the same tensor admits a continuum of real rank-three decompositions, while the displayed nonnegative decomposition is unique. The gain from the positive-scattering criterion is therefore not a reformulation of unrestricted CP uniqueness. 35

For completeness, the real rank of T is also three. Suppose otherwise that T =

2 X

ui ⊗ vi ⊗ wi .

i=1

The two mode-1 slices

T1 =

0 1 , 1 0

T2 =

1 0 0 0

would lie in the two-dimensional span of v1 w1⊤ , v2 w2⊤ . Since T1 , T2 are linearly independent, that span would equal {αT1 + βT2 : α, β ∈ R}. But det(αT1 + βT2 ) = −α2 , so the rank-one matrices in this pencil form only the one-dimensional subspace spanned by T2 , a contradiction. The next example shows that the same strictness phenomenon persists for arbitrary decomposition length. Example 2 (Arbitrary nonnegative rank). Fix R ≥ 3, let n1 = R,

n2 = R − 1,

n3 = 2,

and define TR =

R−1 X

er ⊗ er ⊗ e1 + eR ⊗ e1 ⊗ e2 .

r=1

Every term is a coordinate tensor. Any two labels differ in at least two coordinates: two diagonal labels (r, r, 1) and (r′ , r′ , 1) differ in modes 1 and 2, while (r, r, 1) and (R, 1, 2) differ in modes 1 and 3 (and also in mode 2 unless r = 1). Hence every pair has disjoint supports in at least two modes. It follows from Theorem 3(iii) that τ (S) = +∞

for every S ⊆ [R],

|S| ≥ 2.

Condition (U) therefore holds for every S, and rank+ (TR ) = R with uniqueness among nonnegative decompositions of length R. For the full set S = [R], d1 (S) = R,

d2 (S) = R − 1,

d3 (S) = 2,

so β([R]) = (R − 1) + (R − 2) + 1 = 2R − 2 < 2R − 1. Thus the unreshaped Lovitz–Petrov condition fails. It also fails after every reshaping. The grouped dimension budgets for the five partitions of the three modes are grouped ranks partition {1}, {2}, {3} R, R − 1, 2 {1, 2}, {3} R, 2 {1, 3}, {2} R, R − 1 {2, 3}, {1} R, R {1, 2, 3} R 36

budget 2R − 2 R 2R − 3 2R − 2 R − 1.

The maximum is 2R − 2, still strictly below the uniqueness threshold 2R − 1. The example again separates real and nonnegative identifiability. Flattening TR along mode 1 gives R−1 X

er (er ⊗ e1 )⊤ + eR (e1 ⊗ e2 )⊤ ,

r=1

whose R rows are distinct coordinate vectors. Thus the real rank is at least R, while the displayed decomposition has length R, so its real rank is exactly R. At the same time, the first R − 1 terms can be replaced by an arbitrary rank factorization of the identity. If G = [g1 · · · gR−1 ] is invertible and hs denotes the sth column of G−⊤ , then IR−1 =

R−1 X

gs h⊤ s,

s=1

and therefore, writing ι : RR−1 → RR for the embedding onto the first R − 1 coordinates, TR =

R−1 X

ι(gs ) ⊗ hs ⊗ e1 + eR ⊗ e1 ⊗ e2

s=1

is another real decomposition of length R. These decompositions are generically inequivalent. By the classical characterization of matrices whose inverse is also nonnegative (Berman and Plemmons, 1994), such a factorization is nonnegative only in the monomial case. Thus the real alternatives do not contradict the nonnegative uniqueness established above. Figure 3 summarizes the support obstruction common to the two constructions.

8.2

Numerical Comparison

We next examine the gain from the scattering term on random sparse nonnegative decompositions. Fix d = 3 and R = 5, let all mode dimensions equal n, and draw the support of each factor coordinatewise from Bernoulli(p), conditioning on nonempty factors. On each support, assign independent integer values uniformly from {1, . . . , 999}. For each realization we compute the mode dimensions, the pairwise scattering costs, and the resulting τ (S) exactly. Conditions (M) and (U) are then checked for every nontrivial subset S ⊆ [R]. Thus the reported certification outcomes do not depend on numerical tolerances. Figure 4 compares condition (U) with Kruskal’s condition (Kruskal, 1977, Theorem 4a) and the Lovitz–Petrov condition β(S) ≥ 2|S| − 1

for every S ⊆ [R],

|S| ≥ 2.

Kruskal’s condition implies the Lovitz–Petrov condition (Lovitz and Petrov, 2023, p. 3), and the latter implies (U) because τ (S) ≥ 0. Thus the positive-scattering criterion can only expand the certified region. The difference is largest in sparse regimes. There, support disjointness creates large or infinite scattering costs even when the factor-span dimensions remain too small to meet the dimensiononly threshold. At full support, ordinary support disjointness never occurs, so the infinite-cost obstruction disappears. 37

(a)

(b)

slice x3 = 2

(1, 1, 2) (5, 1, 2)

slice x3 = 1

(1, 2, 1)

(r, r, 1)

(2, 1, 1) diagonal vs. diagonal: modes 1, 2 differ diagonal vs. (5, 1, 2): modes 1, 3 differ

any two labels differ in two coordinates

∞ 1

∞

each edge keeps an unexempted mode with disjoint supports ⇒ τ (S) = +∞

Figure 3: The combinatorics behind the infinite scattering of both examples. (a) The three terms of the W tensor (Example 1) as cells of the 2 × 2 × 2 array: any two of the labels (1, 1, 2), (1, 2, 1), (2, 1, 1) differ in two coordinates, so the corresponding factor pairs have disjoint supports in two modes. (b) The terms of TR (Example 2, drawn for R = 5) in the two slices x3 = 1, 2: the diagonal labels (r, r, 1) and the isolated label (R, 1, 2) again differ pairwise in at least two coordinates. (c) Two equivalent readings of the obstruction. In the tree formula (4), whichever spanning tree and exemption map ε one chooses, each tree edge keeps at least one unexempted mode in which the two supports are disjoint, so κj (Fj (T, ε)) = +∞ there by Lemma 9. Equivalently, no pair is an edge of the activation graph G[d] (S), so G[d] (S) is disconnected and Theorem 3(iii) gives τ (S) = +∞ for every |S| ≥ 2, whereas every reshaped budget falls short of the thresholds.

0.2

0.6

1.0

support density p

0.2

0.6

1.0

support density p

1.0 0.8 0.6 0.4 0.2 0.0

0.2

0.6

1.0

support density p

(d) difference (c) (b) 12 10 8 7 6 5 4 3

0.6

probability difference

(b) Lovitz Petrov 12 10 8 7 6 5 4 3

certification probability

mode dimension n

(a) Kruskal 12 10 8 7 6 5 4 3

0.4 0.2 0.0

0.2

0.6

1.0

support density p

Figure 4: Certification probabilities for random nonnegative decompositions with d = 3 and R = 5. Factor supports are drawn coordinatewise from Bernoulli(p), conditioned on being nonempty, and nonzero entries are independent uniform integers in {1, . . . , 999}. Each cell aggregates 500 P realizations. (a) Kruskal’s condition j (kj − 1) ≥ 2R − 1. (b) The Lovitz–Petrov condition β(S) ≥ 2|S| − 1 for every S. (c) The positive-scattering condition (U). (d) The increase in certification probability from (b) to (c). The largest observed increase is 0.60, at (n, p) = (12, 0.04). At full support, the infinite support-separation obstruction is absent.

8.3

Searching for Alternatives

The previous experiment asks when the criterion certifies uniqueness. We now ask the converse question: when (U) fails, how often can we find an explicit nonnegative alternative? We restrict attention to the slice n = 6 and search every realization that violates (U). The search proceeds in two stages. First, we test explicit pair constructions. If two prescribed terms can be combined into a shorter nonnegative rank-one representation, minimality fails. If they are nonparallel in exactly two modes and have nested supports in one of those modes, the identity x1 ⊗ y1 + x2 ⊗ y2 = x1 ⊗ (y1 + ty2 ) + (x2 − tx1 ) ⊗ y2 produces an inequivalent nonnegative decomposition whenever 0<t<

x2 (i) . i∈supp(x1 ) x1 (i) min

All such constructions are checked exactly over Q. When no pair construction applies, we use multi-start nonnegative alternating least squares (Kim et al., 2007, p. 1148) only as a heuristic to locate candidate alternatives. A candidate is counted only after an exact rational decomposition has been constructed and verified. Among the 5621 realizations violating (U), an exact pair construction was found in 5497, and an additional 10 realizations admitted an exact construction on a larger subset. The remaining 114 cases are inconclusive. Thus an exact nonnegative alternative was found in 5497 + 10 ≈ 0.98 5621 of the violating instances. This provides empirical evidence that the criterion may be close to necessary for this sparse ensemble, although the experiment does not establish necessity.

(a) all instances

fraction of instances

1.0

(b) instances with no alternative found

0.8

0.6

1.00

0.4

0.97

0.2

0.0

0.2

0.4

0.6

0.8

support density p

Kruskal holds Lovitz Petrov holds, Kruskal fails

1.0

0.94

0.2

(U) holds (τ < ∞) (U) holds (τ = ∞)

0.4

0.1

0.3

0.6

support density p

0.5

0.8

1.0

(U) fails (alternative found) (U) fails (no alternative found)

Figure 5: Search for nonnegative alternatives on the n = 6 slice of the ensemble in Figure 4, using 1600 realizations for each value of p. Every realization violating (U) is searched. Exact pair constructions and larger-subset constructions are verified over Q; candidate decompositions found by alternating least squares are not counted unless an exact decomposition is subsequently verified. (a) The search outcomes. (b) The same data after removing the exact-alternative layer. The unresolved cases are therefore genuinely inconclusive rather than evidence of uniqueness.

Matrix Specialization

The order-two case provides a useful boundary case for the general theory. Identifying T with a matrix X, write X=T =

R X

⊤ ar b⊤ r = AB ,

1 ×R A = [a1 · · · aR ] ∈ Rn≥0 ,

2 ×R B = [b1 · · · bR ] ∈ Rn≥0 ,

(9)

r=1

where every column of A and B is nonzero. We call a set of columns of a matrix a circuit if it is linearly dependent and every proper subset of it is linearly independent (Whitney, 1935, p. 510). For a nonempty S ⊆ [R], let AS and BS denote the corresponding column submatrices. Then d1 (S) = rank AS ,

d2 (S) = rank BS ,

and therefore β(S) = rank AS + rank BS − 2.

(10)

The matrix case is especially revealing because neither Kruskal’s nor Lovitz–Petrov’s dimension budget can reach the thresholds in Theorem 1. Hence the matrix content of the present criterion comes entirely from the positivity-induced scattering term. Remark 7 (Dimension budgets in two modes). The usual Kruskal and Lovitz–Petrov theorems are formulated for tensors with at least three modes. Here we only examine the corresponding dimension-budget inequalities after formally setting d = 2. For every S with |S| ≥ 2, β(S) ≤ 2|S| − 2 < 2|S| − 1, 40

so the Lovitz–Petrov uniqueness threshold can never hold in two modes. Likewise, if k1 and k2 are the Kruskal ranks of the two factor matrices, then (k1 − 1) + (k2 − 1) ≤ 2R − 2 < 2R − 1, so the corresponding Kruskal threshold is also unattainable. Thus, in the matrix case, the budget alone cannot certify uniqueness. The difference between the minimality and uniqueness criteria is entirely accounted for by the positive-scattering term. Condition (M) requires

τ (S) ≥ |S| − rank AS + |S| − rank BS , while condition (U) requires one additional unit. The next results show that these inequalities have particularly simple interpretations. Minimality reduces exactly to ordinary matrix rank, whereas uniqueness reduces exactly to two-sided separability.

9.1

Overlap Graphs and Matrix Scattering

For a pair {r, t} ⊆ S, the two mode costs κ1 ({r, t}) and κ2 ({r, t}) are computed relative to the set S, using the spaces and support hulls defined in Section 5. By Proposition 4, each belongs to {0, 1, +∞}. The cases 0 and +∞ can be expressed directly through two natural graphs. Definition 5 (Overlap graphs). Let S ⊆ [R] with |S| ≥ 2. The facet-overlap graph FA (S) has vertex set S and an edge {r, t} whenever AU1 (S) (ar ) ∩ AU1 (S) (at ) ̸= ∅. The support-overlap graph OA (S) has vertex set S and an edge {r, t} whenever supp(ar ) ∩ supp(at ) ̸= ∅. Define FB (S) and OB (S) analogously for the columns of B. All graph unions below are taken on the common vertex set S. By Proposition 4, κ1 ({r, t}) = 0

⇐⇒

{r, t} ∈ E(FA (S)),

κ1 ({r, t}) < +∞

⇐⇒

{r, t} ∈ E(OA (S)).

while Lemma 9 gives The corresponding statements hold for B. In particular, FA (S) ⊆ OA (S),

FB (S) ⊆ OB (S).

Proposition 6 (Matrix activation formula). For every S ⊆ [R] with |S| ≥ 2, the activation graphs GM (S) of Section 5.4 are G∅ (S) = FA (S) ∪ FB (S),

(11)

G{1} (S) = OA (S) ∪ FB (S),

(12)

G{2} (S) = FA (S) ∪ OB (S),

(13)

G{1,2} (S) = OA (S) ∪ OB (S).

(14)

Consequently,

τ (S) =

  0,      

FA (S) ∪ FB (S) is connected,

  2,     +∞,

otherwise, if OA (S) ∪ OB (S) is connected,

otherwise, if OA (S) ∪ FB (S) or FA (S) ∪ OB (S) is connected,

(15)

otherwise.

In particular, τ (S) ∈ {0, 1, 2, +∞}. For a pair S = {r, t},

τ ({r, t}) = min κ1 ({r, t}), κ2 ({r, t}) .

(16)

Proof. For M ⊆ {1, 2}, recall from Theorem 3(i) that a pair e = {r, t} is an edge of GM (S) precisely when n o # j : κj (e) = +∞ or κj (e) = 1 and j ∈ / M ≤ 1. If M = ∅, the counted modes are exactly those with κj (e) ≥ 1. Hence e is an edge if and only if at least one of the two costs is zero, which gives (11). If M = {1}, mode 1 contributes to the count only when κ1 (e) = +∞, while mode 2 contributes whenever κ2 (e) ≥ 1. Thus e is an edge precisely when κ1 (e) < +∞ or κ2 (e) = 0, giving (12). The case M = {2} is symmetric, and for M = {1, 2} only the infinite costs remain, giving (14). The four graphs are monotone in M because FA ⊆ OA ,

FB ⊆ OB .

The activation formula now follows directly from Theorem 3(i). For S = {r, t}, the tree formula (5) leaves exactly one mode nonexempted, giving (16).

9.2

Row-Separability

We next identify the matrix condition associated with persistent failure of facet-overlap connectivity. 1 ×R Definition 6 (Row-separability). Let A ∈ Rn≥0 and let S ⊆ [R] be nonempty. A row index i is pure on r relative to S if

Air > 0,

Ait = 0

for every t ∈ S \ {r}.

The matrix A is row-separable on S if every r ∈ S has a row that is pure on r relative to S, and row-separable if it is row-separable on [R]. The factorization (9) is two-sided separable if both A and B are row-separable. In the conventional notation X = W H with W = A and H = B ⊤ , row-separability of B means that for every r some column of H is a positive multiple of the coordinate vector er . This is the separability condition of Donoho and Stodden (Donoho and Stodden, 2004); row-separability of A is the analogous condition for X ⊤ = BA⊤ . Proposition 7 (Facet characterization of separability). Let A have full column rank. The following are equivalent: (i) A is row-separable; 42

(ii) FA (S) is disconnected for every S ⊆ [R] with |S| ≥ 2; (iii) FA (S) is edgeless for every S ⊆ [R] with |S| ≥ 2. The same equivalences hold with A and FA replaced by B and FB . Proof. Because A has full column rank, every AS has full column rank. Fix S ⊆ [R] with |S| ≥ 2 and put U = U1 (S). For each active row i ∈ N1 (S) define the normalized row (Air )r∈S ∈ RS , qi = P A ir r∈S and let P = conv{qi : i ∈ N1 (S)}. By Proposition 2, a row i defines a facet of C(U ) precisely when qi is a vertex of P . Moreover, two columns ar , at have intersecting facet signatures if and only if some vertex of P has both rth and tth coordinates positive. Thus {r, t} ∈ E(FA (S))

⇐⇒

P has a vertex with positive rth and tth coordinates.

(17)

We use this characterization in both directions. Row-separable implies edgeless. Suppose A is row-separable. For every r ∈ S, choose a row that is pure on r relative to [R]. Since A has full column rank, such a row gives the normalized vector qi = er . Hence the convex hull P contains all coordinate vectors er , while every qi is a probability vector on S and therefore lies in their simplex. Thus P = conv{er : r ∈ S}, whose vertices have exactly one positive coordinate. By (17), FA (S) is edgeless. Edgeless implies disconnected. This is immediate because |S| ≥ 2. Disconnected for every S implies row-separable. Suppose instead that A is not row-separable. Choose an inclusion-minimal nonempty subset S ⊆ [R] on which A is not row-separable. Then |S| ≥ 2. Choose r ∈ S for which no row is pure on r relative to S. For every t ∈ S \ {r}, minimality of S implies that A is row-separable on S \ {t}. Hence there exists a row it such that Ait r > 0, Ait u = 0 (u ∈ S \ {r, t}). Because the row is not pure on r relative to S, necessarily Ait t > 0. Therefore qit ∈ relint conv{er , et }. We next claim that er ∈ / P . Otherwise er would be a convex combination of the points qi . Since all coordinates are nonnegative and er vanishes outside coordinate r, every qi appearing with positive weight would have to equal er . The corresponding row would be pure on r relative to S, a contradiction. Write qit as a convex combination of vertices of P . Since the coordinates outside {r, t} vanish, every vertex appearing with positive weight lies on conv{er , et }. Because qit has both its rth and tth coordinates positive, it cannot be represented using only the vertex et . Moreover, er ∈ / P , so 43

no vertex in the representation can equal er . Hence at least one vertex has both the rth and tth coordinates positive. By (17), {r, t} ∈ E(FA (S)). This holds for every t ∈ S \ {r}, so r is adjacent to every other vertex and FA (S) is connected, contradicting the assumption. Hence A is row-separable.

9.3

Complete Matrix Characterization

We can now identify both main criteria completely. Theorem 5 (Matrices: complete characterization). For the nonnegative matrix decomposition (9): (i) condition (M) holds if and only if rank A = rank B = R, equivalently, rank X = R; (ii) condition (U) holds if and only if the factorization is two-sided separable. Proof. Part (i). If rank A = rank B = R, then every AS and BS has full column rank. Hence β(S) = 2|S| − 2 for every S with |S| ≥ 2, and condition (M) follows from τ (S) ≥ 0. Conversely, suppose rank A < R. Choose a circuit S ⊆ [R] among the columns of A. Then rank AS = |S| − 1,

|S| ≥ 2.

Let U = U1 (S). By circuit minimality, there is a linear dependence X

cr ar = 0

r∈S

with every cr ̸= 0. Applying the injective map LU gives X

cr LU ar = 0.

r∈S

If FA (S) were disconnected, choose a nonempty proper connected component C ⊊ S. For every r ∈ C and t ∈ S \ C, the supports of LU ar and LU at are disjoint. Evaluating the linear relation coordinatewise therefore shows X cr LU ar = 0. r∈C

Injectivity of LU gives X

cr ar = 0,

r∈C

contradicting the fact that S is a circuit. Thus FA (S) is connected. Therefore FA (S) ∪ FB (S) 44

is connected, so Proposition 6 and Theorem 3(ii) give τ (S) = 0. Since rank AS = |S| − 1,

rank BS ≤ |S|,

we have β(S) ≤ 2|S| − 3, and hence β(S) + τ (S) ≤ 2|S| − 3 < 2|S| − 2. Thus condition (M) fails. The same argument with A and B interchanged shows that (M) implies rank A = rank B = R. Finally, rank X ≤ min{rank A, rank B} ≤ R. If rank A = rank B = R, choose left inverses LA A = IR and LB B = IR . Then ⊤ ⊤ LA XL⊤ B = LA AB LB = IR ,

so rank X ≥ R, and therefore rank X = R. Conversely, rank X = R forces both rank A and rank B to equal R. Part (ii). By Part (i), condition (U) can be rewritten as τ (S) ≥ 1

for every S ⊆ [R], |S| ≥ 2,

because then β(S) = 2|S| − 2. By Proposition 6, τ (S) = 0

⇐⇒

FA (S) ∪ FB (S) is connected.

Thus (U) holds if and only if FA (S) ∪ FB (S) is disconnected for every S with |S| ≥ 2. Since each FA (S) and FB (S) is a subgraph of this union, both must themselves be disconnected. Proposition 7 therefore implies that A and B are row-separable. Conversely, suppose A and B are row-separable. Then each has full column rank, since the pure rows for the R columns are necessarily distinct and produce a positive diagonal R × R submatrix. By Proposition 7, FA (S) and FB (S) are edgeless for every |S| ≥ 2. Hence their union is disconnected, so τ (S) ≥ 1 by Proposition 6. Since β(S) = 2|S| − 2, we obtain β(S) + τ (S) ≥ 2|S| − 1, which is condition (U). 45

9.4

Separability and Explicit Recovery

The matrix uniqueness criterion therefore has a completely observable form. Corollary 3 (Separability, diagonal pattern, and recovery). For the nonnegative matrix decomposition (9), the following are equivalent: (i) condition (U) holds; (ii) the factorization is two-sided separable; (iii) there exist pairwise distinct row indices i1 , . . . , iR and pairwise distinct column indices j1 , . . . , jR such that Xir jr > 0, Xir jt = 0, r ̸= t. (18) Under these conditions, rank+ (X) = R, and every nonnegative length-R decomposition is equivalent to (9). Moreover, if ir and jr are pure indices for r in A and B, respectively, then ar b⊤ r =

(Xejr )(e⊤ ir X) , Xir jr

and hence X=

r ∈ [R],

R X (Xejr )(e⊤ i X) r

Xir jr

r=1

(19)

Proof. The equivalence of (i) and (ii) is Theorem 5. (ii) implies (iii). For every r, choose a row ir of A and a row jr of B that are pure on r. These indices are pairwise distinct within each factor. Writing αr = Air r > 0, we obtain

R X

Xir jt =

γr = Bjr r > 0,

Air u Bjt u = αr γr δrt ,

u=1

which gives (18). (iii) implies (ii). Assume (18). For every r, Xir jr =

R X

Air u Bjr u > 0,

u=1

so there exists at least one s(r) such that Air ,s(r) > 0,

Bjr ,s(r) > 0.

The map r 7→ s(r) is injective. Indeed, if s(r) = s(t) = s for r ̸= t, then the term indexed by s contributes Air s Bjt s > 0

to Xir jt , contradicting the zero pattern. Hence, after relabeling, we may assume s(r) = r. For t ̸= r, the diagonal pattern gives 0 = Xir jt ≥ Air t Bjt t . Since Bjt t > 0, we obtain Air t = 0. Thus row ir of A is pure on r. Symmetrically, 0 = Xit jr ≥ Ait t Bjr t and Ait t > 0 imply that row jr of B is pure on r. Hence the factorization is two-sided separable. The rank and uniqueness statements follow from Theorem 1. Recovery. Since row jr of B is pure on r, Xejr =

R X

au Bjr u = γr ar .

u=1

Similarly, since row ir of A is pure on r, e⊤ ir X =

R X

⊤ Air u b⊤ u = αr br .

u=1

Finally, Xir jr = αr γr . Substitution gives (Xejr )(e⊤ ir X) = ar b⊤ r , Xir jr which proves (19). Remark 8 (Fast verification in the matrix case). The matrix specialization eliminates the subset enumeration appearing in the general criterion. Condition (M) is equivalent to rank X = R, and condition (U) is equivalent to two-sided separability, which can be checked directly from the factor matrices. Thus no enumeration of subsets and no linear-programming vertex tests are needed for the matrix certificates.

Conclusion

This paper develops a deterministic identifiability theory for nonnegative tensor decompositions based on two complementary sources of information. The Lovitz–Petrov dimension budget captures the linear-algebraic constraints imposed by the factor spans, while the positive scattering term captures additional rigidity created by nonnegativity and support geometry. The positive splitting inequality combines these two effects and yields separate thresholds for minimality and uniqueness. Although the scattering term is defined through an optimization over intermediate factor spaces, its mode costs reduce exactly to {0, 1, +∞}, leading to a finite activation problem on a graph. The resulting criterion can strictly improve upon dimension-based uniqueness conditions, including in sparse examples where reshaping does not recover the Lovitz–Petrov condition. The theory also clarifies how identifiability behaves under natural structural operations. Appending nonnegative modes can only strengthen the combined dimension–scattering criterion, while reshaping provides additional flexibility by changing the grouping of the modes. In the matrix boundary case, the two criteria admit exact closed-form interpretations: minimality reduces to ordinary full-rank factorization, while uniqueness reduces to two-sided separability and admits an explicit term-recovery formula. Several directions remain open. The full certificate still requires checking all nontrivial subsets of components, motivating the search for more economical sufficient conditions or algorithms that exploit additional structure. The interaction between scattering and reshaping is also not fully understood: while grouping can increase the dimension budget, we do not yet have a general comparison between grouped and ungrouped scattering terms. Finally, the matrix specialization identifies two-sided separability as the exact boundary case of the present criterion, leaving open the question of which broader nonnegative matrix identifiability phenomena admit genuine higherorder analogues. More generally, the positive-scattering perspective suggests a broader program of incorporating structural constraints beyond linear independence into deterministic identifiability theory.

References E. S. Allman, C. Matias, and J. A. Rhodes, “Identifiability of parameters in latent structure models with many observed variables,” Ann. Statist., vol. 37, no. 6A, pp. 3099–3132, 2009. A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky, “Tensor decompositions for learning latent variable models,” J. Mach. Learn. Res., vol. 15, no. 80, pp. 2773–2832, 2014. A. Anandkumar, D. Hsu, M. Janzamin, and S. Kakade, “When are overcomplete topic models identifiable? Uniqueness of tensor Tucker decompositions with structured sparsity,” J. Mach. Learn. Res., vol. 16, no. 82, pp. 2643–2694, 2015. T. Barker and T. Virtanen, “Blind separation of audio mixtures through nonnegative tensor factorization of modulation spectrograms,” IEEE/ACM Trans. Audio Speech Lang. Process., vol. 24, no. 12, pp. 2377–2389, 2016. A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics 9, SIAM, Philadelphia, 1994. J. E. Cohen and U. G. Rothblum, “Nonnegative ranks, decompositions, and factorizations of nonnegative matrices,” Linear Algebra and its Applications, vol. 190, pp. 149–168, 1993. 48

D. L. Donoho and V. C. Stodden, “When does non-negative matrix factorization give a correct decomposition into parts?” in Advances in Neural Information Processing Systems 16, 2004. W. Dür, G. Vidal, and J. I. Cirac, “Three qubits can be entangled in two inequivalent ways,” Phys. Rev. A, vol. 62, no. 6, Art. no. 062314, 2000. C. G. Khatri and C. R. Rao, “Solutions to some functional equations and their applications to characterization of probability distributions,” Sankhyā, Series A, vol. 30, no. 2, pp. 167–180, 1968. H. Kim, H. Park, and L. Eldén, “Non-negative tensor factorization based on alternating largescale non-negativity-constrained least squares,” in Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering (BIBE 2007), vol. II, pp. 1147–1151, 2007. J. B. Kruskal, “Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics,” Linear Algebra Appl., vol. 18, no. 2, pp. 95–138, 1977. L.-H. Lim and P. Comon, “Nonnegative approximations of nonnegative tensors,” J. Chemometrics, vol. 23, nos. 7–8, pp. 432–441, 2009. B. Lovitz and F. Petrov, “A generalization of Kruskal’s theorem on tensor decomposition,” Forum Math. Sigma, vol. 11, Art. no. e27, pp. 1–40, 2023. Y. Qi, P. Comon, and L.-H. Lim, “Uniqueness of nonnegative tensor approximations,” IEEE Trans. Inf. Theory, vol. 62, no. 4, pp. 2170–2183, 2016. R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, vol. 28. Princeton, NJ, USA: Princeton University Press, 1970. A. Schrijver, Theory of Linear and Integer Programming. Chichester, UK: Wiley, 1986. N. D. Sidiropoulos and R. Bro, “On the uniqueness of multilinear decomposition of N -way arrays,” Journal of Chemometrics, vol. 14, no. 3, pp. 229–239, 2000. M. Sørensen and L. De Lathauwer, “New uniqueness conditions for the canonical polyadic decomposition of third-order tensors,” SIAM J. Matrix Anal. Appl., vol. 36, no. 4, pp. 1381–1403, 2015. M. A. Veganzones, J. E. Cohen, R. Cabral Farias, J. Chanussot, and P. Comon, “Nonnegative tensor CP decomposition of hyperspectral data,” IEEE Trans. Geosci. Remote Sens., vol. 54, no. 5, pp. 2577–2588, 2016. H. Whitney, “On the abstract properties of linear dependence,” American Journal of Mathematics, vol. 57, no. 3, pp. 509–533, 1935.

Record · ID 673526 · SHA-256 86cc778726c6dc33
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.