Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

By Joseph B. Kruskal. 1977

Abstract A three-way array X (or three-dimensional matrix) is an array of numbers xijk subscripted by three indices. A triad is a multiplicative array, xijk = aibjck. Analogous to the rank and the row rank of a matrix, we define rank (X) to be the minimum number of triads whose sum is X, and dim1(X) to be the dimensionality of the space of matrices generated by the 1-slabs of X. (Rank and dim1 may not be equal.) We prove several lower bounds on rank. For example, a special case of Theorem 1 is that rank(X)⩾dim 1 (UX) + rank(XW) − dim 1 (UXW) , where U and W are matrices; this generalizes a matrix theorem of Frobenius. We define the triple product [A, B, C] of three matrices to be the three-way array whose (i, j, k) element is given by ⩞rairbjrckr; in other words, the triple product is the sum of triads formed from the columns of A, B, and C. We prove several sufficient conditions for the factors of a triple product to be essentially unique. For example (see Theorem 4a), suppose [A, B, C] = [ A , B , C ] , and each of the matrices has R columns. Suppose every set of rank (A) columns of A are independent, and similar conditions hold for B and C. Suppose rank (A) + rank (B) + rank (C) ⩾ 2R + 2. Then there exist diagonal matrices Λ, M, N and a permutation matrix P such that A = APΛ, B = BP M , C = CP N . Our results have applications to arithmetic complexity theory and to statistical models used in three-way multidimensional scaling.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Identifying Finite Mixtures of Nonparametric Product Distributions and Causal Inference of Confounders (2013, methodology): “Allman et al. (2009) established identiﬁability of the parameters whenever d ≥ 3 and for all m under weak conditions 1 , using a theorem of Kruskal (1977).”
Identifiability of parameters in latent structure models with many observed variables (2008, methodology): “This simply echos the nonidentifiability in the case of 2 variates with finite state spaces commented on in [30].”
Tensor decompositions for learning latent variable models (2012, methodology): “ade, 2013). In these contexts, it is often also possible to establish strong identiﬁability results, without giving an explicit estimators, by invoking the non-constructive identiﬁability argument of Kruskal (1977)—see the article by Allman et al. (2009) for several examples. Related simultaneous di”
CANDECOMP/PARAFAC Decomposition of High-Order Tensors Through Tensor Reshaping (2012, methodology): “By exploiting the uniqueness of CPD under mild conditions (see discussion on uniqueness conditions for order-3 CPD in [33], [34], [27] and for higher order CPD in [35]–[37]), and the relation of a tensor in the Kruskal form [38] and its unfolded tensor, we develop a fast approach for high order and ”
Typed Tensor Decomposition of Knowledge Bases for Relation Extraction (2014, methodology): “The CP (CANDECOMP/PARAFAC) decomposition (Kruskal, 1977; Kiers, 2000) approximates a tensor by a sum of rank-one tensors, while the Tucker decomposition (Tucker, 1966), also known as high-order SVD (De Lathauwer et al.”
A scalable optimization approach for fitting canonical tensor decompositions (2011, background): “CP is known to be unique when it satisﬁes, e.g., the Kruskal conditions [5] (see Reference [4 § 3.2] for a survey), but only up to permutation and scaling of the factor matrices.”
Non-negative tensor factorization with applications to statistics and computer vision (2005, background): “…of tensor ranks, is that unlike matrix factorization, which is generally non-unique for any rank greater than one, a 3-valence tensor decomposition is essentially unique under mild conditions (Kruksal, 1977) and the situation actually improves in higher dimensions n > 3 (Sidiropoulos & Bro, 2000).”
On generic identifiability of symmetric tensors of subgeneric rank (2015, background): “To the best of our knowledge, the best bound that is applicable for Veronese embeddings of any degree d ≥ 3 is the so-called Kruskal condition [22, 23].”
Concurrent EEG/fMRI analysis by multiway Partial Least Squares (2004, methodology): “It has been shown that if the data are approximately trilinear, the correct number of components is used, and the signalto-noise ratio is adequate, then the PARAFAC algorithm will show the true underlying phenomena (Kruskal, 1976, 1977).”
Distributed large-scale tensor decomposition (2014, background): “A sufﬁcient condition for the essential uniqueness of the CPD was ﬁrst established by Kruskal in [18], and states that A , B and C can be uniquely estimated (up to column permutation and scaling) if k A + k B + k C ≥ 2 R + 2 , where k ( · ) denotes the Kruskal-rank, or “k-rank”, of its matrix…”
Decomposition of homogeneous polynomials with low rank (2010, background): “We give an example showing that if m = 2, then Theorem 2 is sharp (see Example 2), even taking B in linearly general position.”
Semi-Parametric Estimation for Conditional Independence Multivariate Finite Mixture Models (2015, background): “One attractive feature of Model (1.2) is the fact that the multivariate density functions for each mixture component may be studied via their univariate marginal densities, since the conditional independence implies that each fj factors into the product of its marginals.”
Tensor Decompositions for Signal Processing Applications: From two-way to multiway component analysis (2014, background): “Another indeterminacy is related to the physical meaning of the factors: if the model in (1) is unconstrained, it admits inﬁnitely many combinations of A and B .”