19 Adaptive Interpolation, TT-Decomposition and Sparse …
279
is uniquely constructed, where rows and columns corresponding to non-essential
values of singular numbers are discarded.
19.6 Tensor Train
For matrices (in the case of two variables), the question is well studied and developed:
there are many effective methods and algorithms for constructing decompositions.
In the case of more than two measurements, it is necessary to work with multidimensional arrays, i.e., tensors. The general idea of efficient representing of these
objects is based on the separation of variables. There are several approaches: canonical decomposition [10], Tucker decomposition [11], and TT-decomposition [5, 6]
(tensor train). There are no reliable algorithms for the canonical decomposition, and
the Tucker decomposition is difficult to apply for a large number of dimensions.
TT-decomposition has appeared relatively recently, and its distinctive feature is the
fact that it is not a subject to the curse of dimensionality.
Let A ∈ R
p 1 × p 2 ×···× p n be the given n-dimensional tensor. Its TT-decomposition
is written as follows:
ˆ
A(i 1 , i 2 , . . . , i n ) = G 1 (i 1 )G 2 (i 2 ) . . . G n (i n ),
where
G k ∈ R
p k ×r k−1 ×r k , i k = 1, p k , k = 1, n, r 0 = r n = 1.
This is the product of n − 2 three-dimensional and two two-dimensional tensors
(Fig. 19.4). To calculate the value of a particular element, the corresponding matrices
are multiplied.
The construction of TT-decomposition reduces to the usual matrix decompositions. We perform the transition from n dimensions to 2 using index grouping.
SVD-decomposition is calculated for the matrix. Rows and columns corresponding
to non-essential singular numbers are discarded. The resulting matrices turn back into
tensors of lower dimension. The algorithm is applied recursively for them. The idea of
TT-cross algorithm that allows one to build TT-decomposition without calculating all
Fig. 19.4 Illustration of TT-decomposition
279
is uniquely constructed, where rows and columns corresponding to non-essential
values of singular numbers are discarded.
19.6 Tensor Train
For matrices (in the case of two variables), the question is well studied and developed:
there are many effective methods and algorithms for constructing decompositions.
In the case of more than two measurements, it is necessary to work with multidimensional arrays, i.e., tensors. The general idea of efficient representing of these
objects is based on the separation of variables. There are several approaches: canonical decomposition [10], Tucker decomposition [11], and TT-decomposition [5, 6]
(tensor train). There are no reliable algorithms for the canonical decomposition, and
the Tucker decomposition is difficult to apply for a large number of dimensions.
TT-decomposition has appeared relatively recently, and its distinctive feature is the
fact that it is not a subject to the curse of dimensionality.
Let A ∈ R
p 1 × p 2 ×···× p n be the given n-dimensional tensor. Its TT-decomposition
is written as follows:
ˆ
A(i 1 , i 2 , . . . , i n ) = G 1 (i 1 )G 2 (i 2 ) . . . G n (i n ),
where
G k ∈ R
p k ×r k−1 ×r k , i k = 1, p k , k = 1, n, r 0 = r n = 1.
This is the product of n − 2 three-dimensional and two two-dimensional tensors
(Fig. 19.4). To calculate the value of a particular element, the corresponding matrices
are multiplied.
The construction of TT-decomposition reduces to the usual matrix decompositions. We perform the transition from n dimensions to 2 using index grouping.
SVD-decomposition is calculated for the matrix. Rows and columns corresponding
to non-essential singular numbers are discarded. The resulting matrices turn back into
tensors of lower dimension. The algorithm is applied recursively for them. The idea of
TT-cross algorithm that allows one to build TT-decomposition without calculating all
Fig. 19.4 Illustration of TT-decomposition