Kruskal's Permutation Lemma and the identification of CANDECOMP/PARAFAC and bilinear models with constant modulus constraints

Tao Jiang, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

150 Scopus citations


CANDECOMP/PARAFAC (CP) analysis is an extension of low-rank matrix decomposition to higher-way arrays, which are also referred to as tensors. CP extends and unifies several array signal processing tools and has found applications ranging from multidimensional harmonic retrieval and angle-carrier estimation to blind multiuser detection. The uniqueness of CP decomposition is not fully understood yet, despite its theoretical and practical significance. Toward this end, we first revisit Kruskal's Permutation Lemma, which is a cornerstone result in the area, using an accessible basic linear algebra and induction approach. The new proof highlights the nature and limits of the identification process. We then derive two equivalent necessary and sufficient uniqueness conditions for the case where one of the component matrices involved in the decomposition is full column rank. These new conditions explain a curious example provided recently in a previous paper by Sidiropoulos, who showed that Kruskal's condition is in general sufficient but not necessary for uniqueness and that uniqueness depends on the particular joint pattern of zeros in the (possibly pretransformed) component matrices. As another interesting application of the Permutation Lemma, we derive a similar necessary and sufficient condition for unique bilinear factorization under constant modulus (CM) constraints, thus providing an interesting link to (and unification with) CP.

Original languageEnglish (US)
Pages (from-to)2625-2636
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number9
StatePublished - Sep 2004

Bibliographical note

Funding Information:
Manuscript received June 6, 2003; revised October 1, 2003. This work was supported by the Army Research Laboratory through participation in the ARL Collaborative Technology Alliance (ARL-CTA) for Communications and Networks under Cooperative Agreement DADD19-01-2-0011 and the National Science Foundation under Grants NSF/CAREER CCR-0096165 and NSF/Wireless IT & Networks CCR-0096164. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Martin Haardt.


Dive into the research topics of 'Kruskal's Permutation Lemma and the identification of CANDECOMP/PARAFAC and bilinear models with constant modulus constraints'. Together they form a unique fingerprint.

Cite this