In
multilinear algebra
Multilinear algebra is a subfield of mathematics that extends the methods of linear algebra. Just as linear algebra is built on the concept of a vector and develops the theory of vector spaces, multilinear algebra builds on the concepts of ''p' ...
, the tensor rank decomposition or the
decomposition of a tensor is the decomposition of a tensor in terms of a sum of minimum
tensors. This is an open problem.
Canonical polyadic decomposition (CPD) is a variant of the rank decomposition which computes the best fitting
terms for a user specified
. The CP decomposition has found some applications in
linguistics
Linguistics is the science, scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure ...
and
chemometrics
Chemometrics is the science of extracting information from chemical systems by data-driven means. Chemometrics is inherently interdisciplinary, using methods frequently employed in core data-analytic disciplines such as multivariate statistics, a ...
. The CP rank was introduced by
Frank Lauren Hitchcock in 1927 and later rediscovered several times, notably in psychometrics.
The CP decomposition is referred to as CANDECOMP,
PARAFAC,
or CANDECOMP/PARAFAC (CP).
Another popular generalization of the matrix SVD known as the
higher-order singular value decomposition computes orthonormal mode matrices and has found applications in
econometrics
Econometrics is the application of statistical methods to economic data in order to give empirical content to economic relationships. M. Hashem Pesaran (1987). "Econometrics," '' The New Palgrave: A Dictionary of Economics'', v. 2, p. 8 p. 8 ...
,
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
,
computer vision,
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
,
psychometrics
Psychometrics is a field of study within psychology concerned with the theory and technique of measurement. Psychometrics generally refers to specialized fields within psychology and education devoted to testing, measurement, assessment, and ...
.
Notation
A scalar variable is denoted by lower case italic letters,
and an upper bound scalar is denoted by an upper case italic letter,
.
Indices are denoted by a combination of lowercase and upper case italic letters,
. Multiple indices that one might encounter when referring to the multiple modes of a tensor are conveniently denoted by
where
.
A vector is denoted by a lower case bold Times Roman,
and a matrix is denoted by bold upper case letters
.
A higher order tensor is denoted by calligraphic letters,
. An element of an
-order tensor
is denoted by
or
.
Definition
A data tensor
is a collection of multivariate observations organized into a -way array where =+1. Every tensor may be represented with a suitably large
as a linear combination of
rank-1 tensors:
:
where
and
where
. When the number of terms
is minimal in the above expression, then
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)''. If the number of terms is not minimal, then the above decomposition is often referred to as ''CANDECOMP/PARAFAC'', ''Polyadic decomposition'.
Tensor rank
Contrary to the case of matrices, computing the rank of a tensor is
NP-hard. The only notable well-understood case consists of tensors in
, whose rank can be obtained from the
Kronecker–
Weierstrass
Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the "father of modern analysis". Despite leaving university without a degree, he studied mathematics ...
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
is one, provided that
.
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
. 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
In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, (if a and b are real, then) the complex conjugate of a + bi is equal to a - ...
, namely
:
where
.
In contrast, the rank of real matrices will never decrease under a
field extension to
: real matrix rank and complex matrix rank coincide for real matrices.
Generic rank
The generic rank
is defined as the least rank
such that the closure in the
Zariski topology
In algebraic geometry and commutative algebra, the Zariski topology is a topology which is primarily defined by its closed sets. It is very different from topologies which are commonly used in the real or complex analysis; in particular, it is n ...
of the set of tensors of rank at most
is the entire space
. In the case of complex tensors, tensors of rank at most
form a
dense set
In topology and related areas of mathematics, a subset ''A'' of a topological space ''X'' is said to be dense in ''X'' if every point of ''X'' either belongs to ''A'' or else is arbitrarily "close" to a member of ''A'' — for instance, the ra ...
: every tensor in the aforementioned space is either of rank less than the generic rank, or it is the limit in the
Euclidean topology
In mathematics, and especially general topology, the Euclidean topology is the natural topology induced on n-dimensional Euclidean space \R^n by the Euclidean metric.
Definition
The Euclidean norm on \R^n is the non-negative function \, \cdot\, ...
of a sequence of tensors from
. In the case of real tensors, the set of tensors of rank at most
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
Volker Strassen (born April 29, 1936) is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of Konstanz.
For important contributions to the analysis of algorithms he has received many aw ...
.
As an illustration of the above concepts, it is known that both 2 and 3 are typical ranks of
while the generic rank of
is 2. Practically, this means that a randomly sampled real tensor (from a continuous probability measure on the space of tensors) of size
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
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
, where
,
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
In measure theory (a branch of mathematical analysis), a property holds almost everywhere if, in a technical sense, the set for which the property holds takes up nearly all possibilities. The notion of "almost everywhere" is a companion notion to ...
. More precisely, the rank of every tensor in an unbalanced tensor space
, where
is some indeterminate closed set in the Zariski topology, equals the above value.
Balanced tensor spaces
The expected generic rank of tensors living in a balanced tensor space is equal to
:
almost everywhere
In measure theory (a branch of mathematical analysis), a property holds almost everywhere if, in a technical sense, the set for which the property holds takes up nearly all possibilities. The notion of "almost everywhere" is a companion notion to ...
for complex tensors and on a Euclidean-open set for real tensors, where
:
More precisely, the rank of every tensor in
, where
is some indeterminate closed set in the
Zariski topology
In algebraic geometry and commutative algebra, the Zariski topology is a topology which is primarily defined by its closed sets. It is very different from topologies which are commonly used in the real or complex analysis; in particular, it is n ...
, is expected to equal the above value.
For real tensors,
is the least rank that is expected to occur on a set of positive Euclidean measure. The value
is often referred to as the expected generic rank of the tensor space
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.,
, with the following exceptional cases:
*
*
In each of these exceptional cases, the generic rank is known to be
. Note that while the set of tensors of rank 3 in
is defective (13 and not the expected 14), the generic rank in that space is still the expected one, 4. Similarly, the set of tensors of rank 5 in
is defective (44 and not the expected 45), but the generic rank in that space is still the expected 6.
The AOP conjecture has been proved completely in a number of special cases. Lickteig showed already in 1985 that
, provided that
. In 2011, a major breakthrough was established by Catalisano, Geramita, and Gimigliano who proved that the expected dimension of the set of rank
tensors of format
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,
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
of
, where
, satisfies
:
where
is the (least) ''generic rank'' of
.
It is well-known that the foregoing inequality may be strict. For instance, the generic rank of tensors in
is two, so that the above bound yields
, while it is known that the maximum rank equals 3.
Border rank
A rank-
tensor
is called a border tensor if there exists a sequence of tensors of rank at most
whose limit is
. If
is the least value for which such a convergent sequence exists, then it is called the border rank of
. For order-2 tensors, i.e., matrices, rank and border rank ''always'' coincide, however, for tensors of order
they may differ. Border tensors were first studied in the context of fast ''approximate''
matrix multiplication algorithm
Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in m ...
s 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
. 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
if and only if there exist
such that
and
for all ''m''. For this reason, the parameters
of a rank-1 tensor
are called identifiable or essentially unique. A rank-
tensor
is called identifiable if every of its tensor rank decompositions is the sum of the same set of
distinct tensors
where the
's are of rank 1. An identifiable rank-
thus has only one essentially unique decomposition
and all
tensor rank decompositions of
can be obtained by permuting the order of the summands. Observe that in a tensor rank decomposition all the
's are distinct, for otherwise the rank of
would be at most
.
Generic identifiability
Order-2 tensors in
, i.e., matrices, are not identifiable for
. This follows essentially from the observation
where
is an invertible
matrix,
,
,
and
. It can be shown that for every
, where
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
are generically not identifiable.
The situation changes completely for higher-order tensors in
with
and all
. For simplicity in notation, assume without loss of generality that the factors are ordered such that
. Let
denote the set of tensors of rank bounded by
. Then, the following statement was proved to be correct using a
computer-assisted proof
A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.
Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a ...
for all spaces of dimension
,
and it is conjectured to be valid in general:
There exists a closed set
in the Zariski topology such that ''every tensor''
''is identifiable'' (
is called generically identifiable in this case), unless either one of the following exceptional cases holds:
# The rank is too large:
;
# The space is identifiability-unbalanced, i.e.,
, and the rank is too large:
;
# The space is the defective case
and the rank is
;
# The space is the defective case
, where
, and the rank is
;
# The space is
and the rank is
;
# The space is
and the rank is
; or
# The space is
and the rank is
.
# The space is perfect, i.e.,
is an integer, and the rank is
.
In these exceptional cases, the generic (and also minimum) number of ''complex'' decompositions is
* proved to be
in the first 4 cases;
* proved to be two in case 5;
* expected
to be six in case 6;
* proved to be two in case 7; and
* expected
to be at least two in case 8 with exception of the two identifiable cases
and
.
In summary, the generic tensor of order
and rank
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-
decomposition closest (in the usual Euclidean topology) to some rank-
tensor
, where
. That is, one seeks to solve
:
where
is the
Frobenius norm
In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices (of given dimensions).
Preliminaries
Given a field K of either real or complex numbers, let K^ be the -vector space of matrices with m ro ...
.
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
, even though the limit of the sequence converges to a tensor of rank strictly higher than
. The rank-3 tensor
:
can be approximated arbitrarily well by the following sequence of rank-2 tensors
:
as
. This example neatly illustrates the general principle that a sequence of rank-
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
(in the Euclidean topology) as
, then there should exist at least
such that
:
as
. 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
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often ...
strictly less than unity between the rank-1 terms appearing in the sought decomposition.
Calculating the CPD
Alternating algorithms:
*
alternating least squares
Alternating may refer to:
Mathematics
* Alternating algebra, an algebra in which odd-grade elements square to zero
* Alternating form, a function formula in algebra
* Alternating group, the group of even permutations of a finite set
* Alternati ...
(ALS)
*
alternating slice-wise diagonalisation (ASD)
Direct algorithms:
* pencil-based algorithms
*moment-based algorithms
General optimization algorithms:
*
simultaneous diagonalization (SD)
*
simultaneous generalized Schur decomposition
Simultaneity may refer to:
* Relativity of simultaneity, a concept in special relativity.
* Simultaneity (music), more than one complete musical texture occurring at the same time, rather than in succession
* Simultaneity, a concept in Endogeneit ...
(SGSD)
*
Levenberg–Marquardt (LM)
*
nonlinear conjugate gradient (NCG)
*
limited memory BFGS (L-BFGS)
General polynomial system solving algorithms:
*
homotopy continuation
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
In probability theory, conditional independence describes situations wherein an observation is irrelevant or redundant when evaluating the certainty of a hypothesis. Conditional independence is usually formulated in terms of conditional probabi ...
random variables known as the different "views" of the hidden variable. For simplicity, assume there are three symmetrical views
of a
-state categorical hidden variable
. Then the empirical third moment of this latent variable model can be written as:
.
In applications such as
topic modeling
In statistics and natural language processing, a topic model is a type of statistical model for discovering the abstract "topics" that occur in a collection of documents. Topic modeling is a frequently used text-mining tool for discovery of hidden ...
, 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