Canonical polyadic decomposition of third-order tensors: Relaxed uniqueness conditions and algebraic algorithm

In the particular case R=K, the new bound above is equivalent to the bound R≤(I−1)(J−1) which is known to be necessary and sufficient for the generic uniqueness of the CPD. An existing algebraic algorithm (based on simultaneous diagonalization of a set of matrices) computes the CPD under the more restrictive constraint R(R−1)≤I(I−1)J(J−1)/2 (implying that R<(J−12)(I−12)/2+1). We give an example of a low-dimensional but high-rank CPD that cannot be found by optimization-based algorithms in a reasonable amount of time while our approach takes less than a second. We demonstrate that, at least for R≤24, our algorithm can recover the rank-1 tensors in the CPD up to R≤(I−1)(J−1).