Abstract
We review and introduce new representations of tensor train decompositions for large-scale vectors, matrices, or low-order tensors. We provide extended definitions of mathematical multilinear operations such as Kronecker, Hadamard, and contracted products, with their properties for tensor calculus. Then we introduce an effective low-rank tensor approximation technique called the tensor train (TT) format with a number of mathematical and graphical representations. We also provide a brief review of mathematical properties of the TT format as a low-rank approximation technique. With the aim of breaking the curse-of-dimensionality in large-scale numerical analysis, we describe basic operations on large-scale vectors and matrices in TT format. The suggested representations can be used for describing numerical methods based on the TT format for solving large-scale optimization problems such as the system of linear equations and eigenvalue problems.
Introduction
Multi-dimensional or multi-way data is prevalent nowadays, which can be represented by tensors. An N th-order tensor is a multi-way array of size I 1 × I 2 × · · · × I N , where the nth dimension or mode is of size I n . For example, a tensor can be induced by the discretization of a multivariate function [24] . Given a multivariate function f (x 1 , . . . , x N ) defined on a domain [0, 1] N , we can get a tensor with entries containing the function values at grid points. For another example, we can obtain tensors based on observed data [2, 22] . We can collect and integrate measurements from different modalities by neuroimaging technologies such as functional magnetic resonance imaging (fMRI) and electroencephalography (EEG): subjects, time, frequency, electrodes, task conditions, trials, and so on. Furthermore, high-order tensors can be created by a process called tensorization or quantization [23] , by which a large-scale vectors and matrices are reshaped into higher-order tensors.
Introduction
However, it is impossible to store a high-order tensor because the number of entries, I N when I = I 1 = I 2 = · · · = I N , grows exponentially as the order N increases. This is called the "curse-ofdimensionality". Even for I = 2, with N = 50 we obtain 2 50 ≈ 10 15 entries. Such a huge storage and computational costs required for high dimensional problems prohibit the use of standard numerical algorithms. To make high dimensional problems tractable, there were developed approximation methods including sparse grids [32, 1] and low-rank tensor approximations [14, 24, 13] . In this paper, we focus on the latter approach, where computational operations are performed on tensor formats, i.e., low-parametric representations of tensors.
Introduction
In this paper, we consider several tensor formats, especially the tensor train (TT) format, which is one of the simplest tensor networks developed with the aim of overcoming the curse-ofdimensionality. Extensive overviews of the modern low-rank tensor approximation techniques are presented in [24, 13] . The TT format is equivalent to the matrix product states (MPS) for open boundary conditions proposed in computational physics, and it has taken a key role in density matrix renormalization group (DMRG) methods for simulating quantum many-body systems [33, 31] . It was later re-discovered in numerical analysis community [28, 30, 18] . The TT-based numerical algorithms can accomplish algorithmic stability and adaptive determination of ranks by employing the singular value decomposition (SVD) [30] . Its scope of application is quickly expanding for addressing high-dimensional problems such as multi-dimensional integrals, stochastic and parametric PDEs, computational finance, and machine learning [13] . On the other hand, a comprehensive survey on traditional low-rank tensor approximation techniques for CP and Tucker formats is presented in [5, 22] .
Introduction
Despite the large interest in high-order tensors in TT format, mathematical representations of the TT tensors are usually limited to the representations based on scalar operations on matrices and vectors, which leads to complex and tedious index notation in the tensor calculus. For example, a TT tensor is defined by each entry represented as products of matrices [30, 18] . On the other hand, representations of traditional low-rank tensor formats have been developed based on multilinear operations such as the Kronecker product, Khatri-Rao product, Hadamard product, and mode-n multilinear product [2, 22] , which enables coordinate-free notation. Through the utilization of the multilinear operations, the traditional tensor formats expanded the area of application to chemometrics, signal processing, numerical linear algebra, computer vision, data mining, graph analysis, and neuroscience [22] .
Introduction
In this work, we develop extended definitions of multilinear operations on tensors. Based on the tensor operations, we provide a number of new and useful representations of the TT format. We also provide graphical representations of the TT format, motivated by [18] , which are helpful in understanding the underlying principles and TT-based numerical algorithms. Based on the TT representations of large-scale vectors and matrices, we show that the basic numerical operations such as the addition, contraction, matrix-vector product, and quadratic form are conveniently described by the suggested representations. We demonstrate the usefulness of the proposed tensor operations in tensor calculus by giving a proof of orthonormality of the so-called frame matrices. Moreover, we derive explicit representations of localized linear maps in TT format that have been implicitly presented in matrix forms in the literature in the context of alternating linear scheme (ALS) for solving various optimization problems. The suggested mathematical operations and TT representations can be further applied to describing TT-based numerical methods such as the solutions to large-scale systems of linear equations and eigenvalue problems [18] . This paper is organized as follows. In Section 2, we introduce notations for tensors and definitions for tensor operations. In Section 3, we provide the mathematical and graphical representations of the TT format. We also review mathematical properties the TT format as a low-rank approximation. In Section 4, we describe basic numerical operations on tensors in TT format such as the addition, Hadamard product, matrix-vector multiplication, and quadratic form in terms of the multilinear 
Introduction
scalar, vector, and matrix
Introduction
operations and TT representations. Discussion and conclusions are given in Section 5.
Notations for tensors and tensor operations
The notations in this paper follow the convention provided by [2, 22] . Table 1 summarizes the notations for tensors. Scalars, vectors, and matrices are denoted by lowercase, lowercase bold, and uppercase bold letters x, x, and X, respectively. Tensors are denoted by underlined uppercase bold letters X. The (i 1 , i 2 , . . . , i N )th entry of X of size
Notations for tensors and tensor operations
A subtensor of X obtained by fixing the indices i 3 , i 4 , . . . , i N is denoted by X :,:,i3,i4,...,i N or X(:, :, i 3 , i 4 , . . . , i N ). We may omit ':' as X i3,i4,...,i N if the rest of the indices are clear to readers. The mode-n matricization of X ∈ R I1×I2×···×I N is denoted by X (n) ∈ R In×I1I2···In−1In+1···I N . We denote the mode-(1, 2, . . . , n) matricization of X by X ([n]) ∈ R I1I2···In×In+1···I N in the sense that [n] ≡ {1, 2, . . . , n} is the set of integers from 1 to n. In addition, we define the multi-index notation by
Notations for tensors and tensor operations
. . , I n , n = 1, . . . , N . By using this notation, we can write an entry of a Kronecker product as (a ⊗ b) ij = a i b j . Moreover, it is important to note that in this paper the vectorization and matricization are defined in accordance with the multi-index notation. That is, for X ∈ R I1×I2×···×I N , we have
Notations for tensors and tensor operations
for n = 1, . . . , N . Table 2 summarizes the notations and definitions for tensor operations used in this paper.
Notations for tensors and tensor operations
3 Table 2 : Notations and definitions for tensor operations
Notations for tensors and tensor operations
Kronecker product of A ∈ R I1×···×I N and B ∈ R J1×···×J N yields a tensor C of size
Notations for tensors and tensor operations
mode-n Kronecker product of A ∈ R I1×···×In−1×J×In+1×···×I N and B ∈ R I1×···×In−1×K×In+1×···×I N yields a tensor C of size I 1 × · · · × I n−1 × JK × I n+1 × · · · × I N with mode-n fibers
Notations for tensors and tensor operations
mode-n Kronecker product of A ∈ R I1×···×I N and B ∈ R J1×···×J N with I n = J n yields a tensor C of size
Notations for tensors and tensor operations
Hadamard (elementwise) product of A ∈ R I1×···×I N and B ∈ R I1×···×I N yields a tensor C of size I 1 × · · · × I N with entries
Notations for tensors and tensor operations
mode-n direct sum of A ∈ R I1×···×I N and B ∈ R J1×···×J N with I n = J n yields a tensor C of size
Notations for tensors and tensor operations
with subtensors C(:, . . . , :, i n , :, . . . , :) = A(:, . . . , :, i n , :, . . . , :) ⊕ B(:, . . . , :, i n , :, . . . , :) C = A × n B mode-n product [22] of tensor A ∈ R I1×···×I N and matrix B ∈ R J×In yields a tensor C of size
Notations for tensors and tensor operations
mode-n (vector) product [22] of tensor A ∈ R I1×···×I N and vector b ∈ R In yields a tensor C of size
Notations for tensors and tensor operations
Tucker operator defined by (2)
Notations for tensors and tensor operations
and B = [B r2,r3 ] ∈ R R2J1×R3J2×J3 yields a block tensor
Notations for tensors and tensor operations
2.1 Kronecker, Hadamard, and outer products
Notations for tensors and tensor operations
Definitions for traditional matrix-matrix product operations such as the Kronecker, Hadamard, and outer products can be generalized to tensor-tensor products.
Notations for tensors and tensor operations
Definition 2.1 (Kronecker product). The Kronecker product of A ∈ R I1×I2×···×I N and B ∈ R J1×J2×···×J N is defined by
Notations for tensors and tensor operations
The mode-n Kronecker product of A ∈ R I1×···×In−1×J×In+1×···×I N and B ∈ R
Notations for tensors and tensor operations
with mode-n fibers
Notations for tensors and tensor operations
Similarly, the mode-n Kronecker product of A ∈ R I1×···×I N and B ∈ R J1×···×J N with common mode size I n = J n is defined by 
Notations for tensors and tensor operations
Note that an N th order tensor X ∈ R I1×I2×···×I N is rank-one if it is written as the outer product of N vectors
Notations for tensors and tensor operations
In general, N th order tensor X ∈ R I1×I2×···×I N can be represented as a sum of rank-one tensors, so called CP or PARAFAC [22] 
Notations for tensors and tensor operations
r .
5
The smallest number R of the rank-one tensors that produce X is called the tensor rank of X [22] . It is possible to define a tensor operation between rank-one tensors and generalize it to sums of rank-one tensors. For example, given two rank-one tensors
5
and Hadamard (elementwise) product of vectors a
5
• the Kronecker product A ⊗ B can be defined by
5
• the mode-n Kronecker product by
5
• the mode-n Kronecker product by
5
• the Hadamard product by
5
• and the outer product by
5
However, the problem of determining the tensor rank of a specific tensor is NP-hard if the order is larger than 2 [16] . So, for practical applications, we will define tensor operations by using index notation and provide examples with rank-one tensors.
Direct sum
The direct sum of matrices A and B is defined by
Direct sum
A generalization of the direct sum to tensors is defined as follows.
Definition 2.4 (Direct sum). The direct sum of tensors
with entries
Definition 2.4 (Direct sum). The direct sum of tensors
with mode-n fibers
Definition 2.4 (Direct sum). The direct sum of tensors
The mode-n direct sum of A ∈ R I1×I2×···×I N and B ∈ R J1×J2×···×J N with common mode size I n = J n is defined by
Definition 2.4 (Direct sum). The direct sum of tensors
with subtensors C(:, . . . , :, i n , :, . . . , :) = A(:, . . . , :, i n , :, . . . , :) ⊕ B(:, . . . , :, i n , :, . . . , :)
Definition 2.4 (Direct sum). The direct sum of tensors
In special cases, the direct sum of vectors a ∈ R I and b ∈ R J is the concatenation a ⊕ b ∈ R I+J , and the direct sum of matrices A ∈ R I1×I2 and B ∈ R J1×J2 is the block diagonal matrix
Definition 2.4 (Direct sum). The direct sum of tensors
. We suppose that the direct sum of scalars a, b ∈ R is the addition
Tucker operator and contracted product
The mode-n product, denoted by × n , is a multilinear operator between a tensor and a matrix [22] . Kolda and Bader [22] further introduced a multilinear operator called the Tucker operator [21] to simplify the expression for the mode-n product. The mode-n product of a tensor G ∈ R R1×R2×···×R N and a matrix A ∈ R In×Rn is defined by
Tucker operator and contracted product
or, in matrix,
Tucker operator and contracted product
The standard Tucker operator of a tensor G ∈ R R1×R2×···×R N and matrices A (n) ∈ R In×Rn , n = 1, . . . , N, is defined by
Tucker operator and contracted product
Here, we generalize this to a multilinear operator between tensors.
Tucker operator and contracted product
Definition 2.5 (Tucker operator). Let N ≥ 1 and M n ≥ 0 (n = 1, 2, . . . , N ). For an N th order tensor G ∈ R R1×R2×···×R N and (M n + 1)th order tensors A (n) ∈ R In,1×In,2×···×I n,Mn ×Rn , n = 1, . . . , N, the Tucker operator is a multilinear operator defined by the (
Tucker operator and contracted product
with entries
Tucker operator and contracted product
where i n = (i n,1 , i n,2 , . . . , i n,Mn ) is the ordered indices.
Tucker operator and contracted product
In a special case, we have the standard Tucker operator (1) if A (n) are matrices, i.e., M n = 1. Even in the case of vectors a (n) ∈ R Rn , i.e., M n = 0, we have the scalar
Tucker operator and contracted product
where × n is the mode-n (vector) product [22] .
Tucker operator and contracted product
be rank-one tensors. Then,
Tucker operator and contracted product
where v, w = v T w is the innerproduct of vectors. In general, we can derive the following properties. Proposition 2.6. Let N ≥ 1 and M n ≥ 0 (n = 1, 2, . . . , N ). Let G X and G Y be N th order tensors, A (n) and B (n) be (M n + 1)th order tensors, n = 1, 2, . . . , N , and
Tucker operator and contracted product
and
Tucker operator and contracted product
have the same sizes. Then
Tucker operator and contracted product
Example. We provide examples where A (n) and B (n) are either matrices or vectors.
Tucker operator and contracted product
• Let M n = 1 (n = 1, 2, . . . , N ), i.e., we have X and Y in Tucker format
Tucker operator and contracted product
It follows that the Kronecker product, Hadamard product, direct sum, and addition is also given in the Tucker format
Tucker operator and contracted product
In the case that X and Y are in CP format where the core tensors G X and G Y are superdiagonal, the results are also given in CP format because the Kronecker product and direct sum of the super-diagonal core tensors are super-diagonal tensors as well.
Tucker operator and contracted product
• Let M n = 0 (n = 1, 2, . . . , N ), then we have the scalars
Tucker operator and contracted product
The multiplication and addition are given in the form
Tucker operator and contracted product
As a special case, we introduce a tensor-tensor contracted product as follows.
Tucker operator and contracted product
We note that the tensor-tensor contracted product defined above is a natural generalization of the matrix multiplication as AB = A • B, and the vector innerproduct as a, b = a • b. Especially, the contracted products between a tensor A ∈ R I1×···×I M and vectors p ∈ R I1 and q ∈ R I M lead to tensors of smaller orders as
Tucker operator and contracted product
The contracted product of rank-one tensors yields
Tucker operator and contracted product
In general, we have the following properties:
Proof of (e). Note that
By inserting auxiliary variables k m+1 , . . . , k M ,
Proof of (e). Note that
We also have
Proof of (e). Note that
and
Proof of (e). Note that
Proposition 2.9. Let A (n) and B (n) be M n th order tensors, n = 1, 2, and let
Proof of (e). Note that
and
Proof of (e). Note that
have the same sizes. Then,
Self-contraction operator
We will define a linear operator, S, called the self-contraction, which generalizes the trace on matrices to tensors.
Self-contraction operator
Definition 2.10 (Self-contraction). The self-contraction, S :
Self-contraction operator
The self-contraction is a generalization of the matrix trace. For a matrix A ∈ R I×I ,
Self-contraction operator
A more formal definition is given by using the contracted product as
Self-contraction operator
where
Self-contraction operator
is the i 1 th standard basis vector. The self-contraction of a rank-one tensor is calculated by
Self-contraction operator
where v, w = v T w. For a tensor X ∈ R I1×I2×···×I N ×I1 , the (i 2 , i 3 , . . . , i N )th entry of S(X) equals to the matrix trace of the (i 2 , i 3 , . . . , i N )th slice as (S(X)) i2,i3,...,i N = tr(X(:, i 2 , i 3 , . . . , i N , :)).
In addition, let
A ∈ R I1×I2×···×I M +1 and B ∈ R I M +1 ×J2×J3×···×J N ×I1 . Then (S(A • B)) i2,...,i M ,j2,...,j N = (S(B • A)) j2,...,j N ,i2,...,i M . As a special case, if M = N = 2, then (S(A • B)) T = S(B • A).
Strong Kronecker product
The strong Kronecker product is an important tool in low-rank TT decompositions of large-scale tensors. We present the definitions of the strong Kronecker product [27] and its generalization to tensors.
Strong Kronecker product
Definition 2.11 (Strong Kronecker product). Let A and B be R 1 × R 2 and R 2 × R 3 block matrices
Strong Kronecker product
where A r1,r2 ∈ R I1×I2 and B r2,r3 ∈ R J1×J2 . The strong Kronecker product of A and B is defined by the R 1 × R 3 block matrix
Strong Kronecker product
where
Strong Kronecker product
for r 1 = 1, 2, . . . , R 1 and r 3 = 1, 2, . . . , R 3 . More generally, let
Strong Kronecker product
and B = B r2,r3 ∈ R
R2J1×R3J2×J3
be R 1 × R 2 and R 2 × R 3 block tensors where A r1,r2 ∈ R I1×I2×I3 and B r2,r3 ∈ R J1×J2×J3 are 3rd order tensors. Then the strong Kronecker product of A and B is defined by the R 1 × R 3 block tensor
R2J1×R3J2×J3
where
R2J1×R3J2×J3
for r 1 = 1, 2, . . . , R 1 and r 3 = 1, 2, . . . , R 3 .
R2J1×R3J2×J3
Example. The strong Kronecker product has a similarity with the matrix-matrix mutliplication. For example, 
Graphical representations of tensors
It is quite useful to represent tensors and related operations by graphs of nodes and edges, as was proposed in [18] . Figure 1(a) , (b), and (c) illustrate the graphs representing a vector, a matrix, and a 3rd order tensor. In each graph, the number of edges connected to a node indicates the order of the tensor, and the mode size can be shown by the label on each edge. In the TT format, a tensor X ∈ R I1×I2×···×I N is represented as
Graphical representations of tensors
where G (n) ∈ R Rn−1×In×Rn , n = 1, . . . , N, are 3rd order tensors called the TT-cores, R 1 , . . . , R N −1 are called the TT-ranks, and R 0 = R N = 1. Since R 0 = R N = 1, we consider that the contracted product (5) yields a tensor of order N even if each of the TT-cores are regarded as a 3rd order tensor for notational convenience. Figure 2 illustrates the graphical representation of a 4th order TT tensor.
Graphical representations of tensors
Alternatively, the TT format is often written entry-wise as
Graphical representations of tensors
1,i1,r1 g
Graphical representations of tensors
r1,i2,r2 · · · g
Graphical representations of tensors
where
Graphical representations of tensors
is the lateral slice of the nth TT-core. Note that G 
13
The TT format can also be represented as a sum of outer products. From (6), we have
13
where g (n)
13
rn−1,rn = G (n) (r n−1 , :, r n ) ∈ R In is the mode-2 fiber. A large-scale vector x of length I 1 I 2 · · · I N can be tensorized into X ∈ R I1×I2×···×I N and represented in TT format. By vectorizing the TT format (7), we get the TT format for x, represented as a sum of the Kronecker products
13
The above form can be compactly represented as the strong Kronecker products
13
where G (n) , n = 1, . . . , N, are the R n−1 × R n block matrices
13
with each block g (n)
13
rn−1,rn ∈ R In . Table 3 summarizes the alternative representations for the TT format.
13
In principle, any tensor X can be represented in TT format through the TT-SVD algorithm [30] .
The storage cost for a TT format is O(N IR
2 ) with I = max(I n ) and R = max(R n ). So the storage and computational complexities can be substantially reduced if the TT-ranks are kept small enough.
Recursive representations for TT format
The TT format can be expressed in a recursive manner, which is summarized in Table 4 . Given the TT-cores G (n) , n = 1, . . . , N, we define the partial contracted products G ≤n ∈ R I1×···×In×Rn and
Recursive representations for TT format
and
Recursive representations for TT format
G <n and G >n are defined in the same way. For completeness, we define G <1 = G >N = 1. The vectorizations of the partial contracted products yield the following recursive equations
Recursive representations for TT format
for n = 2, 3, . . . , N , and 
Recursive representations for TT format
Matrix products
Recursive representations for TT format
Outer products
Recursive representations for TT format
rn−1,rn ∈ R Rn−1In×Rn with each block g
Recursive representations for TT format
for n = 1, 2, . . . , N − 1. Hence, the vectorization of tensor X can be expressed as
Recursive representations for TT format
Proposition 3.1. We obtain the following formulas:
Recursive representations for TT format
and
Extraction of TT-cores
Using the concept of splitting tensor train to sub-tensor trains, we can obtain an another important expression of the vectorization, in which the nth core tensor is separated from the others as [6, 26] vec (X) = vec
Extraction of TT-cores
By defining the so-called frame matrix
Extraction of TT-cores
for n = 1, 2, . . . , N , we get
Extraction of TT-cores
Similarly, we can obtain an expression of the vectorization where two neighboring TT-cores are extracted as [26] vec
Extraction of TT-cores
where
Extraction of TT-cores
for n = 1, 2, . . . , N − 1. 
Extraction of TT-cores
with g
Extraction of TT-cores
Outer products
Orthogonalization of core tensors
Orthogonalization of the TT-cores reduces computational costs and guarantees uniqueness of TTranks.
Orthogonalization of core tensors
Definition 3.2 (Left-or right-orthogonality, [17] ). For n = 1, 2, . . . , N, the nth TT-core
Orthogonalization of core tensors
and
Orthogonalization of core tensors
On the other hand, all orthogonality was defined in the context of Tucker format [4] .
Definition 3.3 (All orthogonality, [4]). A 3rd order tensor
During iterations in numerical algorithms, the TT-cores are kept either left-or right-orthogonal by SVD or QR decomposition [30, 18] . For a fixed n, if all the cores on the left are left-orthogonal, then G <n (n) ∈ R Rn×I1I2···In−1 has orthonormal rows. And if all the cores on the right are rightorthogonal, then G >n (1) ∈ R Rn×In+1In+2···I N has orthonormal rows. Consequently, we can make the frame matrices X =n and X =n,n+1 defined in (15) and (18) have orthonormal columns during iterations. The proof of the orthonormality of G <n (n) and G >n (1) can be given by using the tensor operations described in the previous section as follows. Proof. We prove the orthonormality for G <n (n) . The orthonormality for G >n (1) follows in a similar way. The left-orthogonality (19) is re-written by the tensor operations as
Definition 3.3 (All orthogonality, [4]). A 3rd order tensor
where × n is the mode-n (vector) product of a tensor with a vector, and 1 I = [1, 1, . . . , 1] T ∈ R I is the vector of ones. We will show that
Definition 3.3 (All orthogonality, [4]). A 3rd order tensor
If n = 1, then G <n = 1 and the equality holds. If n = k > 1, we assume that the equality holds for n = 1, . . . , k − 1. From the recursive representation of the TT format, The mode-k Kronecker product of G <k with itself is
Definition 3.3 (All orthogonality, [4]). A 3rd order tensor
The lefthand side of (21) is equivalent to
Definition 3.3 (All orthogonality, [4]). A 3rd order tensor
Hence, we find that 
Properties of TT format
Mathematical properties of the TT format are closely related to the so-called separation ranks [17] . The nth separation rank, S n , of X is defined as the rank of the nth canonical unfolding X ([n]) , i.e.,
Properties of TT format
A tensor X of order N is said to be in the TT format with TT-ranks R 1 , . . . , R N −1 if it can be expressed in the TT format (5). The TT format (5) is called minimal or fulfilling the full-rank condition [17] if all TT-cores have full left and right ranks, i.e.,
Properties of TT format
, for all n = 1, . . . , N . By looking at the mode-n matricization of the TT format (5), we can show the following relationship between the separation ranks and the TT-ranks:
Properties of TT format
S n ≤ R n for n = 1, . . . , N − 1. In [30] , it is shown that for a tensor X, there exists a TT decomposition with TT-ranks not higher than the separation ranks, i.e.,
Properties of TT format
Moreover, Holtz et al. [17] proved the uniqueness of the TT-ranks of minimal TT decompositions for a tensor X. That is, if X admits for a minimal TT decomposition with TT-ranks R n , then it holds that R n = S n for n = 1, . . . , N − 1. Therefore, the TT-ranks of a tensor X is defined as the TT-ranks of a minimal TT decomposition of X. Let T TT (R 1 , . . . , R N −1 ) denote the set of tensors with TT-ranks bounded by {R n }. It has been shown that T TT (R 1 , . . . , R N −1 ) is closed [11, 14] , which implies that there exists a best TT-ranks-(R 1 , . . . , R N −1 ) approximation of any tensor. Oseledets [30] proved that the TT-SVD algorithm returns a quasi-optimal TT approximation. That is, for a tensor Y, the TT-SVD algorithm returns X ∈ T TT (R 1 , . . . , R N −1 ) such that
Properties of TT format
where · F is the Frobenius norm. Moreover, unlike the Tucker format, the TT format requires a storage cost of O(N IR 2 ), that is linear in N . Many algorithms based on the TT format such as the approximation, truncation, contraction, and solution to linear systems, also have computational complexity linear with N . Further mathematical properties of TT-based algorithms will be developed in the next section.
Matrix TT format for linear operators
The matrix product operator (MPO), or equivalently the matrix TT format is an extension of the TT format to linear operators and matrices [29] . Various representations, including new ones, for the matrix TT format are summarized in Table 5 . Suppose that a linear operator from R
Matrix TT format for linear operators
The matrix TT format for A can be represented as outer products 
Matrix TT format for linear operators
Matrix products a i1,j1,i2,j2,...,i N 
Matrix TT format for linear operators
Outer products
Matrix TT format for linear operators
In×Jn is a slice of the 4th order core tensor A (n) ∈ R Rn−1×In×Jn×Rn . Note that the matrices A rn−1,rn ∈ R In in the standard TT/MPS format.
Matrix TT format for linear operators
Moreover, the matrix TT format is a representation of a large-scale matrix. The matrix TT format for a matrix A of size I 1 I 2 · · · I N × J 1 J 2 · · · J N can be written as the strong Kronecker products
Matrix TT format for linear operators
where
Matrix TT format for linear operators
The strong Kronecker product representation is useful, especially for representing large-scale high dimensional operators such as the discrete Laplace operator and Toeplitz matrix [19, 20] . With these representations for the matrix TT format, the matrix-vector product and the quadratic form can be conveniently described. See Section 4.3 for such mathematical expressions. Figure 4 
Basic operations with TT format
For numerical operations with tensors in TT format, it is important to perform all the operations in TT format and avoid the explicit calculation of the full tensors. In this section we present basic operations with tensors in TT format, which are represented in simple and very efficient forms by the notations introduced in the previous sections. The basic operations include addition, scalar multiplication, contraction, Hadamard product, matrix-vector product, and quadratic form. We remark that such operations usually increase the TT-ranks, which requires truncation in the following step.
Basic operations with TT format
In addition, the matrix-vector product and quadratic form are very important for computational algorithms in optimization problems such as linear equations [7, 8, 9, 18] and eigenvalue problems [6, 25] . Table 6 summarizes the representations for the basic operations on the tensors in TT format.
Addition and scalar multiplication
That is, each TT-core of the sum is written as the direct sum of the TT-cores. Alternatively, each entry of Z can be represented as products of matrices
Addition and scalar multiplication
The TT-ranks for X + Y are the sums, {R
Addition and scalar multiplication
On the other hand, multiplication of X with a scalar c ∈ R can be obtained by simply multiplying one core, e.g., X
Addition and scalar multiplication
(1) , with c as cX (1) . This does not increase the TT-ranks. We note that that the set of tensors with TT-ranks bounded by {R n } is not convex, since a linear combination cX + (1 − c)Y generally increases the TT-ranks, which may exceed {R n }. 
Addition and scalar multiplication
Matrices (slices) Z
Addition and scalar multiplication
(1)
Hadamard product and contraction
The Hadamard (elementwise) product
Hadamard product and contraction
can be written in the TT format as
Hadamard product and contraction
That is, each TT-core is written as the mode-2 Kronecker product. As an alternative representation, each entry is written as products of matrices
Hadamard product and contraction
The TT-ranks for the Hadamard product are the multiplications, {R X n R Y n }. The contraction of two tensors A ∈ R I1×I2×···×I N and B ∈ R I1×I2×···×I N is defined by
Hadamard product and contraction
The contraction of a TT tensor
Hadamard product and contraction
The contraction of two TT tensors
Hadamard product and contraction
I1×···×I N can be calculated by combining the Hadamard product and the contraction with the rank one tensor
Hadamard product and contraction
where
Hadamard product and contraction
are row and column vectors.
Hadamard product and contraction
We define a generalized contraction operator of two TT-cores as follows.
Hadamard product and contraction
Definition 4.1 (Core contraction). The core contraction of two TT-cores
Hadamard product and contraction
Proposition 4.2. We can express the contraction of two TT-tensors
Hadamard product and contraction
The computational cost for calculating the contraction X, Y is O(N IR 3 ), which is linear in N .
Matrix-vector product
The matrix-vector product, or the linear mapping can also be efficiently represented by the TT format. The computational cost for computing a matrix-vector product in TT format is O(N I 2 R 4 ).
Matrix-vector product
1. Suppose that a vector x ∈ R J1J2···J N is in TT format and a matrix A ∈ R I1I2···I N ×J1J2···J N is in matrix TT format, and both are represented as Kronecker products
Matrix-vector product
Then the matrix-vector product is represented in TT format
Matrix-vector product
We can get the same expression in the case that X ∈ R J1×···×J N and A ∈ R I1×J1×···×I N ×J N are represented as outer products.
Matrix-vector product
2. The linear mapping A(X) ∈ R I1×I2×···×I N can also be represented by its entries written as products of matrices. Suppose that X ∈ R J1×···×J N and A ∈ R I1×J1×···×I N ×J N are in the TT formats
Matrix-vector product
and
Matrix-vector product
Then the entries of the linear mapping Z = A(X) is calculated by the contraction
Matrix-vector product
where the lateral slices Z (n)
Matrix-vector product
in of TT-cores Z (n) are expressed as
Matrix-vector product
Note that Z
Matrix-vector product
(1)
Matrix-vector product
are row and column vectors.
Matrix-vector product
3. We can further simplify the notation (25) by considering the TT-core
Matrix-vector product
as an operator. Let
Matrix-vector product
Rn−1R n−1 ×In×RnR n be a linear map defined by
Matrix-vector product
with each i n th slice
Matrix-vector product
We can represent A(X) in a simplified form as follows.
Matrix-vector product
On the other hand, we recall that
Matrix-vector product
where X =n is the frame matrix and x (n) = vec(X (n) ). A large-scale matrix-vector multiplication reduces to a smaller matrix-vector multiplication as Ax = AX =n x (n) ≡ A n x (n) , where
Matrix-vector product
But we cannot calculate A n by matrix-matrix multiplication for a large matrix A. However, by using the representation (26), we can show that A n can be calculated by recursive core contractions as follows.
Matrix-vector product
be a linear map defined by
Matrix-vector product
for any W (n) ∈ R R n−1 ×Jn×R n . Let A n be the matrix defined by (27) . Then
Matrix-vector product
for any W (n) ∈ R R n−1 ×Jn×R n . That is, the matrix-vector product A n w (n) , where w (n) = vec(W (n) ), can be computed efficiently via the recursive core contractions in A n (W (n) ). (28), where x (n) = vec(X (n) ) Figure 5 illustrates the graph for the linear map A n . For each k = 1, . . . , n − 1, n + 1, . . . , N, core tensor A (k) is connected to the core tensor X (k) , which is represented as A (k) (X (k) ) in (28).
Quadratic form
The quadratic form x, Ax for a symmetric and very large-scale matrix A ∈ R I1I2···I N ×I1I2···I N can be represented in TT format as follows. (n) r n−1 ,r n for r n , r n = 1, 2, . . . , R n and r n = 1, 2, . . . , R n for n = 1, 2, . . . , N . The outer product representation leads to the same expression.
Quadratic form
2. Recall that the nth core tensor of W = A(X) can be represented by the i n th slices W 
Quadratic form
We have Z 3. Instead, by using the core contraction defined in (23), we can simplify the expression (29) by
Quadratic form
where A (n) (X (n) ) ∈ R Rn−1R n−1 ×In×RnR n is defined in the previous subsection. Finally, we can express the quadratic form efficiently as X, A(X) = X represented by the bilinear form Φ A n (X (n) , X (n) ) (32) , where x (n) = vec(X (n) )
Discussion and conclusions
In this paper, we proposed several new mathematical operations on tensors and developed novel representations of the TT formats. We generalized the standard matrix-based operations such as the Kronecker product, Hadamard product, and direct sum, and proposed tensor-based operations such as the self-contraction and core contraction. We have shown that the tensor-based operations are able to not only simplify traditional index notation for TT representations but also describe important basic operations which are very useful for computational algorithms. The self-contraction operator can be used for defining the tensor chain (TC) [10] representations, and its properties should be more investigated in the future work. Moreover, the definition of core contraction can also be generalized to any tensor network formats such as hierarchical Tucker (HT) format [12, 15] . The partial contracted products of either the left or right core tensors are matricized and used as a building block of the frame matrices. We have shown that the suggested tensor operations can be used to prove the orthonormality of the frame matrices, which have been proved only by using index notation in the literature. The developed relationships may also play a key role in the alternating linear scheme (ALS) and modified alternating linear scheme (MALS) algorithms [18] for reducing the large-scale optimizations to iterative smaller scale problems. Recent studies adjust the frame matrices in order to incorporate rank adaptivity and improve convergence for the ALS [8, 9, 26] . In this work, we have derived the explicit representations of the localized linear map A n and bilinear form Φ A n by the proposed tensor operations, which are important for TTbased iterative algorithms for breaking the curse-of-dimensionality [3] . The global convergence of the iterative methods remains as a future work. In addition, it is important to keep the TT-ranks moderate for a feasible computational cost.

{'paper_id': '14934668', 'title': 'Fundamental Tensor Operations for Large-Scale Data Analysis in Tensor Train Formats', 's2_url': 'https://api.semanticscholar.org/CorpusID:14934668', 'source': 'S2ORC'}