PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Uniqueness of the Canonical Polyadic Decomposition of third-order tensors --- Part II: Uniqueness of the overall decomposition

Ignat Domanov, Lieven De Lathauwer

arXiv:1301.4603v1math.SP

TL;DR

The central question is when a tensor's CPD is unique apart from rank-1 term permutations and within-term scalings. The paper gives condition-based criteria that imply rT=R and CPD uniqueness.

  • Problem

    The central question is when a tensor's CPD is unique apart from rank-1 term permutations and within-term scalings.

    Source: §1.1 · p. 2

  • Method

    Three condition variants pair (1.12) with WmC, UmC, or HmC requirements; the WmC variant also requires A⊙B to have full column rank.

    Source: §1.3 · p. 7

  • Results

    Each of the three stated condition sets implies rT=R and uniqueness of T's CPD.

    Source: §1.3 · p. 7

  • Takeaways & Limitations

    For equal or structured factor matrices, the results adapt; in generic settings, fewer independent entries may lower the rank R up to which uniqueness is guaranteed.

    Source: §7 · p. 27

    Whether an SFS-tensor can have unique SFS-CPD but non-unique CPD remains an open question.

    Source: §4 · p. 18

Abstract

from arXiv · show

Canonical Polyadic (also known as Candecomp/Parafac) Decomposition (CPD) of a higher-order tensor is decomposition in a minimal number of rank-1 tensors. In Part I, we gave an overview of existing results concerning uniqueness and presented new, relaxed, conditions that guarantee uniqueness of one factor matrix. In Part II we use these results for establishing overall CPD uniqueness in cases where none of the factor matrices has full column rank. We obtain uniqueness conditions involving Khatri-Rao products of compound matrices and Kruskal-type conditions.

1. Introduction.

The introduction defines essential CPD uniqueness and distinguishes it from uniqueness of an individual factor, while surveying deterministic and generic criteria for overall uniqueness. It then applies conditions (1.8) to establish CPD uniqueness when rC < R, deriving criteria for decompositions that share factor matrices and combining them for overall uniqueness.

1.1. Problem statement.

  • A CPD is essentially unique when its only ambiguities are common term permutation and compensating factor scalings; individual factor uniqueness can hold without overall uniqueness.The paper distinguishes deterministic results for a particular decomposition from generic uniqueness, which holds with probability one under continuous sampling.Source: §1.1 · pp. 2–3

1.2. Literature overview.

  • The literature overview situates the paper among prior deterministic uniqueness conditions and new results on uniqueness of one factor matrix [7].It directs readers to overview papers for background, applications, and algorithms, while this work focuses on uniqueness results.Source: §1.2 · p. 3, §1.2.1 · p. 3

1.2.1. Deterministic conditions.

  • Prior deterministic work gives Kruskal’s CPD uniqueness theorems [14], compound-matrix conditions, and criteria for uniqueness of an individual factor matrix [7].The overview recalls several Kruskal theorems and results on factor-matrix uniqueness; one cited criterion uses conditions (W_m), …, (W_1) and a full-column-rank Khatri–Rao product.Source: §1.2.1 · pp. 3–5

1.2.2. Generic conditions.

  • The dimension inequality is min(I, R) + min(J, R) + min(K, R) ≥ 2R + 2; separately, an I × J × K tensor’s CPD is generically unique when R ≤ (I − 1)(J − 1) ≤ K [2, Proposition 5.2], [18, Theorem 2.7].Source: §1.2.2 · p. 6
  • Generic uniqueness results for specific dimension-and-rank cases had been obtained in; this paper uses (1.8) to establish CPD uniqueness when rC < R.Source: §1.3 · p. 6, §1.2.2 · p. 6

1.3. Results and organization.

  • Section 2 studies two PDs sharing one or two factor matrices and gives conditions for their equality, including permutation-and-scaling recovery in Proposition 1.20.In Proposition 1.20, if the third factors differ by a permutation and nonsingular diagonal scaling, then the first two factors share that permutation and diagonal scalings whose product with the third scaling is the identity.Source: §1.3 · pp. 6–7
  • Proposition 1.21 gives alternative conditions for the shared-factor decomposition setting, including kC ≥ 2 with a rank condition involving rC, or kA ≥ 2 with one involving rA.The stated alternatives require max(min(kA, kB − 1), min(kA − 1, kB)) + rC ≥ R + 1 or max(min(kB, kC − 1), min(kB − 1, kC)) + rA ≥ R + 1, respectively.Source: §1.3 · p. 7
  • Section 3 combines (1.8) with Proposition 1.21 to obtain further overall-CPD uniqueness results, using mA := R − rA + 2, mB := R − rB + 2, and mC := R − rC + 2.Source: §1.3 · pp. 7–8
  • Under (1.12), Proposition 1.22 combines (WmC) for A, B, and C with full column rank of A ⊙ B to give rT = R and a unique CPD.Here mC := R − rC + 2.Source: §1.3 · p. 7
  • Under (1.12), Corollaries 1.23–1.25 give rT = R and unique CPD using (UmC), (HmC), or full-column-rank CmC(A) ⊙ CmC(B).The respective conditions are (UmC) for A and B, (HmC) for A and B, and full column rank of the compound-matrix Khatri-Rao product.Source: §1.3 · p. 7
  • These results remove Proposition 1.15’s full-column-rank requirement on C by tightening conditions on A and B.The paper states that Proposition 1.22 is more general than Corollary 1.23, which is more general than Corollaries 1.24 and 1.25; the relaxed rank condition is rC = R − mC + 2 with mC ≥ 2.Source: §1.3 · p. 7

Assume that at least two of the following conditions hold

The paper derives overall CPD uniqueness from conditions on one or more factor matrices, including relaxed Kruskal-type conditions. It also identifies limits on when these conditions can be shown to improve on earlier criteria.

Assume that at least two of the following conditions hold

  • When all three corresponding (U_m) conditions hold, the tensor has rank R and its CPD is unique.The conditions apply to each pair of factor matrices at its corresponding m parameter.Source: Assume that at least two of the… · p. 8
  • When at least two of the specified compound-matrix Khatri–Rao products have full column rank, the tensor has rank R and a unique CPD.Corollary 1.28 requires at least two of the three matrices to have full column rank.Source: Assume that at least two of the… · pp. 8–9
  • Corollary 1.29 gives uniqueness under its stated rank and k-rank inequalities, and is more relaxed than Kruskal’s Theorem 1.8.The paper states that Kruskal’s Theorem 1.9 is equivalent to Corollary 1.29.Source: Assume that at least two of the… · p. 8
  • The authors omit a result combining (W_m)-type implications with Proposition 1.21 because they have no examples showing it to be more relaxed than Proposition 1.26.Source: Assume that at least two of the… · p. 9
  • Proposition 1.31 gives generic CPD uniqueness when matrices A0, B0, and C0 satisfy at least one of three compound-matrix full-column-rank conditions.The paper also says that examples illustrate generic-case uniqueness results.Source: Assume that at least two of the… · p. 9

2. Equality of PDs with common factor matrices.

This section establishes when two decompositions with a common factor matrix, or two common factor matrices, must agree. The results use k-rank conditions and subspace arguments, and include an example showing a stated inequality is sharp.

2.1. One factor matrix in common.

  • With one factor matrix C in common, Proposition 1.20 establishes correspondence of the other factors under condition (1.12), up to reciprocal scaling.The proof uses a vector that annihilates selected columns of C while remaining nonzero on the others, then compares Khatri–Rao products.Source: §2.1 · pp. 10–11
  • For the four-term example, fixing either B or C forces the other two factor matrices to match up to reciprocal diagonal scaling.Source: §2.1 · p. 12
  • The inequality in condition (1.12) is sharp: the example admits infinitely many decompositions with A fixed but non-proportional corresponding columns in B and C.The columns of B and C are proportional to their counterparts only for the specified α and β values.Source: §2.1 · p. 12

2.2. Two factor matrices in common.

  • With two factor matrices A and C in common, condition (2.8) forces the permutation relating the decompositions to be the identity.The condition is k_C ≥ 2 and min(k_A − 1, k_B) + r_C ≥ R + 1.Source: §2.2 · pp. 12–13
  • For the two-common-factor proof, the argument shows that Π preserves the subspaces E and span{E_ik, e_R_ik}, which constrains the column permutation.Source: §2.2 · p. 13

3. Overall CPD uniqueness.

Overall CPD uniqueness is obtained by combining results on uniqueness of one or two factor matrices. The examples demonstrate that these criteria apply in cases where familiar Kruskal-type conditions do not.

3. Overall CPD uniqueness.

  • Propositions 1.22–1.25 derive overall CPD uniqueness from uniqueness of one factor matrix, while Proposition 1.26 and Corollaries 1.28–1.30 use uniqueness of two factor matrices.Source: §3 · p. 14
  • For the 5 × 5 × 5 tensor with rank-6 decomposition, Corollary 1.29 establishes uniqueness although Kruskal’s condition fails.The factor matrices have rank 5 and k-rank 4.Source: §3 · pp. 14–15
  • For the 4 × 4 × 4 rank-5 example, compound-matrix products and H_AB(δ), H_BC(δ), and H_CA(δ) establish uniqueness, although Corollary 1.29 does not apply.The three H quantities equal min(δ, 3); the example also does not meet condition (1.12).Source: §3 · p. 15
  • For the 5 × 5 × 8 example, condition (1.12) yields uniqueness through Corollary 1.24, whereas Corollary 1.27 does not apply at δ = 5.At that value, H_BC(δ) and H_CA(δ) equal 4, below min(δ, 8 − 5 + 2).Source: §3 · pp. 15–16
  • In another example, solving the stated equations forces c = 0 and d = 0, proving uniqueness through Corollary 1.23.The authors note that uniqueness of A and B does not follow from Proposition 1.26 because the required compound matrices are not defined.Source: §3 · p. 16
  • For randomly generated 7 × 10 matrices, experiments indicate that A ⊙ B has full column rank while condition (U5) fails; with the stated C conditions, Proposition 1.22 gives uniqueness.The same situation is reported for other dimensions in Table 3.1.Source: §3 · p. 16

4. Application to tensors with symmetric frontal slices and Indscal.

For tensors with symmetric frontal slices, the paper defines symmetry-constrained rank and decompositions, then adapts CPD uniqueness results to this setting. It also identifies an unresolved question about how SFS-CPD uniqueness relates to ordinary CPD uniqueness.

4. Application to tensors with symmetric frontal slices and Indscal.

  • SFS-rank is the minimum number of SFS-rank-1 terms in a decomposition, and an SFS-CPD is a minimal sum of such terms.A CPD is an SFS-CPD exactly when its first two factor matrices agree and its term count equals the SFS-rank.Source: §4 · p. 17
  • If an SFS-tensor has a unique CPD, its SFS-rank equals its CPD rank and its SFS-CPD is unique.The proof uses the symmetry to compare the CPD with the decomposition obtained by swapping the first two factor matrices.Source: §4 · pp. 17–18
  • Whether an SFS-tensor can have a unique SFS-CPD but a non-unique ordinary CPD remains open, according to the authors.Source: §4 · p. 18
  • Proposition 4.9 gives unique SFS-CPD and SFS-rank R when k_A + k_C ≥ R + 2 and C_mC(A) ⊙ C_mC(A) has full column rank.Source: §4 · p. 18
  • Proposition 4.11 gives unique SFS-CPD and SFS-rank R under its stated k-rank inequality and full-column-rank compound-matrix product.The inequality is k_A + max(min(k_C − 1, k_A), min(k_C, k_A − 1)) ≥ R + 1.Source: §4 · p. 18
  • Proposition 4.12 concludes that the SFS-rank is R and the SFS-CPD is unique when its stated matrices have full column rank.Source: §4 · p. 18

5. Uniqueness beyond (Wm).

The section gives an example where the stated Kruskal-type condition fails, yet the CPD is still shown to be unique. The proof combines subresults, including full-column-rank conditions on second compound-matrix Khatri–Rao products.

5. Uniqueness beyond (Wm).

  • Here, ω(d) counts a vector's nonzero components, and a ∥ b means the vectors are collinear.Source: §5 · p. 18
  • For a diagonal matrix, C2(Diag(d)) is zero exactly when d has at most one nonzero component.Source: §5 · p. 18
  • The example has CPD rank 5 and a unique decomposition despite none of its cyclic factor triplets satisfying (W_m).The cited propositions and corollaries do not establish its rank or factor-matrix uniqueness.Source: §5 · pp. 18–19
  • Each of C2(A) ⊙ C2(B), C2(B) ⊙ C2(C), and C2(C) ⊙ C2(A) has full column rank.These rank properties are among the subresults used in the example's proof.Source: §5 · p. 19

Elementary algebra yields

The proof establishes that the example has rank 5 and a unique CPD. It derives constraints on alternative decompositions and uses them to obtain the conditions required for the uniqueness argument.

Elementary algebra yields

  • Any three solutions of ω(C̄^T z) = 1 are linearly dependent.The argument uses the full column rank of C̄^T and the result that at least two of the three vectors are collinear.Source: Elementary algebra yields · p. 19
  • Every competing decomposition has rank at least 4, and rank 4 leads to a contradiction, so its rank is 5.The rank bound follows from the factor-matrix rank bounds; assuming rank 4 makes the columns of an inverse matrix contradict the dependence result in (ii).Source: Elementary algebra yields · pp. 19–20
  • The alternative factor matrices must each have k-rank at least 2.Source: Elementary algebra yields · p. 20
  • When condition (5.9) holds, the rank-4 residual has a unique CPD, yielding uniqueness of the original decomposition.The argument first identifies a rank-1 term shared by the decompositions, then applies Proposition 1.15 to the residual.Source: Elementary algebra yields · p. 20
  • The proof sharpens those bounds to k_Ā = k_B̄ = k_C̄ = 2.It rules out k_C̄ ≥ 3 using the derived condition (5.9), then applies the same reasoning to the other factors.Source: Elementary algebra yields · pp. 20–21
  • The CPD of Tα is unique after the proof derives the conditions of step (v), which imply uniqueness.Step (vii) obtains (5.9) from the preceding relations and applies step (v).Source: Elementary algebra yields · p. 21

6. Generic uniqueness.

The section derives generic uniqueness criteria for unconstrained and partially symmetric CPDs from compound-matrix rank conditions. Its examples show these criteria covering cases beyond Kruskal-type bounds and extending to structured factor matrices.

6.1. Generic uniqueness of unconstrained CPD.

  • For fixed C with k_C ≥ 1, a witness pair satisfying the stated compound-matrix rank condition yields generic third-factor and overall CPD uniqueness under the proposition’s conditions.The exceptional set of (A, B) pairs with rank-deficient T or a nonunique third factor has measure zero.Source: §6.1 · pp. 22–23
  • An I × J × K tensor of rank R is generically CPD-unique when one witness pair makes the mth compound-matrix Khatri–Rao product full column rank, with m = R − min(K, R) + 2.This criterion is stated in Proposition 6.6.Source: §6.1 · p. 23

6.2. Generic uniqueness of SFS-CPD.

  • SFS-CPD is generically unique if either of two specified compound-matrix Khatri–Rao products has full column rank for a witness pair.The orders are m_C = R − min(K, R) + 2 and m_A = R − min(I, R) + 2.Source: §6.2 · p. 23

6.3. Examples.

  • For a 9 × 9 × 17 tensor of rank R, CPD is generically unique when R ≤ 20, compared with Theorem 1.18’s guarantee only through R = 17.Source: §6.3 · p. 25
  • A 6 × 7 × 6 tensor of rank 9 is generically unique using the C4(C) ⊙ C4(A) condition, although the two tested C5 products are rank deficient.The C4(C) ⊙ C4(A) matrix has full column rank for a random choice of A and C.Source: §6.3 · p. 25
  • Table 6.2 marks generic-uniqueness bounds not covered by Kruskal’s theorems or Proposition 1.15, and the authors note that many bounds also apply to constrained CPDs.The discussed constrained examples include Hankel third factors and Toeplitz first two factors.Source: §6.3 · pp. 25–27, Table 6.2 · p. 26
  • Simulations suggest that condition (W5) gives generic uniqueness for rank 10 in the 7 × 7 × 7 case, while the demonstrated (C5) condition reaches rank 9.The authors suggest that starting from Proposition 1.22 may yield further relaxed generic-uniqueness results.Source: §6.3 · p. 27

7. Conclusion.

The uniqueness procedure extends to decompositions with equal or structured factor matrices. Fewer independent entries in the generic setting may lower the rank up to which uniqueness is guaranteed.

7. Conclusion.

  • The same uniqueness procedure adapts to equal or structured factor matrices, though fewer independent entries in generic sampling may decrease the guaranteed rank bound.The text names Toeplitz, Hankel, and Vandermonde structures as examples.Source: §7 · p. 27
Loading 1301.4603v1…