Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition

1.1. Basic notations and terminology.

• A CPD is a minimal sum of rank-1 tensors, unique up to permutation of terms and compensating within-term scaling; k-rank measures column independence.The paper writes the decomposition as T = [A, B, C]R, with A, B, and C as its factor matrices.Source: §1.1 · pp. 1–2

1.2. Problem statement.

• The paper studies noiseless CPD and computes it algebraically using matrix operations, compound matrices, orthogonal complements, and generalized eigenvalue decomposition.For a two-slice tensor with nonsingular A and B and distinct diagonal entries, GEVD recovers the factor vectors; more generally, the cited setup requires full-column-rank A and B and noncollinear columns of C.Source: §1.2 · pp. 2–3

1.3. Previous results on uniqueness and algebraic algorithms.

• Prior algebraic algorithms cover cases with full-column-rank factors, while Kruskal’s condition guarantees CPD uniqueness and compound-matrix conditions provide further uniqueness results.The section notes that the prior algorithmic results include a full-column-rank condition and a compound-matrix criterion; its new results build on these uniqueness guarantees.Source: §1.3 · pp. 3–4

1.4. New results.

• Theorems 1.6–1.7 and Corollaries 1.8–1.9 give conditions for unique, algebraic CPD computation, including when kC < rC and under Kruskal’s condition.Theorem 1.6 assumes kC = rC; Theorem 1.7 extends the result to kC < rC with tighter conditions on A and B. Corollary 1.9 uses kA + kB + kC ≥ 2R + 2.Source: §1.4 · pp. 4–5

1.5. Organization.

• The algorithms first recover a scaled and permuted B(C) from a tensor-derived compound-matrix construction, then recover C, A, and B through either of two routes.One route reconstructs C before A and B, but full exploitation of its structure has combinatorial complexity; the alternative recovers A and B first using two-slice subtensors, then C.Source: §1.5 · p. 7
• The paper concludes with a rank-5 4 × 4 × 4 example and a generic rank-9 6 × 6 × 7 example comparing algorithm complexity; neither CPD’s uniqueness follows from Kruskal’s theorem.Source: §1.5 · p. 7

1.6. Link with [6].

• The recalled algorithm (K=R, m=2) builds a symmetric-kernel space, recovers C through an auxiliary tensor with full-column-rank factors, then obtains A and B.It forms R2(T) from the frontal slices, intersects its kernel with vectorized symmetric matrices, and uses the resulting space to construct the auxiliary tensor.Source: §1.6 · pp. 7–8

2.1. Matrices whose entries are determinants.

• The k-th compound matrix is formed from k × k minors; C_k(A) is zero exactly when k exceeds the rank of A.The Binet–Cauchy formula gives a product rule for compound matrices of matrix products.Source: §2.1 · pp. 8–9
• For a square nonsingular C, B(C) is formed from (K−1) × (K−1) minors, and its columns are orthogonal to exactly K−1 columns of C.The stated properties also allow recovery of C up to column permutation and scaling from B(C) known up to those indeterminacies.Source: §2.1 · pp. 9–10

2.2. Matrices whose entries are permanents.

• The permanent differs from the determinant by omitting permutation signatures, and the permanental compound matrix uses permanents of submatrices as its entries.The construction also introduces Q_m(C), which removes repeated rows arising from invariance under column permutations.Source: §2.2 · pp. 10–11

2.3. Links between matrix Rm(C), matrix B(C) and symmetrizer.

• The main result of the section links B(C) and R_m(C), with Proposition 2.13 specifying the conditions and full-column-rank conclusion.The proposition assumes m = R−K+2 and k_C ≥ K−1.Source: §2.3 · pp. 11–12
• When k_C ≥ K−1, Proposition 2.13 states that R_m(C) has full column rank.It also identifies the dimension of its transposed range with the relevant binomial coefficient.Source: §2.3 · p. 12
• The symmetrizer’s range has an orthogonal basis given by the columns of G, while H compresses symmetric tensors and G reverses that compression.The stated relation is HG = I.Source: §2.3 · pp. 12–13
• R_m(C) is formed by selecting combinations of m columns of C and symmetrizing the corresponding rank-1 tensors; this symmetrization introduces permanents.The symmetrizer averages the tensors obtained by permuting indices.Source: §2.3 · pp. 11–12

3.1. Mixed discriminants.

• The mixed discriminant is the coefficient of x_1···x_m in det(x_1T_1+···+x_mT_m), and it is multilinear and symmetric in its arguments.Polarization is the technique used to obtain it from a determinant.Source: §3.1 · pp. 14–15

3.2. Polarized compound matrices.

• The polarized compound matrix replaces determinants in compound matrices with mixed discriminants and is multilinear and symmetric in its matrix arguments.When all arguments are equal, it equals m! times the m-th compound matrix; it is zero exactly when the matrix rank is at most m−1.Source: §3.2 · p. 15

3.3. Transformation of the tensor.

• R_m(T) stacks polarized compound matrices for all slice combinations, while Q_m(T) removes duplicates and is the smaller matrix used in the algorithms.For T = [A, B, C]_R, the lemma expresses both matrices through the compound matrices of A and B and the corresponding matrices of C, and links their kernels.Source: §3.3 · p. 16

4.1. Algorithm 1.

• Under the stated full-column-rank and k_C = K assumptions, Algorithm 1 recovers C first and then A and B algebraically, using a GEVD for an intermediate CPD.Its second phase can have combinatorial complexity and quickly become computationally infeasible; partially exploiting dependencies can reduce the work.Source: §4.1 · pp. 17–18

4.2. Algorithm 2.

• Algorithm 2 reduces computational cost by reversing the recovery order: after finding B(C), it uses suitable pairs of tensor slices and GEVDs to recover A and B before C.Suitable pairs are characterized by the rank-m condition on the concatenated slices; each corresponding tensor has rank m and yields m columns of A and B.Source: §4.2 · pp. 18–20

4.3. Discussion of working conditions.

• The algorithms’ key failure signals concern Phase 1: an oversized null space indicates k_C < K − 1 or deficient C_m(A) ⊙ C_m(B), while failure at step 5 after step 2 succeeds indicates k_C = K − 1.When the null space has dimension C_{K−1}^R, k_C ≥ K − 1 and C_m(A) ⊙ C_m(B) has full column rank; with the additional stated rank and factor conditions, k_C = K.Source: §4.3 · p. 20

4.4. Theorem 1.7.

• Theorem 1.7’s construction compresses the third factor by X, enabling algebraic recovery from a transformed tensor when X preserves the k-rank of C.For generic X, k_{XC} = k_C; the transformed tensor’s CPD yields A ⊙ B up to permutation and scaling, from which C is recovered. The procedure remains termed algebraic despite using random linear combinations of frontal slices.Source: §4.4 · pp. 20–21
• Under Theorem 1.7, a random projection reduces the third dimension to k_C, after which Algorithm 1 or 2 computes the reduced tensor’s CPD and recovers C.The procedure forms T̄ = Matr(T)X^T, then computes the CPD of the resulting I × J × k_C tensor.Source: §4.4 · p. 21

4.5. Examples.

• Although condition (1.6) fails, the example meets Theorem 1.6’s conditions for m = 3, so Algorithms 1 and 2 can find the factor matrices.The passage notes that Kruskal’s theorem does not establish the CPD’s rank and uniqueness in this case.Source: §4.5 · p. 21
• Algorithm 1 identifies C up to column permutation and scaling from the left kernels of five rank-3 submatrices, then computes three component products directly.The remaining two component products are found by the subsequent procedure.Source: §4.5 · p. 22
• Algorithm 2 uses selected rank-3 tensor pairs to estimate columns of A and B, clusters their collinear products, and recovers C up to scaling and permutation.The clustered centers coincide with A ⊙ B up to column scaling and permutation.Source: §4.5 · p. 23
• In less than 9 seconds, Algorithm 2 computed the CPD of a generic 6 × 6 × 7 tensor of rank 9.The suboptimal MATLAB implementation checked 3,486 matrices and computed 756 rank-4 tensors; the corresponding Phase 2 of Algorithm 1 was computationally infeasible.Source: §4.5 · p. 23

5. Conclusion.

• The two proposed CPD algorithms rely on standard linear algebra and reduce computation to GEVD using properties of compound matrices and permanents.The derivation covers cases beyond Kruskal’s bound.Source: §5 · p. 23
• The paper treats exact CPD; it suggests using an exact result to initialize iterative algorithms for noisy-tensor approximation.The authors defer numerical aspects to another paper and note that current Tensorlab algorithms for the associated partially symmetric structure are optimization-based, without formal solution guarantees.Source: §5 · p. 23

S.1. Supplementary material related to Proposition 1.10.

• When kC = K, B(C) has no proportional columns; for kC ≥ K − 1, it has no zero columns and each column is orthogonal to the span of its corresponding K − 1 columns of C.These statements are given in Lemma S.1.1.Source: §S.1 · p. 26
• For kC = K, CT B(C) has exactly K − 1 zero entries in each specified column, at the indices of that column’s tuple.The passage also gives the corresponding row-wise zero pattern.Source: §S.1 · pp. 26–27
• B(C)(R−K+1) has full column rank under the stated kC = K condition.The proof establishes this by showing that a vector annihilating the matrix must be zero.Source: §S.1 · p. 27

S.2. Supplementary material related to properties (P1)–(P4).

• A linear map with kernel span{c1} reduces the argument to dimension K − 1, after which the vector is shown proportional to one of c2, . . . , cR.The proof applies the map to the relation and uses kC = K to obtain kC̃ = K − 1.Source: §S.2 · pp. 28–29
• Condition (K,R) is established for R ≥ K by induction, using the base cases and the implication from conditions at smaller indices.Lemma S.2.1 supplies the recursive step from conditions (K−1,R−1) and (K,R−1) to condition (K,R).Source: §S.2 · pp. 28–29
• The passage says (P1) follows from Lemma S.1.2(i), (P2) from Lemma S.1.1(iii), and (P3) from Lemma S.1.2(ii); it gives no completed dependency for (P4).Source: §S.2 · p. 29

S.3. Supplementary material related to Lemma 2.17.

• Qm(C)T is obtained from Rm(C)T by removing repeated columns.A column indexed by a tuple in Qm(C)T coincides with the corresponding permutation-indexed column in Rm(C)T.Source: §S.3 · p. 29
• The ((i1, . . . , im), (j1, . . . , jm))-th entry of Rm(C)T G is expressed using a permanent of C.The proof gives the expression as perm C((j1, . . . , jm), (q1, . . . , qm)).Source: §S.3 · p. 29
• The permanent is unchanged when the tuple (i1, . . . , im) is permuted, yielding the entry equality used in Lemma 2.17(ii).The equality follows from the definition of the matrix Qm(C)T.Source: §S.3 · p. 29

• Symmetry makes every unfolding of X equal to the rank-one matrix yzT, so X itself is rank one and x is proportional to y⊗⋯⊗y.Source: §S.4 · p. 30
• The equation implies that y is orthogonal to at least K−1 columns of C.This follows from the product of inner products in (2.9).Source: §S.4 · p. 30
• Because kC = K−1, y is proportional to a column of B(C), and the proof concludes an upper bound on the number of nonzero solutions.Source: §S.4 · p. 30

• Full column rank of Cm(A) ⊙ Cm(B) implies min(kA, kB) ≥ m and max(r bA, r bB) ≥ min(bm, m + 1).Source: §S.5 · p. 30
• For Lemma 4.4, the proof assumes F = B(C) without loss of generality and associates indices with multi-index analogues.Source: §S.5 · p. 30
• The proof states that conditions (i)–(iii) are equivalent to bm = m.It derives the equivalences for (ii) and (iii) from rank inequalities.Source: §S.5 · p. 31
• The proof establishes full column rank for bC ⊙ bB and bC ⊙ bA, then uses resulting rank bounds to prove the equivalences.The displayed bounds include max(r bA, r bB) ≥ min(bm, m + 1) and min(r bA, r bB) ≥ m.Source: §S.5 · p. 31

• The passage states that the full matrix Q3(T) is given.Source: §S.6 · p. 32