Database Reference
In-Depth Information
n
,
the TT-SVD with
(
9.14
) computes a tensor T in the TT format with compression ranks t
k
such that:
Theorem 9.2 (Theorem 2.2 in [Os11])
For each tensor A
∈
R
t
X
d
1
k¼
1
ε
2
k
A T
k
F
k
,
where
ε
k
¼kE
k
k
F
of all unfoldings A
k
¼ R
k
+
E
k
as in step 4 of the TT algorithm.
From Theorem 9.2 the following corollary can de deduced [Os11].
n
and rank bounds t
k
,
the best approximation
to A in the Frobenius norm with TT-ranks bounded by t
k
(denoted by T*) always
exists, and the TT-approximation T computed by the TT-SVD algorithm is
quasi-optimal:
Corollary 9.1
Given a tensor A
∈
R
p
d
1
A T
k
A T
k
F
k
k
F
:
Thus from Theorem 9.2, it immediately follows that for a prescribed relative
accuracy
ε
of the TT-SVD algorithm, we just need to select
ε
d
1
δ ¼
p
kk
F
:
This is a very nice (and constructive!) result. Remember that the truncated
HOSVD is in general not the optimal Tucker decomposition, although it usually
shows good approximation properties. In contrast, the TT-SVD provides us with the
(quasi-) optimal TT decomposition.
The tensor-train decomposition also possesses many other advantages; see [Os11,
OT09]. Unlike the canonical decomposition, it has stable ranks. Basic tensor opera-
tions (Sect.
9.1.1
) can be efficiently implemented. Here, efficient recompression
procedures play an important role since many basic linear algebra operations with
TT-tensors (addition, matrix-by-vector product, etc.) yield increased ranks.
Recompression
(or
rounding
) describes the rank reduction if a tensor is already
given in TT format but with suboptimal ranks
t
k
(i.e., too large). Ivan Oseledets,
who is - along with Eugene Tyrtyshnikov - one of the pioneers in the TT area,
developed a general TT recompression algorithm with linear complexity in
d
and
n
.
Of course, the TT-SVD algorithm is not suited for large mode sizes, for the same
reason as the HOSVD: the unfolding matrices are usually too large. But, like in the
3D-Tucker case, other techniques can be used. In fact, recall that due to the com-
plexity bound (
d
2)
nt
2
+2
nt
, the TT format is linear in both
d
and
n
.Soprovided
the compression ranks are not too high, it can be efficiently used to approximate high-
dimensional problems of high mode sizes. The development of efficient algorithms
for the TT approximation is currently under way. Beside ALS, again the cross-
approximation technique [OT10] is very powerful. In order to determine optimal
compression ranks, the DMRG scheme looks promising [SO11].
