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

Alwin Stegeman, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

177 Scopus citations

Abstract

Let 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.

Original languageEnglish (US)
Pages (from-to)540-552
Number of pages13
JournalLinear Algebra and Its Applications
Volume420
Issue number2-3
DOIs
StatePublished - Jan 15 2007
Externally publishedYes

Bibliographical note

Funding Information:
∗ Corresponding author. Tel.: +31 50 363 6193; fax: +31 50 363 6304. E-mail addresses: [email protected] (A. Stegeman), [email protected] (N.D. Sidiropoulos). 1 The author is supported by the Dutch Organisation for Scientific Research (NWO), VENI grant 451-04-102.

Keywords

  • Candecomp
  • Kruskal-rank condition
  • Parafac
  • Three-way arrays
  • Uniqueness

Fingerprint

Dive into the research topics of 'On Kruskal's uniqueness condition for the Candecomp/Parafac decomposition'. Together they form a unique fingerprint.

Cite this