↑ arvau

Wikipedia / Tensor rank decomposition

In multilinear algebra, the tensor rank decomposition or rank-R decomposition is the decomposition of a tensor as a sum of R rank-1 tensors, where R is minimal. Computing this decomposition is an open problem.

Canonical polyadic decomposition (CPD) is a variant of the tensor rank decomposition, in which the tensor is approximated as a sum of K rank-1 tensors for a user-specified K. The CP decomposition has found some applications in linguistics and chemometrics. It 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). Note that the PARAFAC2 rank decomposition is a variation of the CP 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, and psychometrics.

Notation

.

.

.

.

Definition

is a collection of multivariate observations organized into a -way array where = rank-1 tensors:

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

.

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

. 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

.

In contrast, the rank of real matrices will never decrease under a field extension: real matrix rank and complex matrix rank coincide for real matrices.

Generic rank

The generic rank such that the closure in the Zariski topology 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 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.

will be of complex rank equal to 2.

, 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 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 for complex tensors and on a Euclidean-open set for real tensors, where

is some indeterminate closed set in the Zariski topology, is expected to equal the above value. is often referred to as the expected generic rank because it is only conjecturally correct. It is known that the true generic rank always satisfies

The Abo–Ottaviani–Peterson conjecture, with the following exceptional cases:

is defective (44 and not the expected 45), but the generic rank in that space is still the expected 6.

. for all binary tensors.

Maximum rank

The maximum rank, satisfies

is the (least) generic rank., while it is known that the maximum rank equals 3.

Border rank

is called a border tensor is the least value for which such a convergent sequence exists, then it is called the border rank. For order-2 tensors, i.e., matrices, rank and border rank always 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

. 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

for all m is called identifiable.

Generic identifiability

. It can be shown are generically not identifiable.

. Then, the following statement was proved to be correct using a computer-assisted proof, and it is conjectured to be valid in general:

in the Zariski topology such that every tensoris identifiable is called generically identifiable in this case), unless either one of the following exceptional cases holds:

  1. ;

  2. ;

  3. ;

  4. ;

  5. ;

  6. ; or

  7. .

  8. .

In these exceptional cases, the generic (and also minimum) number of complex decompositions is

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

that is not identifiability-unbalanced is expected to be identifiable (modulo the exceptional cases in small spaces).

Ill-posedness of the standard approximation problem

. That is, one seeks to solve

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. The rank-3 tensor

can be approximated arbitrarily well by the following sequence of rank-2 tensors

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

such that

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

  • pencil-based algorithms

  • moment-based algorithms

General optimization algorithms:

Eigenvalue algorithms:

Factorization Machines:

Bayesian factorizations/Sampling/Markov Chain Monte Carlo (MCMC):

Deep learning/Neural Networks (Gradient-based learning):

General polynomial system solving algorithms:

However, P Wiriyathammabhum and B Kijsirikul found that there are no optimal solving algorithms (all existing optimization methods cannot provide provably optimal solutions.) as they had created a score tensor and reranked the solutions using just a greedy stepwise selection which can give significantly better solutions, at least on nd-PCA, nd-FLD/LDA, and so on (CPD and Tucker variants). The hypothesis is fixing all the other n-1th parameters while optimizing the nth parameter is always (provably) suboptimal. MS Mahanta and KN Plataniotis proposed another spectral clustering solution which further provides better solutions.

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 applications such as topic modeling corresponds to probabilities of words in the vocabulary in the corresponding topic.

See also

References

Further reading