Source-linked AI summary
On the Uniqueness of the Canonical Polyadic Decomposition of third-order tensors --- Part I: Basic Results and Uniqueness of One Factor Matrix
Ignat Domanov, Lieven De Lathauwer
TL;DR
The paper asks how CPD uniqueness can be established beyond prior conditions, noting that CPD may be unique without orthogonality constraints. It generalizes uniqueness conditions with parameter m and derives relaxed sufficient guarantees for uniqueness of a factor matrix; the no-full-column-rank path to overall uniqueness is taken up in Part II.
Problem
Existing uniqueness theorems motivate more general conditions, while CPD may be unique without orthogonality constraints.
Source: §1.2 · p. 3, §1.3 · p. 5Method
The paper formulates generalized uniqueness conditions parameterized by m and relates families of conditions to establish uniqueness of a particular factor matrix.
Source: §1.3 · pp. 5–6Results
For kC ≥ 1 and m = mC := R − rC + 2, rT = R and C is unique; the general statement (1.12) gives relaxed sufficient conditions for one-factor uniqueness.
Source: §1.3 · pp. 6–7Takeaways & Limitations
CPD may provide a meaningful data representation with unique interpretable components without orthogonality constraints.
Source: §1.2 · p. 3In cases where possibly none of the factor matrices has full column rank, how uniqueness of one or more factor matrices implies overall CPD uniqueness is addressed in Part II.
Source: §5.2 · pp. 19–20
Abstract
from arXiv · showhide
Canonical Polyadic Decomposition (CPD) of a higher-order tensor is decomposition in a minimal number of rank-1 tensors. We give an overview of existing results concerning uniqueness. We present new, relaxed, conditions that guarantee uniqueness of one factor matrix. These conditions involve Khatri-Rao products of compound matrices. We make links with existing results involving ranks and k-ranks of factor matrices. We give a shorter proof, based on properties of second compound matrices, of existing results concerning overall CPD uniqueness in the case where one factor matrix has full column rank. We develop basic material involving $m$-th compound matrices that will be instrumental in Part II for establishing overall CPD uniqueness in cases where none of the factor matrices has full column rank.
1. Introduction.
CPD can provide a unique representation without constraints such as orthogonality, motivating conditions that establish uniqueness of one factor matrix and, ultimately, overall uniqueness. This section reviews prior results and introduces relaxed conditions based on compound matrices, with further overall-uniqueness results deferred to Part II.
1.1. Problem statement.
- A CPD expresses a tensor as a minimal sum of rank-1 terms, and uniqueness allows only permutation and scaling indeterminacies.Tensor rank can differ depending on whether the field is real or complex.Source: §1.1 · p. 2
1.2. Literature overview.
- CPD may be unique without orthogonality constraints, making its uniqueness properties relevant to applications across several fields.The paper cites applications in signal processing, data analysis, chemometrics, and psychometrics.Source: §1.2 · p. 3
1.2.1. Early results on uniqueness of the CPD.
- Early sufficient conditions establish overall CPD uniqueness; one relaxed result requires full column rank in A and B and pairwise independent columns in C.Under those conditions, the tensor rank is R and the CPD is unique.Source: §1.2.1 · p. 3
1.2.2. Kruskal’s conditions.
- Kruskal-type conditions give sufficient uniqueness tests, and the paper presents corrected versions of earlier conditions for uniqueness of one factor matrix.Theorem 1.10 uses kC ≥ 1 and condition (Hm) for A and B to guarantee uniqueness of the third factor matrix.Source: §1.2.2 · pp. 3–4
1.2.3. Uniqueness of the CPD when one factor matrix has full column rank.
- When C has full column rank, equivalent conditions connect a test on A and B to overall CPD uniqueness; a more restrictive compound-matrix condition is also sufficient.The equivalence includes condition (U2) and the claim that the CPD is unique.Source: §1.2.3 · p. 4
1.2.4. Necessary conditions for uniqueness of the CPD. Results concerning rank and k-rank of Khatri-Rao product.
- Necessary results link unique CPDs to full-column-rank Khatri-Rao products and constrain factor k-ranks; further corollaries provide bounds involving those k-ranks.For example, kA + kB ≥ R + 1 implies (C1), and positive kA and kB give a lower bound on k_(A⊙B).Source: §1.2.4 · p. 5
1.3. Results and organization.
- The paper formulates parameterized conditions using compound matrices and establishes implications among them; under stated hypotheses, these yield relaxed sufficient conditions for uniqueness of one factor matrix.The conditions also relate to rank- and k-rank-based results, while m-th compound-matrix material is developed for overall-uniqueness work in Part II.Source: §1.3 · pp. 5–7
- With A⊙B full column rank and the W conditions, the third factor matrix is unique; the paper also simplifies a full-column-rank uniqueness proof and leaves broader overall uniqueness to Part II.Part II addresses cases where possibly none of the factor matrices has full column rank.Source: §1.3 · pp. 6–7
2. Compound matrices and their properties.
The section defines compound matrices through minors indexed by ordered k-subsets and develops properties used in later uniqueness arguments. It also relates these matrices to diagonal scaling, rank conditions, and linear expansions.
2. Compound matrices and their properties.
- The k-th compound matrix Ck(A) consists of determinants of submatrices selected by k row and column indices.The row and column indices range over k-element subsets, with the subsets ordered lexicographically.Source: §2 · p. 7
- Ck(AB)=Ck(A)Ck(B), transposition commutes with taking compounds, and Ck(A) vanishes exactly when k exceeds rank(A).For square A, the Sylvester–Franke theorem gives det(Ck(A))=det(A)^binom(n−1,k−1).Source: §2 · p. 8
- For diagonal matrices, Ck(Diag(d)) is diagonal with entries given by products of k components of d; it is zero exactly when d has at most k−1 nonzero entries.It has exactly one nonzero component when d has exactly k nonzero entries.Source: §2 · p. 8
- The paper connects vectorization with Kronecker products: vec(ba^T)=a⊗b.It then introduces expressions for shared-column matrices A and B and a vector d, used throughout the paper.Source: §2 · pp. 8–9
- Condition (Um) is equivalent to requiring that rank(ADiag(d)B^T)≤m−1 forces d to have at most m−1 nonzero entries.The section also establishes that (Um) implies min(kA,kB)≥m.Source: §2 · p. 9
- A linear map ΦI,m expresses C_m([A x]) as ΦI,m(x)C_{m−1}(A), via Laplace expansion along the appended column.The entries of ΦI,m(x) are entries of x, possibly with signs.Source: §2 · p. 10
3. Basic implications.
This section establishes implications among conditions on compound-matrix Khatri–Rao products, ranks, and factor-matrix uniqueness. It also identifies a limitation on descending the W conditions unless an additional k-rank bound holds.
3. Basic implications.
- The proof that (Um) implies (U1) uses full column rank of the Khatri–Rao product A⊙B.The section identifies A⊙B full column rank with (U1).Source: §3 · pp. 12, 14
- The K, C, H, and U conditions each descend from index m to lower indices under the stated lemmas.For U and C this descent follows from Lemmas 3.7 and 3.6; corresponding descent is given for K and H in Lemmas 3.4 and 3.5.Source: §3 · pp. 11–12
- Condition (Km) implies (Cm), which in turn implies (Um).The first implication is established in Lemma 3.8 and the second in Lemma 3.1.Source: §3 · pp. 11–12
- Condition (Km) also implies (Hm), and (Hm) implies (Um), extending the implication chain through the H conditions.The section states that the implication scheme remains valid when C conditions are replaced by H conditions, with (H1)⇒(U1).Source: §3 · p. 14
- Condition (Um) implies min(kA,kB)≥m; at m=1, it is equivalent to A⊙B having full column rank.The section summarizes the equivalence between (U1) and full column rank of A⊙B.Source: §3 · p. 14
- Unlike the other condition families, (Wm) need not imply lower-index W conditions without an additional k-rank bound.When min(kA,kB)≥m−1, (Wm) does imply (Wm−1), …, (W1).Source: §3 · pp. 14–15
4. Sufficient conditions for the uniqueness of one factor matrix.
The section develops sufficient conditions for uniqueness of one factor matrix, including relaxed criteria expressed through compound-matrix products. Its Wm-based conditions are more relaxed than the earlier Um-based conditions, though they may be hard to check.
4.1. Conditions based on (Um), (Cm), (Hm), and (Km).
- When (Um) holds, the tensor has rank R and its third factor matrix is unique.Source: §4.1 · p. 16
- The (Cm) criterion guarantees rank R and third-factor uniqueness when kC ≥ 1, m = R − rC + 2 ≤ min(I, J), and Cm(A) ⊙ Cm(B) has full column rank.The related (Cm), (Hm), and (Km) conditions are more restrictive than (Um), but may be easier to verify.Source: §4.1 · p. 16
4.2. Conditions based on (Wm).
- The (Wm) criterion is more relaxed than (Um), yet may be hard to check; under the stated assumptions, it guarantees rank R and third-factor uniqueness.Proposition 4.9 assumes A ⊙ B has full column rank and conditions (Wm) through (W1).Source: §4.2 · p. 17
- The example satisfies (W5) and has rT = 7 with a unique third factor matrix; (Um) does not hold because min(kA, kB) < m.Source: §4.2 · p. 18
- With kC = 1, the example's tensor CPD is not unique even though its third factor matrix is unique.Source: §4.2 · p. 18
5. Overall CPD uniqueness.
For the case where one factor matrix has full column rank, the paper gives a shorter proof of existing overall CPD uniqueness results. It also distinguishes results that establish individual factor uniqueness from the further step to overall uniqueness when no factor has full column rank, which it leaves to Part II.
5.1. At least one factor matrix has full column rank.
- The proof of Theorem 1.11 uses Proposition 4.3 to establish uniqueness of C, then derives uniqueness of the overall CPD when C has full column rank.Source: §5.1 · p. 19
- Theorem 1.12 follows from Theorem 1.11, and Theorem 1.13 follows from Theorem 1.12, yielding overall CPD uniqueness under their respective conditions.Source: §5.1 · pp. 18–19
- For tensor rank R ≤ 4, the paper gives necessary and sufficient uniqueness conditions when rC = R; for R ≤ 3, (K2) is the easiest listed condition to check.For R = 4, (H2), (C2), and (U2) are equivalent.Source: §5.1 · p. 19
5.2. No factor matrix is required to have full column rank.
- When no factor matrix is required to have full column rank, the stated condition kA + kB + kC ≥ 2R + 2 accompanies rank R and uniqueness of every factor matrix.Source: §5.2 · p. 19
- The paper leaves for Part II the generalization from uniqueness of one or more factor matrices to overall uniqueness when possibly none has full column rank.Source: §5.2 · pp. 19–20
6. Conclusion.
The conclusion passage consists of acknowledgments to the anonymous reviewers and Professor A. Stegeman.
6. Conclusion.
- The authors thank the anonymous reviewers and Professor A. Stegeman for comments and suggestions.Source: §7 · p. 20