Loading [MathJax]/jax/output/HTML-CSS/jax.js
 
 

Tensor Decompositions


Tensors are multidimensional generalizations of vectors and matrices represented by arrays with n indices, i.e.,
TCD=Cd1××dn
is a tensor of order n, where D=(d1,,dn) is called mode set. In what follows, we will denote tensors by bold letters and refer to an element of a tensor T using subscript indices. The storage consumption of such a tensor can be estimated as O(dn) where d is the maximum of all modes. Thus, storing a higher-order tensor is in general infeasible for large n since the number of elements of a tensor grows exponentially with the order - this is also known as the curse of dimensionality. However, it is possible to mitigate this problem by exploiting low-rank tensor approximations in many cases.

 

 

The essential operation used for tensor decompositions is the so-called tensor product: Given a tensor T of order n and a tensor U of order m, the tensor product is defined by
(TU)x1,,xn,y1,,ym=Tx1,,xnUy1,,ym,
for any possible combination of mode indices.

 

 

In order to efficiently represent high-dimensional systems - e.g., probability distributions, transformed data tensors, or quantum states - we focus on tensor trains (TT) a.k.a. matrix product states (MPS). The TT/MPS format is a special case of the more general hierarchical Tucker format and turned out to be a promising candidate in terms of storage consumption as well as computational robustness. A tensor T is said to be in the MPS/TT format if
T=r0k0=1rnkn=1ni=1T(i)ki1,:,ki=r0k0=1rnkn=1T(1)k0,:,k1T(n)kn1,:,kn.
The variables ri are called  bond dimensions or TT ranks and it holds that r0=rn=1 and ri1 for i=1,,n1. The tensors T(i)Cri1×di×ri are called (TT) cores. Each element of the tensor T can be written as
Tx1,,xn=T(1)1,x1,:T(2):,x2,:T(n1):,xn1,:T(n):,xn,1,
which explains the origin of the name matrix product states (MPS). If the ranks are small enough, we may reduce the storage consumption of an order-n tensor significantly: Instead of an exponential dependence, the storage then depends only linearly on the order and can be estimated as O(r2dn), where r is the maximum over all ranks. That is, if the underlying correlation structure admits such a low-rank decomposition, an enormous reduction in complexity can be achieved.


A linear operator GCD×D in the MPO/TT format, can be written as
G=R0k0=1Rnkn=1ni=1G(i)ki1,:,:,ki=R0k0=1Rnkn=1G(1)k0,:,:,k1G(n)kn1,:,:,kn.
Here, the cores are tensors of order 4. Figure 1 (a) and (b) show the graphical representation of an MPS TCD and an MPO GCD×D with D=(d1,,d5), respectively.

 


(a)


(b)

Figure 1: Graphical representation of the MPS/MPO format:  A core is depicted by a circle with different arms indicating the modes of the tensor and the rank indices. (a) Tensor of order 5 as MPS with ranks r1,r2,r3,r4. The first and the last core are matrices, the other cores are tensors of order 3. (b) An MPO of order 10 with ranks R1,R2,R3,R4. The first and the last core are tensors of order 3, the other cores are tensors of order 4. 


Tensor trains have become a widely-studied concept, which found its way into various scientific fields such as quantum mechanics, dynamical systems, system identification, and machine learning.