Completion of High Order Tensor Data with
Missing Entries via Tensor-train Decomposition
Longhao Yuan1,2 , Qibin Zhao2,3 , and Jianting Cao1

arXiv:1709.02641v2 [cs.NA] 14 Sep 2017

1

Graduate School of Engineering, Saitama Institute of Technology, Japan
2
Tensor Learning Unit, RIKEN Center
for Advanced Intelligence Project (AIP), Japan
3
School of Automation, Guangdong University of Technology, China
{longhao.yuan,qibin.zhao}@riken.jp,cao@sit.ac.jp

Abstract. In this paper, we aim at the completion problem of high order
tensor data with missing entries. The existing tensor factorization and
completion methods suffer from the curse of dimensionality when the order of tensor N >> 3. To overcome this problem, we propose an efficient
algorithm called TT-WOPT (Tensor-train Weighted OPTimization) to
find the latent core tensors of tensor data and recover the missing entries.
Tensor-train decomposition, which has the powerful representation ability with linear scalability to tensor order, is employed in our algorithm.
The experimental results on synthetic data and natural image completion demonstrate that our method significantly outperforms the other
related methods. Especially when the missing rate of data is very high,
e.g., 85% to 99%, our algorithm can achieve much better performance
than other state-of-the-art algorithms.
Keywords: tensor-train, tensor decomposition, missing data completion, optimization

1

Introduction

Tensor is a high order generalization of vectors and matrices, which is suitable
for natural data with the characteristic of multi-dimensionality. For example, a
RGB image can be represented as a three-way tensor: height × width × channel
and a video sequence can be represented by a height × width × channel × time
form data. When the original data is transformed into matrix or vector forms,
the structure information and adjacent relation of data will be lost. Tensor is the
natural representation of data that can retain the high dimensional structure of
data. In recent decades, tensor methodologies have attracted a lot of interests
and have been applied to various fields such as image and video completion [1,2],
signal processing [3,4], brain computer interface [5], image classification [6,7] ,
etc. Many theories, algorithms and applications of tensor methods have been
proposed and studied, which can be referred in the comprehensive review [8].
Most tensor decomposition methods assume that the tensor has no missing
entries and is complete. However, in practical situations, we may encounter some

2

Longhao Yuan, Qibin Zhao and Jianting Cao

transmission or device problems which result in that the collected data has missing and unknown entries. To solve this problem, the study on high order tensor
decomposition/factorization with missing entries becomes significant and has a
promising application aspect. The goal of tensor decomposition of missing data
is to find the latent factors of the observed tensor, which can thus be used to
reasonably predict the missing entries. The two most popular tensor decomposition methods in recent years are CANDECOMP/PARAFAC(CP) decomposition
[9,10] and Tucker decomposition [11]. There are many proposed methods that
use CP decomposition to complete data with missing entries. CP weighted optimization (CP-WOPT) [1] applies optimization method to finding the optimal
CP factor matrices from the observed data. Bayesian CP factorization [2] exploits Bayesian probabilistic model to automatically determine the rank of CP
tensor while finding the best factor matrices. The method in [12] recovers lown-rank tensor data with its convex relaxation by alternating direction method
of multipliers (ADM).
However, because of the peculiarity of CP and Tucker model, they can only
reach a relatively high accuracy in low-dimension tensors. When it comes to
a very high dimension, the performance of applying these models to missing
data completion will decrease rapidly. As mentioned above, many natural data’s
original form is high dimension tensor, so the models which are not sensitive
to dimensionality should be applied to perform the tensor decomposition. In
this paper, we use tensor-train decomposition [13] which is free from the curse
of high dimension to perform tensor data completion. Our works in this paper are as follows: (a) We develop a optimization algorithm named tensor-train
weighted optimization (TT-WOPT) to find the factor core tensors of tensortrain decomposition. (b) By TT-WOPT algorithm, tensor-train decomposition
model is applied to incomplete tensor data. Then the factor core tensors are
calculated and used to predict the missing entries of the original data. (c) We
conduct simulation experiments to verify the accuracy of our algorithm and
compare it to other algorithms. In addition, we carry out several real world experiments by applying our algorithm and other state-of-the-art algorithms to a
set of 256 × 256 × 3 images with missing entries. The experiment results show
that our method performs better in image inpainting than other state-of-the-art
approaches. In addition, by converting the image of size 256 × 256 × 3 to a much
higher dimension, our algorithm can successfully recover images with 99% missing entries while other existing algorithms fail at this missing rate. These results
demonstrate that tensor-train decomposition with high order tensorizations can
achieve high compressive and representation abilities.

2
2.1

Notations and Tensor-train Decomposition
Notations

In this paper, vectors are denoted by boldface lowercase letters, e.g., x. Matrices
are denoted by boldface capital letters, e.g., X. Tensors of order N ≥ 3 are denoted by Euler script letters, e.g., X . X(n) denotes the nth matrix of a matrix

Completion of High Order Tensor Data with Missing Entries

3

sequence and the representation of vector and tensor sequence is denoted by the
same way. When the tensor X is in the space of X ∈ RI1 ×I2 ×···×IN , X(n) denotes
the n-mode matricization of X , see [8]. The (i1 , i2 , · · · , iN )th element of X is
denoted by xi1 i2 ···iN or X (i1 , i2 , · · · , iN ).

2.2

Tensor-train Decomposition

The most important feature of tensor-train decomposition is that no matter how
high the dimension of a tensor is, it decomposes the tensor into a sequence of
three-way tensors. This is a great advantage in modeling high dimension tensor
because the number of model parameters will not grow exponentially by the
increase of the tensor dimension. For example, the number of parameters in
Tucker model is O(N IR + RN ) where N is the number of dimension, R is the
size of Tucker core tensor and I is the size of each dimension of the tensor. For
tensor-train decomposition, the number of parameters is O(N Ir2 ) where r is
rank of TT-tensor. Therefore, TT-model needs much fewer model parameters
than Tucker model.
Tensor-train decomposition is to decompose a tensor into a sequence of tensor
cores. All the tensor cores are three-way tensors. In particular, the TT decomposition of a tensor X ∈ RI1 ×I2 ×···×IN is expressed as follow:
X = G (1) , G (2) , · · · , G (N ) ,

(1)

where G (1) , G (2) , · · · , G (N ) is a sequence of three-way tensor cores with size of
1 × I1 × r1 , r1 × I2 × r2 , · · · , rN −1 × IN × 1. The sequence {1, r1 , r2 , · · · , rN −1 , 1}
is named TT-ranks which can limit the size of every core tensor. Each element
of tensor X can be written as the following index form:
(1)

(2)

(N )

xi1 i2 ···iN = Gi1 × Gi2 × · · · × GiN ,
(n)

(2)

where Gin is the in th slice of the nth core tensor. See the concept of slice in [8].
Currently, there is few study about how to compute TT-ranks efficiently. In
paper [13] where tensor-train decomposition is proposed, the author advances an
algorithm named TT-SVD to calculate the core tensors and TT-ranks. Although
it has the advantage of high accuracy and high efficiency, the TT-ranks in the
middle core tensors must be very high to compensate the low TT-ranks in the
border core tensors, which leads to the unreasonable distribution of TT-ranks
and redundant model parameters. Therefore, the TT-ranks calculated by TTSVD may not be the optimal one. In this paper, we manually set the TT-ranks
to a smooth distribution and use TT-WOPT algorithm to calculate the core
tensors. Though we do not have a good TT-rank choosing strategy, much fewer
model parameters are needed. The simulation results and experiment results also
show high accuracy and performance.

4

3

Longhao Yuan, Qibin Zhao and Jianting Cao

TT-WOPT Algorithm

Most of the tensor decomposition methods, which are used for finding the latent
factors, only aim at the fully observed data. When data has missing entries, we
cannot use these methods to predict the missing entries. Weighted optimization
method minimizes the distance between weighted real data and weighted optimization objective. When the optimization is finished, it means the obtained
tensor decomposition factors can match the observed real data well, then the
decomposition factors can be converted to original data structure to predict the
missing entries.
In our algorithm, TT-WOPT is applied to real-valued tensor X ∈ RI1 ×I2 ×···×IN
with missing entries. The index of missing entries can be recorded by a weight
tensor W which is the same size as X . Every entry of W meets:
(
0
if xi1 i2 ···iN is missing entry,
wi1 i2 ···iN =
(3)
1
if xi1 i2 ···iN is observed entry.
In the optimization algorithm, the objective variables are the elements of all
the core tensors. Define Y = W ∗ X and Z = W∗  G (1) , G (2) , · · · , G (N ) 
(∗ is the Hadamard product, see [8]), then the objective function can be written
as:
1
2
(4)
f (G (1) , G (2) , · · · , G (N ) ) = k(Y − Z)k .
2
The relation between original tensor and core tensors can be deduced as the
following equation [14]:
(n)

<n
X(n) = G(2) (G>n
(1) ⊗ G(n) ),

(5)

G>n = G (n+1) , G (n+2) , · · · , G (N ) ∈ RRn ×In+1 ×···×IN ,

(6)

G<n = G (1) , G (2) , · · · , G (n−1) ∈ RI1 ×···×In−1 ×Rn−1 ,

(7)

where for n = 1, ..., N ,

where G>N = G<1 = E and ⊗ is the symbol of Kronecker products, also see
[8].
For n = 1, ..., N , the partial derivatives of the objective function w.r.t. the
nth core tensor G (n) can be inferred as follow:
∂f
(n)
∂G(2)

<n T
= (Z(n) − Y(n) )(G>n
(1) ⊗ G(n) ) .

(8)

After the objective function and the derivation of gradient are obtained, we
can solve the optimization problem by any optimization algorithms based on
gradient descent method [15]. The optimization procedure of the algorithm is
listed in Alg.1.

Completion of High Order Tensor Data with Missing Entries

5

Algorithm 1 Tensor-train Weighted Optimization (TT-WOPT)
Input: an N -way incomplete tensor X and a weight tensor W.
Initialization: core tensors G (1) , G (2) , · · · , G (N ) of tensor X .
1. Compute Y = W ∗ X .
For each optimization iteration,
2. Compute Z = W∗  G (1) , G (2) , · · · , G (N ) .
3. Compute objective function: f = 21 kYk2 − < Y, Z > + 12 kZk.
<n T
4. Compute all ∂f(n) = (Z(n) − Y(n) )(G>n
(1) ⊗ G(n) ) .
∂G(2)

5. Use optimization algorithm to update G (1) , G (2) , · · · , G (N ) .
Until reach optimization stopping condition.
Return core tensors G (1) , G (2) , · · · , G (N ) .

4

Experiments

In [1] where the CP-WOPT method is proposed, only three-way data is tested.
When it comes to high dimension data, the performance of CP-WOPT will
fall. This is not because of the optimization method but the nature limit of
CP decomposition. In our paper, we test our TT-WOPT on different orders of
synthetic data. Then we test our algorithm on real world image data. We also
compare the performance of TT-WOPT with several state-of-the-art methods.
W is created by randomly setting some percentage of entries to zero while the
rest elements remain one.
4.1

Simulation Data

We consider to use synthetic data to validate the effectiveness of our algorithm.
Till now, there is few relevant study about applying tensor-train decomposition
to data completion, so we compare our algorithm to two other state-of-the-art
methods–CP weighted optimization (CP-WOPT) [1] and Fully Bayesian CP
Factorization (FBCP) [2]. We randomly initialize the factor matrices of a tensor with a specified CP rank, then we create the synthetic data by the factor
matrices. For data
evaluation index, we use relative square error (RSE) which is
r
2
defined as RSE = X − X̂ / kX k2 where X̂ is the tensor of full entries generated
by core tensors or factor matrices. T able 1. shows the simulation results of a
three-way tensor and a seven-way tensor. The tensor sizes of synthetic data are
30 × 30 × 30 and 4 × 4 × 4 × 4 × 4 × 4 × 4, and the CP ranks are set to 10 in
both cases.
Though we test the three algorithms on the data generated by CP model,
our TT-WOPT algorithm shows good results. As we can see from Table 1., when
we test on three-way tensor, TT-WOPT shows better fitting performance than
CP-WOPT and FBCP at low data missing rates but a little weak at high missing
rates. However, when we test on seven-way tensor, TT-WOPT outperforms the
other two algorithms. In addition, we also find that the performance of TTWOPT is sensitive to the setting of TT-ranks, different TT-ranks will lead to

6

Longhao Yuan, Qibin Zhao and Jianting Cao

very different model accuracies. It should be noted that till now there is no good
strategy to set TT-ranks and so in our experiments we set all TT-ranks the same
value. This is an aspect that our algorithm needs to improve. Furthermore, the
initial values of core tensors also influence the performance of TT-WOPT.

Table 1. Comparison of RSE of three different algorithms for two different data sizes
with different missing rates of synthetic data. The algorithms are TT-WOPT, CPWOPT, FBCP. The tensor ranks of each algorithm are set by experience (FBCP sets
CP ranks automatically). The two data sizes are: 30×30×30 and 4×4×4×4×4×4×4.
The three different missing rates are: 0%, 50% and 95%.
three-way tensor
seven-way tensor
missing rate
0%
50%
95%
0%
50%
95%
TT-ranks
{1,20,20,1} {1,20,20,1} {1,20,20,1} {1,20,...,20,1} {1,20,...,20,1} {1,8,...,8,1}
TT-WOPT
RSE
2.64e-08 6.64e-05
1.06
7.22e-03
4.71e-03
0.744
CP rank(manual)
10
10
10
10
10
10
CP-WOPT
RSE
5.34e-07
0.956
0.948
0.764
0.957
0.916
CP rank(auto)
10
11
6
3
7
4
FBCP
RSE
0.0581
0.0863
0.696
0.542
0.211
0.672

4.2

Image Data

In this section, we compare our algorithm with CP-WOPT and FBCP on image
completion experiments. The size of every image data is 256 × 256 × 3. We use
a set of images with missing rate from 85% to 99% to compare the performance
of every algorithm. In this experiment, we do not set tensor ranks and tensor
orders identically but use the best ranks to see the best possible result of every
algorithm. For TT-WOPT, we first reshape original data to a seventeen-way
tensor of size 2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×3 and permute the
tensor according to the order of {1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16 17}. Then
we reshape the tensor to a nine-way tensor of size 4×4×4×4×4×4×4×4×3. This
nine-way tensor is a better structure to describe the image data. The first-order
of the nine-way tensor contains the data of a 2×2 pixel block of the image and the
following orders of the tensor describe the expanding pixel blocks of the image.
Furthermore, we set all TT-ranks to 16 according to our testing experience. For
image evaluation index, we use PSNR (Peak Signal-to-noise Ratio) to measure
the quality of reconstructed image data. T able 2. shows the testing results of
one image. F ig.1. visualizes the image inpainting results.
The experiment result shows that our TT-WOPT algorithm outperforms
other algorithms for image data completion. Particularly, when the missing rate
reaches 98% and 99%, our algorithm can recover the image successfully while
other algorithms totally fail. The RSE and the PSNR values of TT-WOPT are
always better than CP-WOPT and FBCP. In addition, the image visual quality
of our method is always the best.

Completion of High Order Tensor Data with Missing Entries

7

Fig. 1. Visualizing results of image inpainting performance of three different algorithms
under five different missing rates of 85%, 90%, 95%, 98% and 99%. The values of missing
entries of the image are changed from 0 to 255 in order to show the observed image
clearly on the white paper.

Table 2. Comparison of the inpainting performance (RSE and PSNR) of three algorithms under five different missing rates: 85%, 90%, 95%, 98% and 99% of a testing
image.
missing rate
RSE
TT-WOPT
PSNR
RSE
CP-WOPT
PSNR
RSE
FBCP
PSNR

5

85%
0.1233
23.4877
0.1891
18.8578
0.1440
22.2853

90%
0.1297
22.6076
0.3169
18.0389
0.1867
19.9410

95%
0.1416
21.5282
0.5348
12.5649
0.2432
17.5166

98%
0.2202
18.9396
1.0918
7.8015
0.3052
15.4784

99%
0.2638
17.0029
1.1309
6.4971
0.3372
14.5841

Conclusion

In this paper, we first elaborate the basis of tensor and the tensor-train decomposition method. Then we use a gradient-based first-order optimization method
to find the factors of the tensor-train decomposition when tensor has missing
entries and propose the TT-WOPT algorithm. This algorithm can solve the
tensor completion problem of high dimension tensor. From the simulation and
image experiments, we can see our algorithm outperforms the other state-ofthe-art methods in many situations especially when the missing rate of data is
extremely high. Our study also proves that high order tensorization of data is an
effective and efficient method to represent data. Furthermore, it should be noted
that the accuracy of TT model is sensitive to the selection of TT-ranks. Hence,
we will study on how to choose TT-ranks automatically in our future work.

8

Longhao Yuan, Qibin Zhao and Jianting Cao

Acknowledgement
This work is supported by JSPS KAKENHI (Grant No. 17K00326) and KAKENHI (Grant No. 15H04002).

References
1. Acar, E., Dunlavy, D.M., Kolda, T.G., Mørup, M., Scalable Tensor Factorizations
for Incomplete Data, Chemometrics and Intelligent Laboratory Systems, vol. 106,
no. 1, pp. 41–56, (2011).
2. Zhao, Q., Zhang, L., Cichocki, A., Bayesian CP Factorization of Incomplete Tensors
with Automatic Rank Determination, IEEE transactions on pattern analysis and
machine intelligence, vol. 37, no. 9, pp. 1751–1763, (2015).
3. De Lathauwer, L., Castaing, J., Blind Identification of Underdetermined Mixtures
by Simultaneous Matrix Diagonalization, IEEE Transactions on Signal Processing,
vol. 56, no. 3, pp. 1096–1105, (2008).
4. Muti, D., Bourennane, S., Multidimensional Filtering Based on a Tensor Approach,
Signal Processing, vol. 85, no. 12, pp. 2338–2353, (2005).
5. Mocks, J., Topographic Components Model for Event-related Potentials and Some
Biophysical Considerations, IEEE transactions on biomedical engineering, vol. 35,
no. 6, pp. 482–484, (1988).
6. Shashua, A., Levin, A., Linear Image Coding for Regression and Classification Using the Tensor-rank Principle, in Computer Vision and Pattern Recognition, 2001.
CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, vol. 1.
IEEE, pp. I–I, (2001).
7. Vasilescu, M.A.O., Terzopoulos, D., Multilinear Image Analysis for Facial Recognition, in Pattern Recognition, 2002. Proceedings. 16th International Conference on,
vol. 2. IEEE, pp. 511–514, (2002).
8. Kolda, T.G., Bader, B.W., Tensor Decompositions and Applications, SIAM review,
vol. 51, no. 3, pp. 455–500, (2009).
9. Harshman, R.A., Foundations of the pParafac Procedure: Models and Conditions
for an” Explanatory” Multi-modal Factor Analysis, (1970).
10. Sorensen, M., De Lathauwer, L., Comon, P., Icart, S., Deneire, L., Canonical
Polyadic Decomposition with Orthogonality Constraints, SIAM Journal on Matrix
Analysis and Applications, (2012).
11. Tucker, L.R., Some Mathematical Notes on Three-mode Factor Analysis, Psychometrika, vol. 31, no. 3, pp. 279–311, (1966).
12. Gandy, S., Recht, B., Yamada, I., Tensor Completion and Low-n-rank Tensor Recovery via Convex Optimization, Inverse Problems, vol. 27, no. 2, p. 025010, (2011).
13. Oseledets, I.V., Tensor-train Decomposition, SIAM Journal on Scientific Computing, vol. 33, no. 5, pp. 2295–2317, (2011).
14. Cichocki, A., Lee, N., Oseledets, I.V., Phan, A.H., Zhao, Q., Mandic, D.P., et al.,
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1
Low-rank Tensor Decompositions, Foundations and Trends R in Machine Learning,
vol. 9, no. 4-5, pp. 249–429, (2016).
15. Nocedal, J., Wright, S., Numerical optimization. Springer Science & Business
Media, (2006).

