Tensor rank decomposition

In multilinear algebra, the tensor rank decomposition or canonical polyadic decomposition (CPD) is one generalization of the matrix singular value decomposition (SVD) to tensors, which have found application in statistics, signal processing, computer vision, computer graphics, psychometrics, linguistics and chemometrics. The tensor rank decomposition was introduced by Hitchcock in 1927 and later rediscovered several times, notably in psychometrics. 
For this reason, the tensor rank decomposition is often referred to as CANDECOMP, PARAFAC, or CANDECOMP/PARAFAC (CP).
Another popular generalization of the matrix SVD is known as the higher-order singular value decomposition.
Notation.
A scalar variable is denoted by lower case italic letters, formula_1 and a constant scalar is denoted by an upper case italic letter, formula_2.
Indices are denoted by a combination of lowercase and upper case italic letters, formula_3. Multiple indices that one might encounter when referring to the multiple modes of a tensor are conveniently denoted by formula_4 where formula_5.
A vector is denoted by a lower case bold Times Roman, formula_6 and a matrix is denoted by bold upper case lettering formula_7.
A higher order tensor is denoted by calligraphic letters,formula_8. An element of an formula_9-order tensor formula_10 is denoted by formula_11 or formula_12.
Definition.
A tensor is a multilinear transformation that maps a set of vector spaces to another vector space. A data tensor is a collection of multivariate observations organized into a M-way array.
Consider a data tensor formula_13, where formula_14 is either the real field formula_15 or the complex field formula_16. Every (order-formula_9, refers to the number of modes) tensor in this space may then be represented with a suitably large formula_18 as a linear combination of formula_18 rank-1 tensors:
where formula_21 and formula_22 where formula_23. When the number of terms formula_18 is minimal in the above expression, then formula_18 is called the rank of the tensor, and the decomposition is often referred to as a "(tensor) rank decomposition", "minimal CP decomposition", or "Canonical Polyadic Decomposition (CPD)". Contrariwise, if the number of terms is not minimal, then the above decomposition is often referred to as "formula_18-term decomposition", "CANDECOMP/PARAFAC" or "Polyadic decomposition".
Tensor rank.
Contrary to the case of matrices, the rank of a tensor is presently not understood well. It is known that the problem of computing the rank of a tensor is NP-hard. The only notable well-understood case consists of tensors in formula_27, whose rank can be obtained from the Kronecker–Weierstrass normal form of the linear matrix pencil that the tensor represents. A simple polynomial-time algorithm exists for certifying that a tensor is of rank 1, namely the higher-order singular value decomposition.
The rank of the tensor of zeros is zero by convention. The rank of a tensor formula_28 is one, provided that formula_29.
Field dependence.
The rank of a tensor depends on the field over which the tensor is decomposed. It is known that some real tensors may admit a complex decomposition whose rank is strictly less than the rank of a real decomposition of the same tensor. As an example, consider the following real tensor
where formula_31. The rank of this tensor over the reals is known to be 3, while its complex rank is only 2 because it is the sum of a complex rank-1 tensor with its complex conjugate, namely
where formula_33.
In contrast, the rank of real matrices will never decrease under a field extension to formula_16: real matrix rank and complex matrix rank coincide for real matrices.
Generic rank.
The generic rank formula_35 is defined as the least rank formula_18 such that the closure in the Zariski topology of the set of tensors of rank at most formula_18 is the entire space formula_38. In the case of complex tensors, tensors of rank at most formula_35 form a dense set formula_40: every tensor in the aforementioned space is either of rank less than the generic rank, or it is the limit in the Euclidean topology of a sequence of tensors from formula_40. In the case of real tensors, the set of tensors of rank at most formula_35 only forms an open set of positive measure in the Euclidean topology. There may exist Euclidean-open sets of tensors of rank strictly higher than the generic rank. All ranks appearing on open sets in the Euclidean topology are called typical ranks. The smallest typical rank is called the generic rank; this definition applies to both complex and real tensors. The generic rank of tensor spaces was initially studied in 1983 by Volker Strassen.
As an illustration of the above concepts, it is known that both 2 and 3 are typical ranks of formula_43 while the generic rank of formula_44 is 2. Practically, this means that a randomly sampled real tensor (from a continuous probability measure on the space of tensors) of size formula_45 will be a rank-1 tensor with probability zero, a rank-2 tensor with positive probability, and rank-3 with positive probability. On the other hand, a randomly sampled complex tensor of the same size will be a rank-1 tensor with probability zero, a rank-2 tensor with probability one, and a rank-3 tensor with probability zero. It is even known that the generic rank-3 real tensor in formula_43 will be of complex rank equal to 2.
The generic rank of tensor spaces depends on the distinction between balanced and unbalanced tensor spaces. A tensor space formula_38, where formula_48,
is called unbalanced whenever
and it is called balanced otherwise.
Unbalanced tensor spaces.
When the first factor is very large with respect to the other factors in the tensor product, then the tensor space essentially behaves as a matrix space. The generic rank of tensors living in an unbalanced tensor spaces is known to equal
almost everywhere. More precisely, the rank of every tensor in an unbalanced tensor space formula_51, where formula_52 is some indeterminate closed set in the Zariski topology, equals the above value.
Balanced tensor spaces.
The generic rank of tensors living in a balanced tensor space is expected to equal
almost everywhere for complex tensors and on a Euclidean-open set for real tensors, where
More precisely, the rank of every tensor in formula_55, where formula_52 is some indeterminate closed set in the Zariski topology, is expected to equal the above value. For real tensors, formula_57 is the least rank that is expected to occur on a set of positive Euclidean measure. The value formula_57 is often referred to as the expected generic rank of the tensor space formula_59 because it is only conjecturally correct. It is known that the true generic rank always satisfies
The Abo–Ottaviani–Peterson conjecture states that equality is expected, i.e., formula_61, with the following exceptional cases:
In each of these exceptional cases, the generic rank is known to be formula_65. Note that while the set of tensors of rank 3 in formula_66 is defective (13 and not the expected 14), the generic rank in that space is still the expected one, 4.
The AOP conjecture has been proved completely in a number of special cases. Lickteig showed already in 1985 that formula_67, provided that formula_68. In 2011, a major breakthrough was established by Catalisano, Geramita, and Gimigliano who proved that the expected dimension of the set of rank formula_69 tensors of format formula_70 is the expected one except for rank 3 tensors in the 4 factor case, yet the expected rank in that case is still 4. As a consequence, formula_71 for all binary tensors.
Maximum rank.
The maximum rank that can be admitted by any of the tensors in a tensor space is unknown in general; even a conjecture about this maximum rank is missing. Presently, the best general upper bound states that the maximum rank formula_72 of formula_38, where formula_48, satisfies
where formula_35 is the (least) "generic rank" of formula_38.
It is well-known that the foregoing inequality may be strict. For instance, the generic rank of tensors in formula_78 is two, so that the above bound yields formula_79, while it is known that the maximum rank equals 3.
Border rank.
A rank-formula_69 tensor formula_81 is called a border tensor if there exists a sequence of tensors of rank at most formula_82 whose limit is formula_81. If formula_18 is the least value for which such a convergent sequence exists, then it is called the border rank of formula_81. For order-2 tensors, i.e., matrices, rank and border rank "always" coincide, however, for tensors of order formula_86 they may differ. Border tensors were first studied in the context of fast "approximate" matrix multiplication algorithms by Bini, Lotti, and Romani in 1980.
A classic example of a border tensor is the rank-3 tensor
It can be approximated arbitrarily well by the following sequence of rank-2 tensors
as formula_89. Therefore, its border rank is 2, which is strictly less than its rank. When the two vectors are orthogonal, this example is also known as a W state.
Properties.
Identifiability.
It follows from the definition of a pure tensor that formula_90 if and only if there exist formula_91 such that formula_92 and formula_93 for all "m". For this reason, the parameters formula_94 of a rank-1 tensor formula_81 are called identifiable or essentially unique. A rank-formula_18 tensor formula_97 is called identifiable if every of its tensor rank decompositions is the sum of the same set of formula_18 distinct tensors formula_99 where the formula_100's are of rank 1. An identifiable rank-formula_18 thus has only one essentially unique decomposition formula_102and all formula_103 tensor rank decompositions of formula_81 can be obtained by permuting the order of the summands. Observe that in a tensor rank decomposition all the formula_100's are distinct, for otherwise the rank of formula_81 would be at most formula_107.
Generic identifiability.
Order-2 tensors in formula_108, i.e., matrices, are not identifiable for formula_109. This follows essentially from the observation formula_110where formula_111 is an invertible formula_112 matrix, formula_113 , formula_114, formula_115 and formula_116. It can be shown that for every formula_117, where formula_52 is a closed set in the Zariski topology, the decomposition on the right-hand side is a sum of a different set of rank-1 tensors than the decomposition on the left-hand side, entailing that order-2 tensors of rank formula_119 are generically not identifiable.
The situation changes completely for higher-order tensors in formula_120 with formula_121 and all formula_122. For simplicity in notation, assume without loss of generality that the factors are ordered such that formula_123. Let formula_124denote the set of tensors of rank bounded by formula_18. Then, the following statement was proved to be correct using a computer-assisted proof for all spaces of dimension formula_126, and it is conjectured to be valid in general:
There exists a closed set formula_127 in the Zariski topology such that "every tensor" formula_128"is identifiable" (formula_129 is called generically identifiable in this case), unless either one of the following exceptional cases holds: 
In these exceptional cases, the generic (and also minimum) number of "complex" decompositions is 
In summary, the generic tensor of order formula_149 and rank formula_150 that is not identifiability-unbalanced is expected to be identifiable (modulo the exceptional cases in small spaces).
Ill-posedness of the standard approximation problem.
The rank approximation problem asks for the rank-formula_18 decomposition closest (in the usual Euclidean topology) to some rank-formula_69 tensor formula_81, where formula_82. That is, one seeks to solve
where formula_156 is the Frobenius norm.
It was shown in a 2008 paper by de Silva and Lim that the above standard approximation problem may be "ill-posed". A solution to aforementioned problem may sometimes not exist because the set over which one optimizes is not closed. As such, a minimizer may not exist, even though an infimum would exist. In particular, it is known that certain so-called "border tensors" may be approximated arbitrarily well by a sequence of tensor of rank at most formula_18, even though the limit of the sequence converges to a tensor of rank strictly higher than formula_18. The rank-3 tensor
can be approximated arbitrarily well by the following sequence of rank-2 tensors
as formula_161. This example neatly illustrates the general principle that a sequence of rank-formula_18 tensors that converges to a tensor of strictly higher rank needs to admit at least two individual rank-1 terms whose norms become unbounded. Stated formally, whenever a sequence
has the property that formula_164 (in the Euclidean topology) as formula_165, then there should exist at least formula_166 such that
as formula_165. This phenomenon is often encountered when attempting to approximate a tensor using numerical optimization algorithms. It is sometimes called the problem of "diverging components". It was, in addition, shown that a random low-rank tensor over the reals may not admit a rank-2 approximation with positive probability, leading to the understanding that the ill-posedness problem is an important consideration when employing the tensor rank decomposition.
A common partial solution to the ill-posedness problem consists of imposing an additional inequality constraint that bounds the norm of the individual rank-1 terms by some constant. Other constraints that result in a closed set, and, thus, well-posed optimization problem, include imposing positivity or a bounded inner product strictly less than unity between the rank-1 terms appearing in the sought decomposition.
Calculating the CPD.
Alternating algorithms:
Direct algorithms:
General optimization algorithms:
General polynomial system solving algorithms:
Applications.
In machine learning, the CP-decomposition is the central ingredient in learning probabilistic latent variables models via the technique of moment-matching. For example, consider the multi-view model which is a probabilistic latent variable model. In this model, the generation of samples are posited as follows: there exists a hidden random variable that is not observed directly, given which, there are several conditionally independent random variables known as the different "views" of the hidden variable. For simplicity, assume there are three symmetrical views formula_169 of a formula_170-state categorical hidden variable formula_171. Then the empirical third moment of this latent variable model can be written as:
formula_172.
In applications such as topic modeling, this can be interpreted as the co-occurrence of words in a document. Then the eigenvalues of this empirical moment tensor can be interpreted as the probability of choosing a specific topic and each column of the factor matrix formula_173 corresponds to probabilities of words in the vocabulary in the corresponding topic.