1

Efficient Low Rank Tensor Ring Completion

arXiv:1707.08184v1 [cs.LG] 23 Jul 2017

Wenqi Wang, Vaneet Aggarwal, and Shuchin Aeron

Abstract—Using the matrix product state (MPS) representation
of the recently proposed tensor ring decompositions, in this paper
we propose a tensor completion algorithm, which is an alternating
minimization algorithm that alternates over the factors in the
MPS representation. This development is motivated in part by
the success of matrix completion algorithms that alternate over
the (low-rank) factors. In this paper, we propose a spectral initialization for the tensor ring completion algorithm and analyze
the computational complexity of the proposed algorithm. We
numerically compare it with existing methods that employ a low
rank tensor train approximation for data completion and show
that our method outperforms the existing ones for a variety of
real computer vision settings, and thus demonstrate the improved
expressive power of tensor ring as compared to tensor train.

I. I NTRODUCTION
Tensor decompositions for representing and storing data
have recently attracted considerable attention due to their
effectiveness in compressing data for statistical signal processing [1]–[5]. In this paper we focus on Tensor Ring (TR)
decomposition [6] and in particular its relation to Matrix Product States (MPS) [7] representation for tensor representation
and use it for completing data from missing entries. In this
context our algorithm is motivated by recent work in matrix
completion where under a suitable initialization an alternating
minimization algorithm [8], [9] over the low rank factors is
able to accurately predict the missing data.
Recently, tensor networks, considered as the generalization
of tensor decompositions, have emerged as the potentially
powerful tools for analysis of large-scale tensor data [7].
The most popular tensor network is the Tensor Train (TT)
representation, which for a order-d tensor with each dimension
of size n requires O(dnr2 ) parameters, where r is the rank
of each of the factors, and thus allows for the efficient data
representation [10]. Tensor completion based on tensor train
decompositions have been recently considered in [11], [12].
The authors of [11] considered the completion of data based
on the alternating least square method.
Although the TT format has been widely applied in numerical analysis, its applications to image classification and
completion are rather limited [4], [11], [12]. As outlined in
[6], TT decomposition suffers from the following limitations.
Namely, (i) TT model requires rank-1 constraints on the border
factors, (ii) TT ranks are typically small for near-border factors
and large for the middle factors, and (iii) the multiplications
of the TT factors are not permutation invariant. In order to
alleviate those drawbacks, a tensor ring (TR) decomposition
has been proposed in [6]. TR decomposition removes the unit
rank constraints for the boundary tensor factors and utilizes a
W. Wang and V. Aggarwal are with Purdue University, West Lafayette
IN 47907, email: {wang2041, vaneet}@purdue.edu. S. Aeron is with Tufts
University, Medford, MA 02155, email: shuchin@ece.tufts.edu.

trace operation in the decomposition. The multilinear products
between cores also have no strict ordering and the cores can be
circularly shifted due to the properties of the trace operation.
This paper provides novel algorithms for data completion
when the data is modeled as a TR decomposition.
For data completion using tensor decompositions, one of
the key attribute is the notion of the rank. Even though the
rank in TR is a vector, we can assume all ranks to be the
same, unlike that for tensor-train case where the intermediate
ranks are higher, thus providing a single parameter that can be
tuned based on the data and the number of samples available.
The use of trace operation in the tensor ring structure brings
challenges for completion as compared to that for tensor train
decomposition. The tensor ring structure is equivalent to a
cyclic structure in tensor networks, and understanding this
structure can help understand completion for more general
tensor networks. In this paper, we propose an alternating
minimization algorithm for the tensor ring completion. For
the initialization of the this algorithm, we extend the tensor
train approximation algorithm in [10] for zero-filled missing
data. Further, the different sub-problems in alternating minimization are converted to efficient least square problems, thus
significantly improving the complexity of each sub-problem.
We also analyze the storage and computational complexity of
the proposed algorithm.
We note that, to the best of our knowledge, tensor ring
completion has never been investigated for tensor completion,
even though tensor ring factorization has been proposed in
[6]. The different novelties as compared to [6] include the
initialization algorithm, exclusion of the normalization of
tensor factors, utilizing the structure of the different subproblems of alternating minimization with incomplete data
to convert to least squares based problems, and analysis of
storage and computational complexity.
The proposed algorithm is evaluated on a variety of data
sets, including Einstein’s image, Extended YaleFace Dataset B,
and high speed video. The results are compared with the tensor
train completion algorithms in [11], [12], and the additional
structure in the tensor ring is shown to significantly improve
the performance as compared to using the TT structure.
The rest of the paper is organized as follows. In section II
we introduce the basic notation and preliminaries on the TR
decomposition. In section III we outline the problem statement
and propose the main algorithm. We also describe the computational complexity of the proposed algorithm. Following
that we test the algorithm extensively against competing
methods on a number of real and synthetic data experiments in
section IV. Finally we provide conclusion and future research
directions in section V. The proofs of Lemmas are provided
in the Appendix.

2

II. N OTATION & P RELIMINARIES
In this paper, vector and matrices are represented by bold
face lower case letters (x, y, z, · · ·) and bold face capital letters
(X, Y, Z, · · ·) respectively. A tensor with order more than two
is represented by calligraphic letters (X, Y, Z). For example,
an nth order tensor is represented by X ∈ RI1 ×I2 ×···×In ,
where Ii:i=1,2,··· ,n is the tensor dimension along mode i.
The tensor dimension along mode i could be an expression,
where the expression inside () is evaluated as a scalar,
e.g. X ∈ R(I1 I2 )×(I3 I4 )×(I5 I6 ) represents a 3-mode tensor
where dimensions along each mode is I1 I2 , I3 I4 , and I5 I6
respectively. An entry inside a tensor X is represented as
X(i1 , i2 , · · · , in ), where ik:k=1,2,..,n is the location index
along the k th mode. A colon is applied to represent all
the elements of a mode in a tensor, e.g. X(:, i2 , · · · , in )
represents the fiber along mode 1 and X(:, :, i3 , i4 , · · · , in )
represents the slice along mode 1 and mode 2 and so forth.
Similar to Hadamard product under matrices case, Hadamard
product between tensors is the entry-wise product of the two
tensors. vec(·) represents the vectorization of the tensor in the
argument. The vectorization is carried out lexicographically
over the index set, stacking the elements on top of each other
in that order. Frobenius norm of a tensor is the same as the
vector `2 norm of the corresponding tensor after vectorization,
e.g. kXkF = kvec(X)k`2 . × between matrices is the standard
matrix product operation.
Definition 1. (Mode-i unfolding [13]) Let X ∈ RI1 ×···×In
be a n-mode tensor. Mode-i unfolding of X, denoted as X[i] ,
matrized the tensor X by putting the ith mode in the matrix
rows and remaining modes with the original order in the
columns such that
X[i] ∈ RIi ×(I1 ···Ii−1 Ii+1 ···In ) .

(1)

Definition 2. (Left Unfolding and Right Unfolding [14]) Let
X ∈ RRi−1 ×Ii ×Ri be a third order tensor, the left unfolding
is the matrix obtained by taking the first two modes indices
as rows indices and the third mode indices as column indices
such that
L(X) = (X[3] )T ∈ R(Ri−1 Ii )×Ri .
(2)
Similarly, the right unfolding gives
R(X) = X[1] ∈ RRi−1 ×(Ii Ri ) .

(3)

Definition 3. (Mode-i canonical matrization [13] ) Let X ∈
RI1 ×···×In be an nth order tensor, the mode-i canonical
matrization gives
X<i> ∈ R(

Qi

t=1

Q
It )×( n
t=i+1 It )

,

(4)

such that any entry in X<i> satisfies
X<i> (i1 + (i2 − 1)I1 + · · · + (ik − 1)

k−1
Y

n-order tensor with Ii -dimension along the ith mode, then
any entry inside the tensor, denoted as X(i1 , · · · , in ), is
represented by
X(i1 , · · · , in ) =

R1
X
r1 =1

···

Rn
X

U1 (rn , i1 , r1 ) · · ·

rn =1

(6)

Un (rn−1 , in , rn ),
where Ui ∈ R
is a set 3-order tensors, also named
matrix product states (MPS), that consist the bases of the
tensor ring structures. Note that Uj (:, ij , :) ∈ RRj−1 ×1×Rj
can be regarded as a matrix of size RRj−1 ×Rj , thus (6) is
equivalent to
Ri−1 ×Ii ×Ri

X(i1 , · · · , in ) = tr(U1 (:, i1 , :) × · · · × Un (:, in , :)).

(7)

Remark 1. (Tensor Ring Rank (TR-Rank)) In the formulation
of tensor ring, we note that tensor ring rank is the vector
[R1 , · · · , Rn ]. In general, Ri ’s are not necessary to be the
same. In our set-up, motived by the fact that Ri and Ri−1 represent the connection between Ui with the remaining Uj:j6=i ,
we set Ri = R ∀i = 1, · · · , n, and the scalar R is referred
to as the tensor ring rank in the remainder of this paper.
Remark 2. (Tensor Train [10]) Tensor train is a special case
of tensor ring when Rn = 1.
Based on the formulation of tensor ring structure, we define
a tensor connect product, the operation between the MPSs, to
describe the generation of high order tensor X from the sets
of MPSs Ui:i=1,··· ,n . Let R0 , Rn for ease of expressions.
Definition 5. (Tensor Connect Product) Let Ui ∈
RRi−1 ×Ii ×Ri , i = 1, · · · , n be n 3rd-order tensors, the tensor
connect product between Uj and Uj+1 is defined as,
Uj Uj+1 ∈ RRj−1 ×(Ij Ij+1 )×Rj+1
= reshape (L(Uj ) × R(Uj+1 )) .

(8)

Thus, the tensor connect product n MPSs is
U = U1 · · · Un ∈ RR0 ×(I1 ···In )×Rn .

(9)

Tensor connect product gives the product rule for the production between 3-order tensors, just like the matrix product
as for 2-order tensor. Under matrix case, Uj ∈ R1×Ij ×Rj ,
Uj+1 ∈ RRj ×Ij+1 ×1 . Thus tensor connect product gives the
vectorized solution of matrix product.
We then define an operator f that applies on U. Let U ∈
RR0 ×(I1 ···In )×Rn be the 3-order tensor, R0 = Rn , and let f be
a reshaping operator function that reshapes a 3-order tensor U
to a tensor of dimension X of dimension RI1 ×···×In , denoted
as
X = f (U),
(10)
where X(i1 , · · · , in ) is generated by

It ,
(5)

X(i1 , · · · , in ) = tr(U(:, i1 +(i2 −1)I1 +· · ·+(in −1)In−1 , :)).
(11)
Thus a tensor X ∈ RI1 ×···×In with tensor ring structure is
equivalent to
X = f (U1 · · · Un ).
(12)

Definition 4. (Tensor Ring [6]) Let X ∈ RI1 ×···×In be a

Similar to matrix transpose, which can be regarded as an
operation that cyclic swaps the two modes for a 2-order

t=1
n−1
Y

ik+1 + (ik+2 − 1)Ik+1 + · · · + (in − 1)

It )

t=k+1

=X(i1 , · · · , in ).

3

tensor, we define a ‘tensor permutation’ to describe the cyclic
permutation of the tensor modes for a higher order tensor.
Definition 6. (Tensor Permutation) For any n-order tensor
X ∈ RI1 ×···×In , the ith tensor permutation is defined as XPi ∈
RIi ×Ii+1 ×···×In ×I1 ×I2 ×···×Ii−1 such that ∀i , ji ∈ [1, Ii ]
XPi (ji , · · · , jn , j1 , · · · , ji−1 ) = X(j1 , · · · , jn ).

(13)

Then we have the following result.
Lemma 1. If X = f (U1 · · · Un ), then XPi
=
f (Ui Ui+1 · · · Un U1 · · · Ui−1 ).
With this background and basic constructs, we now outline
the main problem setup.
III. F ORMULATION AND A LGORITHM FOR T ENSOR R ING
C OMPLETION
A. Problem Formulation
Given a tensor X ∈ RI1 ×···×In that is partially observed
at locations Ω, let PΩ ∈ RI1 ×···×In be the corresponding
binary tensor in which 1 represents an observed entry and 0
represents a missing entry. The problem is to find a low tensor
ring rank (TR-Rank) approximation of the tensor X, denoted
as f (U1 · · · Un ), such that the recovered tensor matches X at
PΩ . This problem is referred as the tensor completion problem
under tensor ring model, which is equivalent to the following
problem
min

Ui:i=1,··· ,n

kPΩ ◦ (f (U1 · · · Un ) − X)k2F .

(14)

Note that the rank of the tensor ring R is predefined and the
dimension of Ui:i=1,··· ,n is RR×Ii ×R .
To solve this problem, we propose an algorithm, referred
as Tensor Ring completion by Alternating Least Square (TRALS) to solve the problem in two steps.
• Choose an initial starting point by using Tensor Ring
Approximation (TRA). This initialization algorithm is
detailed in Section III-B.
• Update the solution by applying Alternating Least Square
(ALS) that alternatively (in a cyclic order) estimates
a factor say Ui keeping the other factors fixed. This
algorithm is detailed in Section III-C.
B. Tensor Ring Approximation (TRA)
A heuristic initialization algorithm, namely TRA, for solving (14) is proposed in this section. The proposed algorithm is
a modified version of tensor train decomposition as proposed
in [10]. We first perform a tensor train decomposition on the
zero-filled data, where the rank is constrained by Singular
Value Decomposition (SVD). Then, an approximation for
the tensor ring is formed by extending the obtained factors
to the desired dimensions by filling the remaining entries
with small random numbers. We note that the small entries
show faster convergence as compared to zero entries based
on our considered small examples, and thus motivates the
choice in the algorithm. Further, non-zero random entries
help the algorithm initialize with larger ranks since the TT
decomposition has the corner ranks as 1. Having non-zero
entries can help the algorithm not getting stuck in a local
optima of low corner rank. The TRA algorithm is given in
Algorithm 1.

Algorithm 1 Tensor Ring Approximation (TRA)
Input: Missing entry zero filled tensor X ∈ RI1 ×I2 ×···×In ,
TR-Rank R, small random variable depicting the standard
deviation of the added normal random variable σ
Output: Tensor train decomposition Ui:i=1,··· ,n ∈ RR×Ii ×R
1: Apply mode-1 canonical matricization for X and get
matrix X1 = X<1> ∈ RI1 ×(I2 I3 ···In )
2: Apply SVD and threshold the number of singular
values to be T1 = min(R, I1 , I2 · · · In ), such that
X1 = U1 S1 V1> , U1 ∈ RI1 ×T1 , S1 ∈ RT1 ×T1 , V1 ∈
RT1 ×(I2 I3 ···In ) . Reshape U1 to R1×I1 ×T1 and extend it to
U1 ∈ RR×I1 ×R by filling the extended entries by random
normal distributed values sampled from N (0, σ 2 ).
3: Let M1 = S1 V1> ∈ RT1 ×(I2 I3 ···In ) .
4: for i = 2 to n − 1 do
5:
Reshape Mi−1 to Xi ∈ R(Ti−1 Ii )×(Ii+1 Ii+2 ···In ) .
6:
Compute SVD and threshold the number of singular
values to be Ti = min(R, Ti−1 Ii , Ii+1 · · · In ), such that
Xi = Ui Si Vi> , Ui ∈ R(Ti−1 Ii )×Ti , Si ∈ RTi ×Ti , V ∈
RTi ×(Ii+1 Ii+2 ···In ) . Reshape Ui to RTi−1 ×Ii ×Ti and extend it to Ui ∈ RR×Ii ×R by filling the extended entries by
random normal distributed values sampled from N (0, σ 2 ).
7:
Set Mi = Si Vi> ∈ RTi ×(Ii+1 Ii+2 ···In )
8: end for
9: Reshape Mn−1 ∈ RTn−1 ×In to RTn−1 ×In ×1 , and extend
it to Un ∈ RR×In ×R by filling the extended entries by
random normal distributed values sampled from N (0, σ 2 )
to get Un
10: Return U1 , · · · , Un

C. Alternating Least Square
The proposed tensor ring completion by alternating least
square method (TR-ALS) solves (14) by solving the following
problem for each i iteratively. The factors are initialized from
the TRA algorithm presented in the previous section.
Ui = argminY kPΩ ◦ f (U1 · · · Ui−1 YUi+1 · · · Un ) − XΩ )k2F .
(15)
Lemma 2. When i 6= 1, solving
Ui = argminY kPΩ ◦ f (U1 · · · Ui−1 YUi+1 · · · Un ) − XΩ )k2F
(16)
is equivalent to
Pi 2
i
Ui = argminY kPP
Ω ◦ f (YUi+1 · · · Un U1 · · · Ui−1 ) − XΩ kF .
(17)

Since the format of (17) is exactly the same for each i when
the other factors are known, it is enough to describe solving a
single Uk without loss of generality. Based on Lemma 2, we
need to solve the following problem.
Pk 2
k
Uk = argminY kPP
Ω ◦ f (YUk+1 · · · Un U1 · · · Uk−1 ) − XΩ kF .
(18)

We further apply mode-k unfolding, which gives the equiv-

4

Algorithm 2 TR-ALS Algorithm

alent problem
k
Uk = argminY kPP
Ω [k] ◦ f (YUk+1 · · · Un U1 · · · Uk−1 )[k]

2
k
− XP
Ω [k] kF ,

(19)
Pk
k
where PP
Ω [k] , f (YUk+1 · · · Un U1 · · · Uk−1 )[k] and XΩ [k] are
Ik ×(Ik+1 ···In I1 ···Ik−1 )
matrices with dimension R
.
The trick in solving (19) is that each slice of tensor Y,
denoted as Y(:, ik , :), ik ∈ {1, · · · , Ik } which corresponds
k
to each row of PP
Ω [k] , f (YUk+1 · · · Un U1 · · · Uk−1 )[k] and
Pk
XΩ [k] , can be solved independently, thus equation (19) can
be solved by solving Ik equivalent subproblems

Uk (:, ik , :) = argminZ∈RR×1×R
Pk
2
k
kPP
Ω [k] (ik , :) ◦ f (ZUk+1 · · · Uk−1 ) − XΩ [k] (ik , :)kF .

B(k)

Let

=

R×(Ik+1 ···In I1 ···Ik−1 )×R

R
entries

in

,

vector

(20)

Uk+1 · · · Un U1 · · · Uk−1
∈
Ωik
be
the
observed
(k)
X[k] (ik , :),
thus
BΩi
∈
k

R×(Ik+1 ···In I1 ···Ik−1 )Ωi ×R

k
R
are the components in B(k)
Pk
such that PΩ [k] (ik , (Ik+1 · · · In I1 · · · Ik−1 )Ωik ) are observed.
Thus equation (20) is equivalent to

Input: Zero-filled Tensor XΩ ∈ RI1 ×I2 ×...×In , binary observation index tensor PΩ ∈ RI1 ×I2 ×...×In , tensor ring
rank R, thresholding parameter tot, maximum iteration
maxiter
Output: Recovered tensor XR
1: Apply tensor ring approximation in Algorithm 1 on XΩ to
initialize the MPSs Ui:i=1,··· ,n ∈ RR×Ii ×R . Set iteration
parameter ` = 0.
2: while ` ≤ maxiter do
3:
`=`+1
4:
for i = 1 to n do
5:
Solve by Least Square Method
Ui (`)
=
(`−1)
(`−1) (`)
(`)
argminU kPΩ ◦ (UUi+1 ...Un
U1 ...Ui−1 − X)k2F
6:
end for
kU(`+1) −U(`) k
7:
if n (`) n F ≤ tot then
kUn kF
8:
Break
9:
end if
10: end while
(`) (`)
(`)
(`)
11: Return XR = reshape(U1 U2 ...Un−1 Un )

Details of the algorithm are given in Algorithm 2.

(k)

Uk (:, ik , :) =argminZ kf (ZBΩi )
k

2
k
− XP
Ω [k] (ik , (Ik+1 · · · In I1 · · · Ik−1 )Ωik ))kF .
(21)

We regard Z ∈ RR×1×R as a matrix Z ∈ RR×R . Since the
Frobenius norm of a vector in (21) is equivalent to entry-wise
square summation of all entries, we rewrite (21) as
Uk (:, ik , :) = argminZ∈RR×R
X
(k)
2
k
ktr(Z × BΩi (:, j, :)) − XP
Ω [k] (ik , j)kF .

(22)

k

j∈Ωik

Lemma 3. Let A ∈ Rr1 ×r2 and B ∈ Rr2 ×r1 be any two
matrices, then
Trace(A × B) = vec(B> )> vec(A).

(23)

Based on Lemma 3, (22) becomes
X
Uk (:, ik , :) = argminZ
(k)

j∈Ωi

(24)

k

(k)
kvec((BΩi (:, j, :))> )> vec(Z)
k

−

2
k
XP
Ω [k] (ik , j)kF .

Then the problem for solving Uk [:, ik , :] becomes a least
square problem. Solving Ik least square problem would give
the optimal solution for Uk . Since each Ui:i=1,··· ,n can solved
by a least square method, tensor completion under tensor ring
model can be solved by taking orders to update Ui:i=1,··· ,n
until convergence. We note the completion algorithm does not
require normalization on each MPS, unlike the decomposition
algorithm [6] that normalizes all the MPSs to seek a unique
factorization. The stopping criteria in TR-ALS is measured via
the changes of the last tensor factors Un since if the last factor
does not change, the other factors are less likely to change.

D. Complexity Analysis
Storage Complexity Given an n-order tensorQ X ∈
n
RI1 ×···×In , the total amount of parameters to store is i=1 Ii ,
which increases exponentially with order. Under tensor ring
model, we can reduce the storage space by converting each
factor (except the last) one by one to being orthonormal
and multiply the product with the next factor. Thus, the
number of parameters to store the MPSs
Ui:i=1,··· ,n−1 with
Pn−1
orthonormal property requires storage i=1 (R2 Ii − R2 ), and
2
Un with
Pnparameter R In . Thus, the total amount of storage
2
is R ( i Ii − n + 1), where the tensor ring rank R can be
adjusted to fit the tensor data at the desired accuracy.
Computational Complexity For each Ui , the least square
problem in (19) solved by pseudo-inverse gives a computational complexity max(O(P R4 ), O(R6 )), where P is the
total number of observations. Within one iteration when
n MPSs need to be updated, the overall complexity is
max(O(nP R4 ), O(nR6 )).
We note that tensor train completion [11] gives the similar
complexity as tensor ring completion. However, tensor train
rank is a vector and it is hard for tuning to achieve the
optimal completion. The intermediate ranks in tensor train are
large in general, leading to significantly higher computational
complexity of tensor train. This is alleviated in part by the
tensor ring structure which can be parametrized by the tensor
ring rank which can be smaller than the intermediate ranks of
the tensor train in general. In addition, the single parameter
in the tensor ring structure leads to an ease in characterizing
the performance for different ranks and can be easily tuned
for practical applications. The lower ranks lead to lower
computational complexity of data completion under the tensor
ring structure as compared to the tensor train structure.

5

IV. N UMERICAL R ESULTS
In this section, we compare our proposed TR-ALS algorithm
with tensor train completion under alternating least square (TTALS) algorithm [11], which solves the tensor completion by
alternating least squares under tensor train format. SiLRTC
algorithm is another tensor train completion algorithm proposed in [12] and the tensor train rank is tuned based on
the dimensionality of the tensor. It is selected for comparison
as it shows good recovery in image completion [12]. The
evaluation merit we consider is Recovery Error (RE). Let X̂ be
the recovered tensor and X be the ground truth of the tensor.
Thus, the recovery error is defined as
RE =

kX̂ − XkF
.
kXkF

Tensor ring completion by alternating least square (TR-ALS )
algorithm is an iterative algorithm and the maximum iteration,
maxiter, is set to be 300. The convergence is captured by
the change of the last factorization term Un , where the error
tolerance is set to be 10−10 .
In the remaining of the section, we first evaluate the
completion results for synthetic data. Then we validate the
proposed TR-ALS algorithm on image completion, YaleFace
image-sets completion, and video completion.
A. Synthetic Data
In this section, we consider a completion problem of a 4order tensor X ∈ R20×20×20×20 with TR-Rank being 8 without loss of generality. The tensor is generated by a sequence of
connected 3-rd order tensor Ui:i=1,··· ,4 ∈ R8×20×8 and every
entry in Ui are sampled independently from a standard normal
distribution.
TT-ALS is considered as a comparable to show the difference between tensor train model and tensor ring model. Two
different tensor train ranks are chosen for the comparisons.
The first tensor-train ranks are chosen as [8, 8, 8], and the
completion with these ranks is called Low rank tensor train
(LR-TT) completion. The second tensor-train ranks are chosen
as the double of the first ( [16, 16, 16]), and the completion
with these ranks is called High rank tensor train (HR-TT)
completion. Another comparable used is the SiLRTC algorithm proposed in [12], where the rank is adjusted according
to the dimensionality of the tensor data, and a heuristic factor
of f = 1 in the proposed algorithm of [12] is selected for
testing.
Fig.1a shows the completion error of TR-ALS, LR-TT,
HR-TT, and SiLRTC for observation ratio from 10% to
60%. TR-ALS shows the lowest recovery error compared
with other algorithms and the recovery error drops to 10−10
for observation ratio larger than 14%. The large completion
errors of all tensor train algorithm at every observation ratio
show that tensor train algorithm can not effectively complete
the tensor data generated under tensor ring model. Fig. 1b
shows the convergence of TR-ALS under sampling ratios
10%, 15%, 20%, 30%, 40%, and 50%, and the plot indicates
the higher the observation ratios, the faster the algorithm
converges. When the observation ratio is lower than 10%,

the tensor with missing data can not be completed under
the proposed set-up. The fast convergence of the proposed
TR-ALS algorithm indicates that alternating least square is
effective in tensor ring completion.
B. Image Completion
In this section, we consider the completion of RGB Einstein
Image [15], treated as a 3-order tensor X ∈ R600×600×3 . A
reshaping operation is applied to transform the image into a
7-order tensor of size R6×10×10×6×10×10×3 . Reshaping low
order tensors into high order tensors is a common practice in
literature and has shown improved performance in classification [4] and completion [12].
Fig. 2a shows the recovery error versus rank for TRALS and TT-ALS when the percentage of data observed
are 5%, 10%, 20%, 30%. At any considered ranks, TR-ALS
completes the image with a better accuracy than TT-ALS.
For any given percentage of observations, the recovery error
first decreases as the rank increases which is caused by the
increased information being captured by the increased number
of parameters in the tensor structure. The recovery error then
starts to increase after a thresholding rank, which can be
ascribed to over-fitting. The plot also indicates that higher
the observation ratio, larger the thresholding rank, which to
the best of our knowledge is reported for the first time. Fig.
2b shows the recovered image of Einstein image when 10%
pixels are randomly observed. TR-ALS with rank 28 gives the
best recovery accuracy in the considered ranks.
C. YaleFace Dataset Completion
In this section, we consider Extended YaleFace Dataset B
[16] that includes 38 people with 9 poses under 64 illumination
conditions. Each image has the size of 192 × 168, where
we down-sample the size of each image to 48 × 42 for
ease of computation. We consider the image subsets of 38
people under 64 illumination with 1 pose by formatting the
data into a 4-order tensor in R48×42×64×38 , which is further
reshaped into a 8-order tensor X ∈ R6×8×6×7×8×8×19×2 . We
consider the case when 10% of pixels are randomly observed.
YaleFace sets completion is considered to be harder than an
image completion since features under different illumination
and across human features are harder to learn than information
from the color channels of images. Table I shows that for any
considered rank, TR-ALS recovers data better than TT-ALS
and the best completion result in the given set-up is 16.25%
for TR-ALS as compared with 25.55% given by TT-ALS.
Further we reshape the data into an 11-order tensor and 4order tensor to evaluate the effect of reshaped tensor size on
tensor completion. The result in Table I shows that in the
given reshaping set-up, reshaping tensor from 4-order tensor
to 7-th order tensor significantly improve the performance of
tensor completion by decreasing recovery error from 21.48%
to 16.25%. However, further reshaping to 11-order tensor
slightly degrades the performance of completion, resulting in
an increased recovery error to 16.34%.
Fig. 3 shows the original image, missing images, and
recovered images using TR-ALS and TT-ALS algorithms for
ranks of 10, 20, and 30, where the completion results given

6

5

2

0.1
0.15

-2

Recovery Error (log10)

Recovery Error (log10)

0
TR
LR-TT
HR-TT
SiLRTC

-4
-6
-8

0.2
0.3

0.4
0.5

0

-5

-10

-10
-12
0.1

-15
0.2

0.3

0.4

0.5

0.6

0

20

40

60

80

100

Iteration

Observation Ratio

(a) Recovery error versus observation Ratio. Average of 10 experiments
for TR-ALS with TR-Rank 8, TT-ALS with TT-Rank [8, 8, 8], TT-ALS (b) Convergence plot for TR-ALS under observation ratio being from
with TT-Rank [16, 16, 16], and SiLRTC are shown for comparison. 0.1 to 0.5 for 4th order tensor of dimension 20 × 20 × 20 × 20 with
Error bar marked using one standard deviation.
TR-Rank 8.
Fig. 1: Synthetic data is a 4th order tensor of dimension 20 × 20 × 20 × 20 with TR-Rank being 8.

Recovery Error (log10)

TR(5%)
TT(5%)

TR(10%)
TT(10%)

TR(20%)
TT(20%)

TR(30%)
TT(30%)

-0.4

-0.6

-0.8

-1

(b) The completed Einstein Image when 10% of pixels are randomly observed. The first column is the original Einstein image
and Einstein image with 10% randomly observed entries. In the
-1.2
remaining 4 columns, the first row are completed images by TR5
10
15
20
25
30
ALS with TR-Rank 2, 10, 18, 28 and the second row are images
Rank
completed by TT-ALS with the same TT-Rank. The completion errors
(a) The recovery error versus rank for TR-ALS and TT-ALS under for TR-ALS and TT-ALS are 33.97%, 14.03%, 10.83%, 14.55% and
observation ratio 5%, 10%, 20%, 30%
38.51%, 22.89%, 20.70%, 23.19% accordingly.
Fig. 2: Einstein image is of size 600 × 600 × 3, and is further reshaped into a 7-order tensor of size 6 × 10 × 10 × 6 × 10 × 10 × 3 tensor
for tensor ring completion

Rank
6×8×6×7×8×8×19×2

TT-ALS (R
)
TR-ALS (R6×8×6×7×8×8×19×2 )
TR-ALS (R2×3×2×4×2×3×7×8×8×19×2 )
TR-ALS (R48×42×64×38 )

5

10

15

20

25

30

37.08%
33.45%
33.73%
30.36%

29.65%
24.67%
25.08%
26.08%

27.91%
20.72%
21.20%
23.74%

26.84%
18.47%
18.97%
22.22%

26.16%
16.92%
17.34%
21.48%

25.55%
16.25%
16.34%
21.57%

TABLE I: Completion error of 10% observed Extended YaleFace data for TT-ALS and TR-ALS under rank 5, 10, 15, 20, 25, 30.
by TR-ALS better captures the detail information given from
the image and recovers the image with a better resolution.
D. Video completion
The video data we used in this section is high speed camera
video for gun shooting [17]. It is downloaded from Youtube
with 85 frames in total and each frame is consisted by a
100×260×3 image. Thus the video is a 4-order tensor of size
100 × 260 × 3 × 85, which is further reshaped into a 11-order
tensor of size 5 × 2 × 5 × 2 × 13 × 2 × 5 × 2 × 3 × 5 × 17

for completion. Video is a multi-dimensional data with different color channel a time dimension in addition to the 2D
image structure.
In Table II, we show that TR-ALS achieves 6.25% recovery
error when 10% of the pixels are observed, which is much
better than the best recovery error of 14.83% achieved by
TT-ALS. The first frame of the video is shown in Fig. 4,
where the first row shows the original frame and the completed
frames by TR-ALS, and the second row shows the frame with
missing entries and the frames completed by TT-ALS. The

7

Original

Missing

TR(10)

TR(20)

TR(30)

TT(10)

TT(20)

TT(30)
Fig. 3: YaleFace dataset is sub-sampled to formulated into a tensor of size R48×42×64×38 , and is further reshaped into a 8-order tensor of
size 6 × 8 × 6 × 7 × 8 × 8 × 19 × 2 for tensor ring completion. 90% of the pixels are assumed to be randomly missing. YaleFace dataset
completion. From top to bottom are original images, missing images, TR-ALS completed images for TR-Ranks 10, 20, 30, and TT-ALS
completed images for ranks 10, 20, 30.

Rank

10

15

20

25

30

TT-ALS
TR-ALS

19.16%
13.90%

14.83%
10.12%

16.42%
8.13%

16.86%
6.88%

16.99%
6.25%

TABLE II: Completion error of 10% observed Video data for TT-ALS and TR-ALS under rank 10, 15, 20, 25.
Original

TR(10)

TR(15)

TR(20)

TR(25)

TR(30)

Missing

TT(10)

TT(15)

TT(20)

TT(25)

TT(30)

Fig. 4: Gun Shot is a video download from Youtube of size 100 × 260 × 3 × 80. 90% of the pixels are assumed to be randomly missing.
The video is further reshaped into a 11-order tensor of size 5 × 2 × 5 × 2 × 13 × 2 × 5 × 2 × 3 × 5 × 17 for tensor ring completion. From left
to right in the top row, images are the first frame of original video and TR-ALS completed frame under TR-Rank 10, 15, 20, 25, 30. From
left to right in the second row, images are the first frame of missing video and TT-ALS completed frame under rank 10, 15, 20, 25, 30.
resolution, and the display of the bullets and the smoke depict
that the proposed TR-ALS achieves better completion results
as compared to the TT-ALS algorithm.
V. C ONCLUSION
We proposed a novel algorithm for data completion using
tensor ring decomposition. This is the first paper on data
completion exploiting this structure which is a non-trivial
extension of the tensor-train structure. Our algorithm exploits
the matrix product state representation and uses alternating

minimization over the low rank factors for completion. The
proposed approach has been evaluated on a variety of data
sets, including Einstein’s image, Extended YaleFace Dataset B,
and video completion. The evaluation results show significant
improvement as compared to the completion using a tensor
train decomposition.
Deriving provable performance guarantees on tensor completion using the proposed algorithm is left as further work.
In this context, the statistical machinery for proving analogous
results for the matrix case [8], [9] can be used.

8

VI. APPENDIX

Based on Lemma 1, we have

A. Proof of Lemma 1

(f (U1 · · · Ui−1 YUi+1 · · · Un ))Pi = f (YUi+1 · · · Un U1 · · · Ui−1 ),
(31)
thus equation (30) becomes

Proof. Let M = M1 M2 , thus
M(j1 , j2 ) =

r1
X

M1 (j1 , j)M2 (j, j2 )

(25)

j=1

where M(j1 , j2 ) locates at vec(M1 M2 )(j1 + (j2 − 1)I1 , 1).
Let T1 ∈ R(I1 I2 )×(r1 I2 ) = I(I2 ) ⊗ L(M1 ) and T2 ∈
(r1 I2 )×1
R
= L(M2 ), and T ∈ RI1 I2 ×1 = T1 T2 , thus

Pi 2
i
Ui = argminY kPP
Ω ◦ f (YUi+1 · · · Un U1 · · · Ui−1 ) − XΩ kF .
(32)
Comparing (32) and (??), we have PΩ , XΩ and U2 · · · Un
>i
i
in (??) become P>
Ω , XΩ and Ui+1 · · · Un U1 · · · Ui−1 in(32)
respectively. Thus we prove our claim.

T(j1 + (j2 − 1)I1 , 1)
=

rX
1 I2

D. Proof of Lemma 4
T1 (j1 + (j2 − 1)I1 , j)T2 (j, 1)

Proof.

j=1
jX
2 r1

=

=

T1 (j1 + (j2 − 1)I1 , j)T2 (j, 1)

(26)

Trace(A × B) =

r1
X
i

j=(j2 −1)r1 +1
r1
X

=

M(j1 , j)M2 (j, j2 )

B. Proof of Lemma 2
Proof. Based on definition of tensor permutation in (13), on
the left hand side, the (j1 , ...., jn ) entry of the tensor is
(27)

On the right hand side, the (j1 , ...., jn ) entry of the tensor
gives
f (Ui · · · Ui−1 )(j1 , · · · , jn )
(28)

U1 (:, jn−i+2 , :) · · · Ui−1 (:, jn , 1)).
Since trace is invariant under cyclic permutations, we have
Trace(Ui (:, j1 , :)Ui+1 (:, j2 , :)...Un (:, jn−i+1 , :)
U1 (:, jn−i+2 , :) · · · Ui−1 (:, jn , 1))
=Trace(U1 (:, jn−i+2 , :) · · · Ui−1 (:, jn , 1)

A(i, j)B> (i, j)

(33)

j

= vec(A)> vec(B> )

th

We conclude that any j1 + (j2 − 1)I1 entry on the left hand
side is the same as that on the right hand side, thus we prove
our claim.

=Trace(Ui (:, j1 , :)Ui+1 (:, j2 , :)...Un (:, jn−i+1 , :)

j

r1 X
r2
X
i

j=1

XPi (j1 , ..., jn ) = X(jn−i+2 , ..., jn , j1 , ..., jn−i+1 ).



r2
X

A(i, j)B(j, i)

(29)

Ui (:, j1 , :)Ui+1 (:, j2 , :)...Un (:, jn−i+1 , :))
=f (U1 · · · Un )(jn−i+2 , · · · , jn , j1 , · · · , jn−i+1 ),
which equals to the right hand side of equation (27).
Since any entries in XPi are the same as those in
Ui Ui+1 · · · Un U1 · · · Ui−1 , the claim is proved.
C. Proof of Lemma 3
Proof. First we note that tensor permutation does not change
tensor Frobenius norm as all the entries remain the same as
those before the permutation. Thus, when i 6= 1, we permute
the tensor inside the Frobenius norm in (16) and get the
equivalent equation as
Pi 2
Pi
i
Ui = argminY kPP
Ω ◦(f (U1 · · · Ui−1 YUi+1 · · · Un )) −XΩ kF .
(30)

R EFERENCES
[1] T. Kolda and B. Bader, “Tensor decompositions and applications,” SIAM
Review, vol. 51, no. 3, pp. 455–500, 2009.
[2] A. Cichocki, D. Mandic, L. De Lathauwer, G. Zhou, Q. Zhao, C. Caiafa,
and H. A. Phan, “Tensor decompositions for signal processing applications: From two-way to multiway component analysis,” IEEE Signal
Processing Magazine, vol. 32, no. 2, pp. 145–163, 2015.
[3] M. Vasilescu and D. Terzopoulos, “Multilinear image analysis for face
recognition,” Proceedings of the International Conference on Pattern
Recognition ICPR 2002, vol. 2, pp. 511–514, 2002, quebec City, Canada.
[4] A. Novikov, D. Podoprikhin, A. Osokin, and D. P. Vetrov, “Tensorizing neural networks,” in Advances in Neural Information Processing
Systems, 2015, pp. 442–450.
[5] M. Ashraphijuo, V. Aggarwal, and X. Wang, “Deterministic and probabilistic conditions for finite completability of low rank tensor,” arXiv
preprint arXiv:1612.01597, 2016.
[6] Q. Zhao, G. Zhou, S. Xie, L. Zhang, and A. Cichocki, “Tensor ring
decomposition,” arXiv preprint arXiv:1606.05535, 2016.
[7] R. Orús, “A practical introduction to tensor networks: Matrix product
states and projected entangled pair states,” Annals of Physics, vol. 349,
pp. 117–158, 2014.
[8] P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion
using alternating minimization,” in Proceedings of the forty-fifth annual
ACM symposium on Theory of computing. ACM, 2013, pp. 665–674.
[9] M. Hardt, “On the provable convergence of alternating minimization
for matrix completion,” CoRR, vol. abs/1312.0925, 2013. [Online].
Available: http://arxiv.org/abs/1312.0925
[10] I. V. Oseledets, “Tensor-train decomposition,” SIAM Journal on Scientific Computing, vol. 33, no. 5, pp. 2295–2317, 2011.
[11] L. Grasedyck, M. Kluge, and S. Kramer, “Variants of alternating least
squares tensor completion in the tensor train format,” SIAM Journal on
Scientific Computing, vol. 37, no. 5, pp. A2424–A2450, 2015.
[12] H. N. Phien, H. D. Tuan, J. A. Bengua, and M. N. Do, “Efficient tensor
completion: Low-rank tensor train,” arXiv preprint arXiv:1601.01083,
2016.
[13] A. Cichocki, “Tensor networks for big data analytics and large-scale
optimization problems,” arXiv preprint arXiv:1407.3124, 2014.
[14] S. Holtz, T. Rohwedder, and R. Schneider, “On manifolds of tensors of
fixed tt-rank,” Numerische Mathematik, vol. 120, no. 4, pp. 701–731,
2012.
[15] “Albert Einstein image,” http://orig03.deviantart.net/7d28/f/2012/361/1/
6/albert einstein by zuzahin-d5pcbug.jpg.
[16] A. S. Georghiades and P. N. Belhumeur, “Illumination cone models
for faces recognition under variable lighting,” in Proceedings of CVPR,
1998.

9

[17] “Pistol shot recorded at 73,000 frames per second,” https://youtu.be/
7y9apnbI6GA, published by Discovery on 2015-08-15.

