Kruskal's Condition for CP Identifiability

Why CP Identifiability Needs a Condition

A CP decomposition writes a three-way tensor as a sum of rank-one terms. Even when the tensor is known exactly, its factors cannot be expected to be unique entry by entry: a factor column can be multiplied by a nonzero constant if another factor column in the same term is divided by that constant. The terms can also be reordered. The relevant question is therefore whether the decomposition is unique up to permutation and scaling.

Kruskal’s condition gives a practical sufficient answer in terms of the factor matrices. It is sufficient, not necessary: passing the test certifies uniqueness, while failing it does not establish that a decomposition is nonunique. The condition uses k-rank, which measures independence of every small subset of columns rather than the rank of the whole matrix alone.

K-Rank and the Uniqueness Statement

Definition: For a matrix $A$ with $R$ columns, its k-rank, denoted $k_A$, is the largest integer $k$ such that every set of $k$ columns of $A$ is linearly independent. If $A$ has a zero column, then $k_A=0$. In particular, if $A$ has no zero columns, $k_A\geq 1$.

The k-rank is not the ordinary matrix rank. For example, a matrix may have ordinary rank 2 and four nonzero columns, but if two of those columns are proportional, its k-rank is only 1. A k-rank of $k$ guarantees independence for all subsets of size at most $k$, since a dependent smaller subset could be extended to a dependent subset of size $k$.

Let $a_r,b_r,c_r$ be the columns of factor matrices $A,B,C$, respectively. The CP decomposition under consideration is

\mathcal{X}=\sum_{r=1}^{R}a_r\otimes b_r\otimes c_r .

Here each term is a rank-one tensor. Its factors are assumed nonzero; otherwise the term is zero and it is not a rank-one component. A decomposition is essentially unique if any other decomposition with the same number of nonzero rank-one terms has the same terms after a common permutation and reciprocal rescaling of their factors.

Theorem (Kruskal’s condition): Suppose $\mathcal{X}$ has a CP decomposition with $R$ nonzero terms and factor matrices $A,B,C$. If $$ k_A+k_B+k_C\geq 2R+2, $$ then the tensor rank of $\mathcal{X}$ is $R$, and its $R$-term CP decomposition is essentially unique. In particular, for any other $R$-term decomposition with factor matrices $A',B',C'$, there are a permutation matrix $P$ and nonsingular diagonal matrices $D_A,D_B,D_C$ such that $$ A'=APD_A,\qquad B'=BPD_B,\qquad C'=CPD_C,\qquad D_AD_BD_C=I. $$

The final identity expresses the scaling freedom: within each matched term, the three scaling factors multiply to 1, so the rank-one tensor itself is unchanged.

The Khatri–Rao Bound

A useful way to check Kruskal’s condition is to combine information about two factor matrices. For matrices with the same number $R$ of columns, their Khatri–Rao product $A\odot B$ has columns $a_r\otimes b_r$. The following bound requires both matrices to have no zero columns; without that hypothesis, a zero column in either factor gives a zero column in the product.

Theorem (Khatri–Rao k-rank bound): If $A$ and $B$ have the same number $R$ of columns and neither has a zero column, then $$ k_{A\odot B}\geq \min(k_A+k_B-1,R). $$

Proof. Set $q=\min(k_A+k_B-1,R)$, and take any $s\leq q$ columns of $A\odot B$. Suppose a linear combination of them is zero. Let $T$ be the subset whose coefficients are nonzero, and write $t=|T|$. If $T$ is empty, the combination is trivial. Otherwise, reshaping each vector $a_r\otimes b_r$ into a matrix gives

A_T\operatorname{diag}(x_T)B_T^{\mathsf T}=0.

The diagonal matrix is invertible because $x_T$ contains exactly the nonzero coefficients. The Sylvester rank inequality, applied to the product of these three matrices, gives

\operatorname{rank}\!\left(A_T\operatorname{diag}(x_T)B_T^{\mathsf T}\right) \geq \operatorname{rank}(A_T)+\operatorname{rank}(B_T)-t \geq \min(k_A,t)+\min(k_B,t)-t.

Since $t\leq k_A+k_B-1$, the last quantity is positive. Indeed, if $t\leq k_A$ or $t\leq k_B$, it is at least 1 because both k-ranks are at least 1; otherwise it equals $k_A+k_B-t\geq 1$. This contradicts the displayed zero matrix. Thus every set of at most $q$ columns of $A\odot B$ is independent, proving the bound. $\square$

Why Kruskal’s Condition Gives Uniqueness

The central algebraic step is Kruskal’s permutation lemma. It is useful to state the version that also handles a proposed decomposition with fewer terms, since tensor rank must be established rather than assumed.

Kruskal’s permutation lemma: Let a tensor have a decomposition with $R$ nonzero terms and factor k-ranks $k_A,k_B,k_C$, where $k_A+k_B+k_C\geq 2R+2$. Any other expression of the tensor as a sum of $S\leq R$ nonzero rank-one terms must have $S=R$. When $S=R$, its terms match the original terms up to a common permutation and nonzero factor scalings whose product within each term is 1.

The lemma’s proof uses contractions and a finite-set matching argument. For a vector $x$ in the dual space of the first mode, contracting the tensor in that mode gives the matrix

B\operatorname{diag}(A^{\mathsf T}x)C^{\mathsf T}.

If the nonzero entries of $A^{\mathsf T}x$ have index set $T$, the Sylvester inequality gives the lower bound

\operatorname{rank}\!\left(B_T\operatorname{diag}((A^{\mathsf T}x)_T)C_T^{\mathsf T}\right) \geq \min(k_B,|T|)+\min(k_C,|T|)-|T|.

This bound, and its versions for contractions in the other modes, distinguish how many component indices a contraction can retain. The k-rank condition ensures that the bounds in the three modes overlap strongly enough to identify the same component indices. The finite-set matching argument then matches the terms in the two expressions; it also rules out an expression with fewer than $R$ nonzero terms. Once terms are matched, equality of the rank-one tensors gives proportional factor columns, with the three proportionality constants multiplying to 1. This is the content of the permutation lemma; it is the classical algebraic step behind Kruskal’s condition.

Proof of Kruskal’s condition. Apply the permutation lemma to the given $R$-term expression. It rules out every expression with fewer than $R$ nonzero terms, so the tensor rank is $R$. It also says that any other $R$-term expression matches the original terms up to a permutation and scalings whose product within each term is 1. Collecting those scalings into diagonal matrices gives $A'=APD_A$, $B'=BPD_B$, and $C'=CPD_C$, with $D_AD_BD_C=I$. Hence the decomposition is essentially unique. $\square$

The permutation lemma should not be applied to a shorter expression padded with zero terms: those added terms are not nonzero rank-one terms, so the lemma’s hypotheses do not hold. The lemma’s rank conclusion is instead the required separate lower bound on the number of terms.

Worked Applications

Worked Example: A Three-Term Decomposition Certified as Unique

Suppose $R=3$, and let $A$ and $B$ be $3\times3$ identity matrices. Let

C=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}.

The three columns of $A$ are independent, so $k_A=3$. The same reasoning gives $k_B=3$. The columns of $C$ are $(1,0)^{\mathsf T}$, $(0,1)^{\mathsf T}$, and $(1,1)^{\mathsf T}$. Each is nonzero, and no pair is proportional, so $k_C=2$. Therefore

$$ k_A+k_B+k_C=3+3+2=8=2(3)+2. $$

Kruskal’s condition holds at equality. Thus any tensor expressed by these three nonzero rank-one terms has tensor rank 3, and the decomposition is unique up to permutation and reciprocal rescaling. For instance, the Khatri–Rao bound also gives $k_{B\odot C}\geq\min(3+2-1,3)=3$, consistent with all three paired columns being independent.

Worked Example: Using the Khatri–Rao Bound with Five Terms

Take $R=5$. Let $A,B,C$ each be a $4\times5$ Vandermonde matrix with distinct real nodes in its columns; for example, use nodes $1,2,3,4,5$ and rows corresponding to powers 0 through 3. Any four columns form a square Vandermonde matrix with nonzero determinant, so each factor has k-rank 4. Thus

$$ k_A+k_B+k_C=4+4+4=12=2(5)+2. $$

The condition certifies essential uniqueness and tensor rank 5. To check one paired factor directly from the bound,

k_{A\odot B}\geq\min(4+4-1,5)=5.

The nonzero-column hypothesis is satisfied because every Vandermonde column begins with an entry equal to 1. Hence $A\odot B$ has five independent columns. This calculation illustrates why the bound is useful: neither $A$ nor $B$ needs to have five independent columns on its own for their paired columns to be independent.

Worked Example: A Failed Test Is Not a Nonuniqueness Proof

Let $R=4$. Choose the columns of a $2\times4$ matrix $A$ to be $(1,0)^{\mathsf T},(0,1)^{\mathsf T},(1,1)^{\mathsf T},(1,2)^{\mathsf T}$. No two are proportional, so $k_A=2$. Let $B$ and $C$ be $3\times4$ Vandermonde matrices at the distinct nodes $1,2,3,4$; any three columns are independent, so $k_B=k_C=3$. The sum is

$$ k_A+k_B+k_C=2+3+3=8<2(4)+2=10. $$

Kruskal’s sufficient condition does not certify uniqueness for this decomposition. It does not follow that the decomposition is nonunique: this test gives no conclusion when its inequality fails. A different argument may still establish uniqueness for a particular tensor.

Common Pitfalls and Practical Use

Confusing ordinary rank with k-rank. Ordinary rank describes the dimension of the full column span; k-rank asks how many columns are guaranteed independent in every subset. A few dependent columns can make k-rank much smaller than ordinary rank.
Using the Khatri–Rao bound with a zero column. Both factors must have no zero columns. A zero column makes the corresponding product column zero, invalidating a positive lower bound.
Calling the condition necessary. The inequality is sufficient. Failure to meet it means only that this criterion does not certify uniqueness.
Ignoring the allowed indeterminacies. Even an essentially unique decomposition is not entrywise unique: term order and within-term scaling remain free.
Inferring tensor rank from an $R$-term display alone. A representation with $R$ terms only shows tensor rank is at most $R$. The rank conclusion in Kruskal’s theorem uses the permutation lemma to rule out shorter expressions.

In practice, compute or lower-bound each factor’s k-rank, add the three values, and compare with $2R+2$. When the k-ranks are difficult to determine exactly, a valid lower bound can still certify the inequality. The conclusion is powerful precisely because it turns a structural property of the factors into a guarantee about the tensor’s representation.

Check Your Understanding

Use the definitions and results above to answer the following questions.

A factor matrix has one zero column. What is its k-rank, and why can the stated Khatri–Rao bound not be used as if both factors had positive k-rank?
For $R=4$, factor k-ranks are $3,3,4$. Does Kruskal’s condition hold? What conclusion follows?
If $k_A=2$, $k_B=4$, and both factors have no zero columns, what lower bound does the Khatri–Rao inequality give when $R=5$?
Why does failure of Kruskal’s inequality not prove that a CP decomposition is nonunique?
What permutation and scaling freedoms are allowed between two essentially unique CP decompositions?