On Kruskal’s uniqueness condition for the Candecomp/Parafac decomposition

AbstractLet X be a real-valued three-way array. The Candecomp/Parafac (CP) decomposition is written as X=Y(1)+⋯+Y(R)+E, where Y(r) are rank-1 arrays and E is a rest term. Each rank-1 array is defined by the outer product of three vectors a(r), b(r) and c(r), i.e. yijk(r)=ai(r)bj(r)ck(r). These vectors make up the R columns of the component matrices A, B and C. If 2R+2 is less than or equal to the sum of the k-ranks of A, B and C, then the fitted part of the decomposition is unique up to a change in the order of the rank-1 arrays and rescaling/counterscaling of each triplet of vectors (a(r),b(r),c(r)) forming a rank-1 array. This classical result was shown by Kruskal. His proof is, however, rather inaccessible and does not seem intuitive. In order to contribute to a better understanding of CP uniqueness, this paper provides an accessible and intuitive proof of Kruskal’s condition. The proof is both self-contained and compact and can easily be adapted for the complex-valued CP decomposition