In multilinear algebra, 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 and chemometrics. 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). PARAFAC2 rank decomposition is yet to explore.

Tensor rank decomposition

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, signal processing, computer vision, computer graphics, psychometrics.

Tensor rank decomposition

Notation

A scalar variable is denoted by lower case italic letters, and an upper bound scalar is denoted by an upper case italic letter, .

Tensor rank decomposition

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 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, 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 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 : 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 . 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.