Fully-Connected Tensor Network Decomposition and Its Application toHigher-Order Tensor Completion
Yu-Bang Zheng,1 Ting-Zhu Huang,∗,1 Xi-Le Zhao,∗,1 Qibin Zhao,2,3 Tai-Xiang Jiang4
1

School of Mathematical Sciences, University of Electronic Science and Technology of China, China
2
Tensor Learning Team, RIKEN Center for Advanced Intelligence Project (AIP), Japan3
School of Automation, Guangdong University of Technology, China
4
School of Economic Information Engineering, Southwestern University of Finance and Economics, China{zhengyubang, xlzhao122003}@163.com, tingzhuhuang@126.com, qibin.zhao@riken.jp, taixiangjiang@gmail.com
Abstract
The popular tensor train (TT) and tensor ring (TR) decompositions have achieved promising results in science and engineering. However, TT and TR decompositions only establish a connection between adjacent two factors and are highly
sensitive to the permutation of tensor modes, leading to an
inadequate and inflexible representation. In this paper, we
propose a generalized tensor decomposition, which decomposes an N th-order tensor into a set of N th-order factors andestablishes a multi-linear operation/connection between any
two factors. Since it can be graphically interpreted as a fullyconnected network of all factors, we named it fully-connected
tensor network (FCTN) decomposition. The superiorities of
the FCTN decomposition lie in the outstanding capability forcharacterizing adequately the intrinsic correlations between
any two modes of tensors and the essential invariance fortransposition. Furthermore, we employ the FCTN decomposition to one representative task, i.e., tensor completion, anddevelop an efficient proximal alternating minimization-basedalgorithm. Theoretically, we prove the convergence of the developed algorithm, i.e., the obtained sequence of it globally
converges to a critical point. Experimental results substantiate that the proposed method compares favorably to the stateof-the-art methods based on tensor decomposition.

1

Introduction

The rapid advance in science and technology has givenrise to the wide presence of higher-order data, e.g., multitemporal, multi-spectral, and multi-scale data, which areusually expressed by higher-order tensors. Tensor decompositions focus on decomposing a higher-order tensor toa set of low-dimensional factors used to represent its latent features, which have powerful capability to capture theglobal correlations of tensors and have been widely appliedin a variety of fields, such as signal processing, computer
vision, and medical imaging (Kolda and Bader 2009; Mu
et al. 2014; Anandkumar et al. 2014; Cong et al. 2015;
Zhao, Zhang, and Cichocki 2015; Lu et al. 2016; Yokota
and Hontani 2017; Yokota et al. 2019; Zheng et al. 2020).
By designing different structures of latent factors and different multi-linear operations among them, various tensor∗

Corresponding authors.
Copyright c 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

decompositions have been proposed and attracted considerable attention. Among them, the Tucker decomposition and
the CANDECOMP/PARAFAC (CP) decomposition as two
most classical decompositions have achieved great successin the past decade (Kolda and Bader 2009; Gandy, Recht,
and Yamada 2011; Liu et al. 2013, 2014; Zhao et al. 2016;
Yokota, Zhao, and Cichocki 2016; Li, Ye, and Xu 2017; Xieet al. 2018; Yao et al. 2019; He et al. 2019; Phan et al. 2020).
More recently, an increasing number of tensor networkbased tensor decompositions have emerged and shown great
ability to deal with higher-order, especially beyond thirdorder, tensors. One of the most representative among them isthe tensor train (TT) decomposition (Oseledets 2011), which
decomposes an N th-order tensor into N -2 third-order tensors located at intermediate and two matrices located at bothsides (see Figure 1(a)). Besides, from the first TT factor (matrix), each factor needs to conduct a multi-linear operation
with its next factor, until the last one (matrix). Subsequently,
as an extension of the TT decomposition, tensor ring (TR)decomposition (Zhao et al. 2016) replaced two matrices in
TT factors by third-order tensors and established an additional multi-linear operation between them (see Figure 1(b)).
Since TT and TR decompositions have the outstanding capability in super-compression and computational practicability, they have been employed in many applications, such as
signal restoration, compression and reconstruction, and image/video recovery (Bengua et al. 2017; Imaizumi, Maehara,and Hayashi 2017; Ding et al. 2019; Zhao et al. 2019; Yuan
et al. 2018; Yuan et al. 2019; Chen et al. 2020). Many ofthem can be regarded as a tensor completion (TC) problem,
which aims to complete a tensor from its partial observation.
However, there are two limitations to TT and TR decompositions. First, these two decompositions only establish an
operation/connection between adjacent two factors, rather
than any two factors, which leads to a limited characterization for correlations of tensors. Second, TT decomposition keeps the invariance only when the modes of the target
tensor make a reverse permuting, while TR decomposition
keeps the invariance only when the modes of the target tensor make a circular shifting or a reverse permuting. These
imply that these two decompositions are highly sensitive tothe permutation of tensor modes, leading to the inflexibilityof decompositions and applications.

I2

G1

G2

I3

R1

IN
...

R2

RN-1

I1

R2

Ik

...

I3

Rk,k+1

R2,N
G2... ...

X

I2

I2

R3

Gk

R2,k

R2,4

I4

Ik

Rk-1,k

R2,3
Ik

R4,N

R3,N

Rk-1

...

R4
G3

I3

RN-1,N

...

G2
...

...

I4

...

...

I3

I2

Rk
Gk

...

Ik

IN

I1

RN-1
...

...

X

I2

IN
GN

R1

IN

I1

RN

GN

...

(a) TT decomposition
G1

R1,N

R1,k
R 1 , 2 R 1 , 3R 1 , 4

I4
I1

IN
G1

GN

.

I1

...

Ik

...
..

...

X

G3

G4

...

IN

I1
I2

... R 4 , 5

R3,k
R3,4

G4

I3

I4

(b) TR decomposition

I4(c) FCTN decomposition

Figure 1: A graphical representation of TT, TR, and the proposed FCTN decompositions.
To tackle the above two limitations, we propose a fullyconnected tensor network (FCTN) decomposition, which
decomposes an N th-order tensor into a set of N th-order factors and establishes a multi-linear operation/connection between any two factors (see Figure 1(c)). The proposed FCTN
decomposition has the superior capability to characterize directly the intrinsic correlations between any two modes oftensors and is proved to be essentially invariable for any permutations of tensor modes. The main contributions of thispaper are summarized as three-folds:
1) We propose an FCTN decomposition, which breaks
through the limitations of TT and TR decompositions interms of correlation characterization and transpositional invariance.
2) We employ the FCTN decomposition to the TC problem and develop an efficient proximal alternating minimization (PAM)-based algorithm to solve it.
3) We theoretically demonstrate the convergence of thedeveloped algorithm by proving the sequence obtained by itglobally converges to a critical point (local minima).

2

Notations and Preliminaries

In this paper, we denote scalars, vectors, matrices,and tensors as x, x, X, and X , respectively. For an
N th-order tensor X ∈ RI1 ×I2 ×···×IN , we employ
X (i1 , i2 , · · · , iN ) to denote its (i1 , i2 , · · · , iN )th element.
The
qP Frobenius norm of X is defined as kX kF =2
i1 ,i2 ,··· ,iN |X (i1 , i2 , · · · , iN )| . For the sake of clarity,
we use X1:d to denote (X1 , X2 , · · · , Xd ).

3
3.1

defined as a tensor X~ n ∈ RIn1 ×In2 ×···×InN , which is generated by rearranging the modes of X in the order specified
by the vector n. We denote the corresponding operationand its inverse operation as X~ n = permute(X , n) and
X = ipermute(X~ n , n), respectively.
Definition 2 (Generalized Tensor Unfolding) Supposingthat X ∈ RI1 ×I2 ×···×IN is an N th-order tensor and thevector n is a reordering of the vector (1, 2, · · · , N ). The
generalized tensor unfolding of X is defined as a matrix


N
d
Y
Y
Ini .
Ini ,
X[n1:d ;nd+1:N ] = reshape1 X~ n ,i=1

We denote the corresponding operation and its inverse operation as X[n1:d ;nd+1:N ] = GenUnfold(X , n1:d ; nd+1:N ) and
X = GenFold(X[n1:d ;nd+1:N ] , n1:d ; nd+1:N ), respectively.
For example, the traditional mode-k unfolding (Kolda andBader 2009) of X is X[k;1,2,··· ,k−1,k+1,··· ,N ] , which is also
simply denoted as X(k) .
Definition 3 (Tensor Contraction) Supposing that vectors
n and m are the reordering of vectors (1, 2, · · · , N ) and(1, 2, · · · , M ), respectively; X ∈ RI1 ×I2 ×···×IN and Y ∈RJ1 ×J2 ×···×JM are two tensors satisfied Ini = Jmi with i =1, 2, · · · , d. The tensor contraction along the n1:d th-modesof X and the m1:d th-modes of Y yields an (N + M − 2d)thorder tensor
Ind+1 ×···×InN ×Jmd+1 ×···×JmM
1:d
Z = X ×m,
n1:d Y ∈ R
whose elements
Z(ind+1 ,· · ·, inN , jmd+1 ,· · ·, jmM ) =Ind
In1 In2
X
X X
 n
···
X~ (in1 ,· · ·, ind , ind+1 ,· · ·, inN )FCTN Decomposition

Basic Theory

in1 in2

Before proposing the FCTN decomposition, we first develop
several basic definitions and theorems.
Definition 1 (Generalized Tensor Transposition)
Supposing that X ∈ RI1 ×I2 ×···×IN is an N th-order tensor
and the vector n is a reordering of the vector (1, 2, · · · , N ).
The vector n-based generalized tensor transposition of X is

i=d+1

ind

~ m (in ,· · ·, in , jm ,· · ·, jm ) .
Y
1
M
d
d+1
Especially, here requires nd+1 < nd+2 < · · · < nN andmd+1 < md+2 < · · · < mM to guarantee the uniquenessof the tensor Z.
1

Matlab commands.

Furthermore, Theorem 1 delivers the relationship of thetensor contraction and the matrix multiplication.
Theorem 1 Supposing that X ∈ RI1 ×I2 ×···×IN and Y ∈RJ1 ×J2 ×···×JM are two tensors, we have1) XT
[n1:d ;nd+1:N ] = X[nd+1:N ;n1:d ] ;1:d2) Z = X ×m
n1:d Y ⇔Z[1:N−d;N−d+1:N+M−2d] = X[nd+1:N ;n1:d ] Y[m1:d ;md+1:M ] .
Here vectors n and m have the same setting as that in Definition 3.

3.2

FCTN Decomposition

Definition 4 (FCTN Decomposition) The FCTN decomposition aims to decompose an N th-order tensor X ∈RI1 ×I2 ×···×IN into a set of N th-order factor tensors
Gk ∈ RR1,k ×R2,k ×···×Rk−1,k ×Ik ×Rk,k+1 ×···×Rk,N with k =1, 2, · · · , N . More specifically, the element-wise form of the
FCTN decomposition can be expressed as
X (i1 , i2 , · · · , iN ) =
R1,2

R1,3

R1,N

R2,3

R2,N

X

X

X

X

X

···

r1,2 =1 r1,3 =1

···

r1,N =1 r2,3 =1

RN −1,N···r2,N =1

X

rN −1,N =1

G1 (i1 , r1,2 , r1,3 ,· · ·, r1,N )(1)G2 (r1,2 , i2 , r2,3 ,· · ·, r2,N )· · ·Gk (r1,k , r2,k ,· · ·, rk−1,k , ik , rk,k+1 ,· · ·, rk,N )· · ·GN (r1,N , r2,N ,· · ·, rN −1,N , iN ) .
Moreover, we denote
the FCTN decomposition as X =
=
FCTN(GFCTN {Gk }N
1 , G2 , · · · , GN ) and call the
k=1
vector collected by Rk1 ,k2 (1 ≤ k1 < k2 ≤ N and k1 , k2 ∈N+ ) as the FCTN-ranks.
To illustrate the FCTN decomposition vividly, Figure 1(c)gives a graphical representation of it. It is not hard to seethat for second-order tensors, the FCTN decomposition is
actually the matrix factorization and the FCTN-rank is actually the matrix rank. Furthermore, for higher-order tensors, any two FCTN factors Gk1 and Gk2 have an equal-sizedmode Rk1 ,k2 used to conduct the tensor contraction operation, which enables the FCTN decomposition to characterizeadequately the intrinsic correlations between any two modesof the target tensor. This indicates an essential advantage of
the FCTN decomposition over the TT and TR decompositions, which establish only the connection between adjacent
two factors, leading to a limited characterization for correlations of tensors. Besides, the FCTN decomposition can degenerate to the TT and TR decompositions by simply setting
the corresponding modes of factors to 1.
In second-order case, it is well known that the matrix factorization is essentially invariable under the transpositional
condition, i.e., X = G1 G2 ⇔ XT = GT2 GT1 . Naturally, it
is expected to extend this property to higher-order cases.
Theorem 2 (Transpositional Invariance) Supposing thatan N th-order tensor X has the following FCTN decomposition: X = FCTN(G1 , G2 , · · · , GN ). Then, its vectorn-based generalized tensor transposition X~n can be expressed as X~ n = FCTN G~nn1 , G~nn2 , · · · , G~nnN , where n =(n1 , n2 ,· · ·, nN ) is a reordering of the vector (1, 2, · · · , N ).
Theorem 2 illustrates another essential advantage of the
FCTN decomposition as compared with the TT and TR decompositions. More specifically, the FCTN decompositionis essentially invariable, no matter how to permute the modesof the target tensor. But TR decomposition keeps the invariance only when the modes of the target tensor make a circular shifting or a reverse permuting. And TT decomposition
keeps the invariance only when the modes of the target tensor make a reverse permuting.
The following theorem presents that the FCTN-ranks canbound the rank of all generalized tensor unfolding.
Theorem 3 Supposing that an N th-order tensor X can be
represented by Equation (1), the following inequality holds:
d
N
Y
 Y
Rni ,nj ,Rank X[n1:d ;nd+1:N ] ≤i=1 j=d+1

where Rni ,nj = Rnj ,ni if ni > nj and (n1 , n2 ,· · ·, nN ) is areordering of the vector (1, 2, · · · , N ).
Since the FCTN decomposition aims to characterize theintrinsic correlations between any two modes by establishing a connection between any two factors, the factors haveto be designed as N th-order tensors, which inevitably leads
to the increment of the storage cost as compared to TT and
TR decompositions. For an N th-order X ∈ RI×I×···×I ,whose FCTN-ranks are the same value R1 , the FCTN decomposition requires O(N IR1N −1 ) parameters to express it.
It seems to stay on the same order of magnitude with that of
the Tucker decomposition (O(N IR2 + R2N ) parameters).
But when we express real-world data, the required FCTNrank R1 is usually far less than Tucker-rank R2 , because
the FCTN decomposition uses R1N −1 to bound Tucker-rank
R2 (as shown in Theorem 3). This indicates that the FCTN
decomposition is superior to the Tucker decomposition regarding the storage cost2 .
Definition 5 (FCTN Composition) We call the process ofgenerating X by its FCTN factors Gk (k = 1, 2, · · · N )as the FCTN composition, which is also denoted as
FCTN {Gk }N
k=1 . Furthermore, if one of the factors Gt (t ∈{1, 2, · · · , N }) does not participate
 in the composition, we
denote it as FCTN {Gk }N
,
/G
.
t
k=1

Theorem 4 Supposing that X = FCTN {Gk }N
k=1 andMt = FCTN {Gk }N
k=1 , /Gt , we obtain that
X(t) = (Gt )(t) (Mt )[m1:N−1 ;n1:N−1 ] ,where 2i,
if i < t,
2i − 1, if i < t,mi =and ni =2i − 1, if i ≥ t,2i,
if i ≥ t.
Theorem 4 reveals the relationship between one FCTN
factor and the composition of the other factors. It is of great
importance to the computation of the FCTN decomposition
since computing one factor usually needs to fix the others.
2
More experimental evidence is provided in the supplementarymaterial, which is available at https://yubangzheng.github.io.

4

FCTN Decomposition-Based TC Method

Algorithm 1 PAM-Based Solver for the FCTN-TC Model.

4.1

Model and Solving Algorithm

1: Input: The incomplete tensor F ∈ RI1 ×I2 ×···×IN , theDue to space limitations, we only apply the FCTN decomposition to one representative task, i.e., TC, which aims to recover missing elements of a higher-order tensor from its an
incomplete observation. Giving an incomplete observation
F ∈ RI1 ×I2 ×···×IN of the target tensor X ∈ RI1 ×I2 ×···×IN ,the proposed FCTN decomposition-based TC (FCTN-TC)
model can be formulated as1
min kX − FCTN(G1 , G2 , · · · , GN )k2F + ιS (X ),(2)
X ,G 2where G = (G1 , G2 ,· · ·, GN ) and
0, if X ∈ S,
ιS (X ) :=with S := {X : PΩ (X −F) = 0}.
∞, otherwise,
Here Ω denotes the index of the known elements and PΩ (X )is a projection operator which projects the elements in Ω tothemselves and all others to zeros.
Since all optimization variables are coupled with eachother, we employ the framework of PAM (Attouch, Bolte,
and Svaiter 2013) to solve (2), whose solution can be obtained by alternately updatingn (s+1)
(s+1)
(s)

Gk
= argmin f (G1:k−1 , Gk , Gk+1:N , X (s) )



Gk


o
ρ
(s)
+ kGk −Gk k2F , k = 1, 2, · · ·, N, (3)


n2
o

 (s+1)ρX= argmin f (G (s+1) , X ) + kX −X (s) k2F ,2
X
where f (G, X ) is the objective function of (2) and ρ > 0 is
a proximal parameter.
1) Update Gk : According to Theorem 4, the Gk (k =1, 2,· · ·, N )-subproblems can be rewritten as

ρ
(s+1)
(s)
Gk
= argmink(Gk )(k) − (Gk )(k) k2F
2
Gk
 (4)
1 (s)
(s)
+ kX(k) −(Gk )(k) (Mk )[m1:N−1 ;n1:N−1 ] k2F ,
2

(s)
(s+1)
(s)
where Mk = FCTN G1:k−1 , Gk , Gk+1:N , /Gk , and vectors m and n have the same setting as that in Theorem 4.
The problem (4) can be directly solved as
(s+1)

(Gk
)(k) =
 (s)

(s)
(s)
(5)
X(k) (Mk )[n1:N−1 ;m1:N−1 ] +ρ(Gk )(k)
 (s)
−1
(s)
(Mk )[m1:N−1 ;n1:N−1 ] (Mk )[n1:N−1 ;m1:N−1 ] +ρI ,
(s+1)

(s+1)

and Gk  = GenFold (Gk)(k) , k; 1, · · · , k − 1, k +1, · · · , N .
2) Update X : The X -subproblem has the following
closed-form solution since it is a least square problem:(s+1) N 
FCTN {Gk}k=1 +ρX (s)
(s+1)
X
= PΩc
+PΩ (F). (6)1+ρ

index Ω, the maximal FCTN-rank Rmax , and ρ = 0.1.
2: Initialization: s=0, smax
=
1000,
(0)
X
=
F, the initial FCTN-rank R=(0)max{ones1 (N (N − 1)/2, 1), Rmax − 5}, and Gk =rand1 (R1,k , R2,k , · · · , Rk−1,k , Ik , Rk,k+1 , · · · , Rk,N ),where k = 1, 2, · · · , N .
3: while not converged and s < smax do(s+1)
4:
Update Gk
via (5).
5:Update X (s+1) via (6).
(s+1)
6:Let R = min{R + 1, Rmax } and expand Gk
if
kX (s+1) − X (s) kF /kX (s) kF < 10−2 .
7:

Check the convergence condition:kX (s+1) − X (s) kF /kX (s) kF < 10−5 .

8:Let s = s + 1.
9: end while
10: Output: The reconstructed tensor X .

The whole process of the PAM-based solver for the
FCTN-TC model is summarized in Algorithm 1. Especially,
if the observed tensor F is complete (no missing elements),
the way for iteratively solving the factors Gk in the proposed
FCTN-TC method can be regarded as a strategy for obtaining its one FCTN decomposition.

4.2

Computational Complexity Analysis

For an N th-order incomplete tensor F ∈ RI×I×···×I ,we analyze the computational complexity of the proposed FCTN-TC method by simply setting the FCTNranks Rk1 ,k2 (1 ≤ k1 < k2 ≤ N and k1 , k2 ∈ N+ )as the same value R. The computational cost lies on two
part: 1) updating Gk (k = 1, 2, · · · , N ) and 2) updating
X . In (5), updating Gk involves the FCTN composition,
the matrix multiplication, and the matrix inversion, which
PN
costs O N k=2 I k Rk(N −k)+k−1 + N I N −1 R2(N −1) +
N R3(N −1) . In (6), updating X requires the FCTNPN
k k(N −k)+k−1
composition costing O. Therek=2 I R
fore, the whole computational complexity at each iteraPNtion in the Algorithm 1 is O N k=2 I k Rk(N −k)+k−1 +N I N −1 R2(N −1) +N R3(N −1) .

4.3

Convergence Analysis

In this section, we provide a theoretical guarantee for theconvergence of the developed PAM-based algorithm.
Theorem 5 The sequence {G (s) , X (s) }s∈N obtained by the
Algorithm 1 globally converges to a critical point of (2).
To prove the Theorem 5, we only need to justify that thefollowing four conditions hold (Attouch, Bolte, and Svaiter
2013):
1) G (s) and X (s) (s ∈ N) are bounded;(Original) (Transpositional)
TT-TC (PAM)

10-3

6

(Original) (Transpositional)
TR-TC (PAM)

Fourth-order tensor

4

10-3

(Original) (Transpositional)
FCTN-TC (PAM)

Fifth-order tensor

5

3

RSE

RSE

4
3

2

2

1
1
80%

60%

80%

40%

60%

40%

MR

MR

Figure 2: Reconstructed results on the synthetic dataset withdifferent permutations.
2) f (G, X ) is a proper lower semi-continuous function;3) f (G, X ) satisfies the K-Ł property at {G (s) , X (s) }s∈N ;4) {G (s) , X (s) }s∈N satisfies Lemmas 1 and 2.
Lemma 1 (Sufficient Decrease) Letting {G (s) , X (s) }s∈Nbe the sequence obtained by the Algorithm 1, then it satisfiesρ (s+1) (s) 2
(s+1)
(s)
−Gk kFf (G1:k , Gk+1:N , X (s) )+ kGk
2
(s+1)
(s)
≤ f (G1:k−1 , Gk:N , X (s) ), k = 1, 2,· · ·, N ;ρ
f (G (s+1), X (s+1) )+ kX (s+1)−X (s) k2F ≤ f (G (s+1), X (s) ).
2
Lemma 2 (Relative Error) Letting {G (s) , X (s) }s∈N be thesequence obtained by the Algorithm 1, then there exists(s+1)
Ak∈ 0 and A(s+1) ∈ ∂X ιS (X (s+1) ) satisfied
(s+1)

kAk

(s+1)

+∇Gk h(G1:k(s), Gk+1:N , X (s) )kF(s+1)≤ ρkGk(s)−Gk kF , k = 1, 2,· · ·, N ;kA(s+1) +∇X h(G (s+1) ,X (s+1) )kF ≤ ρkX (s+1)−X (s) kF ,
 2
where h(G, X ) = 12 kX −FCTN {Gk }N
k=1 kF .
The detailed proof for the above four conditions is presented in the supplementary materials.

5

Numerical Experiments

We test the performance of the proposed FCTN-TC method3
by conducting synthetic data and real data experiments. The
missing ratio (MR) is defined as the ratio of the number ofmissing elements and the total elements.

5.1

Synthetic Data Experiments

This section mainly aims to verify the superiorities of the
proposed FCTN decomposition over the TT and TR decompositions by contrasting the performance of their corresponding TC methods, i.e., FCTN-TC, TT-TC, and TRTC. All methods are solved by PAM to get rid of the influence of the algorithm. Since TT decomposition is a special case of TR and FCTN decompositions, we generate
synthetic tensors by the TT composition of TT factors,
3

The code is available at https://yubangzheng.github.io.

DatasetMR

Observed
HaLRTC
TMac
news
t-SVD
TMacTT
TRLRF
FCTN-TC
Observed
HaLRTC
TMac
containet-SVD
TMacTT
TRLRF
FCTN-TC
Observed
HaLRTC
TMac
elephants
t-SVD
TMacTT
TRLRF
FCTN-TC
Observed
HaLRTC
TMac
bunny
t-SVD
TMacTT
TRLRF
FCTN-TC
Observed
HaLRTC
TMac
HSV
t-SVD
TMacTT
TRLRF
FCTN-TC

95%

90%

80%

8.714914.49025.09225.07024.69922.55826.3924.596918.61726.94128.81428.13930.63130.8053.849916.65126.75321.81025.91827.12027.7806.4291
14.56125.46421.55226.25227.74928.3378.415712.00831.15135.32836.47837.35243.2568.950318.50727.03528.13027.49227.82329.523
4.831521.55626.14234.91231.28232.51237.3264.084720.33428.64827.25228.88028.36130.8356.663819.12828.16926.09429.51229.03432.2308.650622.14036.74940.37941.56141.79648.1759.460722.46029.77831.40231.54631.44733.0485.342125.19132.53339.72237.08838.32442.9744.594624.81331.01030.97532.23232.13334.3917.173623.39630.52530.34433.09633.22436.135
9.159429.00041.66345.80146.58146.21152.701Meantime (s)—36.738911.1474.807465.75891.96473.50—34.5281224.471.510450.70640.41412.72—38.541500.7063.994204.64592.13455.71—32.882779.7866.294264.15652.03468.25—15.45693.06530.533131.314776.5501.03

Table 1: The PSNR values and the running times of all utilized methods on the CV and HSV datasets.
sampled from uniform distribution U (0, 1), for the sake offairness. The testing data includes a fourth-order tensor ofsize 20 × 20 × 20 × 20 and a fifth-order tensor of size
12 × 12 × 12 × 12 × 12, whose TT-ranks are (10, 80, 10)
and (8, 48, 48, 8), respectively. Besides, for each data, wetest two permutations, i.e., its original ordering and one generalized transposition (n are (2, 4, 1, 3) and (2, 4, 1, 3, 5) for
fourth-order and fifth-order tensors, respectively). The relative error between the reconstructed tensor and the groundtruth, i.e., RSE = kX − Xtrue kF /kXtrue kF , is adopted toevaluate the performance of different methods. The methodology for selecting the missing elements is purely random
sampling. The hyper-parameters needed to adjust in the proposed FCTN-TC method only involve the maximal FCTNranks, i.e., Rkmax(1 ≤ k1 < k2 ≤ N and k1 , k2 ∈ N+ ), which
1 ,k2
are simply set as the same value.
Figure 2 shows the reconstructed results of different meth-Observed

0.9

Ground truth

1

0.8

0.9

0.7

FCTN-TC

0.8

0.6

0.5

TRLRF

0.7

0.6

0.4

TMacTT

0.5

0.3

t-SVD

0.4

0.2

0.3

0.1

TMac

0.2

0.1

0

0

HaLRTC

1

Figure 3: Reconstructed results on two testing CVs with MR=90%. From top to bottom: the odd-numbered rows are the visual
results at the 1st frame of the CV containe and the 35th frame of the CV bunny, respectively; the even-numbered rows are thecorresponding residual images average over three color channels.
ods on the synthetic data under different MRs, where theRSE value under each case is averaged over the values
obtained by 50 independent tests. We observe that 1) the
performance of the proposed FCTN-TC method is pronouncedly robust to different permutations, while that of TTTC and TR-TC are sensitive; and 2) the proposed FCTN-TC
method always achieves the lowest RSE values among threemethods under different datasets, MRs, and permutations.
This is because the rearranging of tensor modes shifts thecorrelation among them (e.g., the correlation between thefirst and second modes shifts to the first and third modes),leading to the change in the performance of TT and TR
decomposition-based methods. But owing that the proposed
FCTN decomposition can characterize the correlations between any two modes and is essentially invariable for tensor
transposition, the FCTN-TC method obtains the best and robust results. These testing results provide empirical evidence
for the fore theoretical analysis regarding the superiorities of
the FCTN decomposition.

5.2

Real Data Experiments

This section mainly aims to test the performance of the proposed FCTN-TC method on two types of real data by contrasting it with the state-of-the-art methods based on different tensor decompositions, including HaLRTC (Liu et al.
2013), TMac (Xu et al. 2015), t-SVD (Zhang and Aeron2017), TMacTT (Bengua et al. 2017), and TRLRF (Yuanet al. 2019). All hyper-parameters involved in all comparedmethods are manually adjusted to achieve optimal performance following the authors’ recommendations and codes.
For instance, In TMac, TMacTT, and TRLRF, the hyperparameters are mainly Tucker-rank, TT-rank, and TR-rank.

We adjust them in a certain range. In HaLRTC and t-SVD,
the hyper-parameters are mainly the threshold for the singular value thresholding operation, which is selected from thecandidate set {10−6 , 10−5 , 10−4 , 10−3 , 10−2 , 10−1 }.
Video Data Completion. The testing video dataset includes four color videos4 (CVs) of size 144 × 176 × 3 × 50
(spatial height×spatial width×color channel×frame) and a
hyperspectral video5 (HSV) of size 60 × 60 × 20 × 20 (spatial height×spatial width×band×frame) (Mian and Hartley2012). For each data, we test three MRs: 80%, 90%, and95%, and employ the peak signal-to-noise ratio (PSNR) as
the quantitative metric. The methodology for selecting themissing elements is purely random sampling and the pixel
values of the testing data are normalized into [0, 1].
For the proposed FCTN-TC method, on CV dataset,max
max
we set R1,4
and R2,4
as the same value since they
all directly characterize the correlation between the spatial modes (height and width, respectively) and the temmax
maxmax
poral mode. And we set R1,3
, R2,3, and R3,4
as thesame value, since the third mode represents the color
max
max
max
channel. Therefore, only R1,2
, R1,3, and R1,4
need toadjust, which are recommended to select from the candidate sets {10, 15, 20, 25, 30, 35, 40, 45, 50}, {2, 3}, and{4, 5, 6, 7, 8}, respectively. On the HSV dataset, we simply set Rkmax(1 ≤ k1 < k2 ≤ 4 and k1 , k2 ∈ N+ ) as the
1 ,k2
same value recommended to select from the candidate set{4, 5, 6, 7, 8}.
Table 1 reports the PSNR values and the running timesof all utilized methods under different MRs on the testing
4
5

The data is available at http://trace.eas.asu.edu/yuv/.
The data is available at http://openremotesensing.net/kb/data/.

Observed

HaLRTC

TMac

t-SVD

TMacTT

TRLRF

FCTN-TC

Ground truth

00:02

00:02

00:02

00:02

00:02

00:02

00:02

00:02

04:00

04:00

04:00

04:00

04:00

04:00

04:00

04:00

08:00

08:00

08:00

08:00

08:00

08:00

08:00

08:00

12:00

12:00

12:00

12:00

12:00

12:00

12:00

12:00

16:00

16:00

16:00

16:00

16:00

16:00

16:00

16:00

20:00

20:00

20:00

20:00

20:00

20:00

20:00

24:00

24:00
1

3

5

7

9 11 13 15 17 19

24:00
1

3

5

7

9 11 13 15 17 19

24:00
1

3

5

7

9 11 13 15 17 19

24:00
1

3

5

7

9 11 13 15 17 19

24:00
1

3

5

7

9 11 13 15 17 19

20:00

24:00
1

3

5

7

9 11 13 15 17 19

24:00
1

3

5

7

9 11 13 15 17 19

00:02

00:02

00:02

00:02

00:02

00:02

00:02

00:02

04:00

04:00

04:00

04:00

04:00

04:00

04:00

04:00

08:00

08:00

08:00

08:00

08:00

08:00

08:00

08:00

12:00

12:00

12:00

12:00

12:00

12:00

12:00

12:00

16:00

16:00

16:00

16:00

16:00

16:00

16:00

16:00

20:00

20:00

20:00

20:00

20:00

20:00

20:00

24:00

24:00
1

3

5

7

9 11 13 15 17 19

RSE=0.6370

3

5

7

9 11 13 15 17 19

24:00
1

RSE=0.0989

57

9 11 13 15 17 19

3

5

7

9 11 13 15 17 19

RSE=0.1016

3

5

7

9 11 13 15 17 1957

9 11 13 15 17 197

9 11 13 15 17 19

1

3

5

7

9 11 13 15 17 19

24:00
1

3

5

7

9 11 13 15 17 19

1800

—

1

1600

0.9

1400

5

RSE=0.0553

RSE=0.0766

0.8

1200

3

3

20:00

24:00
1

0.7

1000

0.6

800

24:00
1

RSE=0.0613

0.5

600

24:00
1

0.4

400

0.3

200

3

RSE=0.0669

0.2

0.1

0

0

24:00
1

1

2000

Figure 4: Reconstructed results on the traffic flow dataset with MR=40%. The first and the second rows are the results on the
2nd day and the corresponding residual results, respectively.
CVs and HSV. In terms of effect (PSNR), we see that the
proposed FCTN-TC method compares favorably to the othermethods on both the testing CVs and HSV. Especially on the
HSV, the FCTN-TC method is ahead by about 5dB of PSNR
compared to the second-best method. In terms of efficiency(running time), we observe that on the CV dataset, the meanof the running time of the FCTN-TC method stays roughlyon the same order of magnitude with that of the compareddecomposition-based methods, i.e., TMac, TMacTT, andTRLRF. The main reason is that although the computational
complexity of the FCTN-TC method is theoretically higher,
the setting rank of it for obtaining the optimal result is usually lower than that of the compared ones.
Furthermore, Figure 3 shows the reconstructed spatial images and their corresponding residual images (the absolutedifference between the reconstructed image and the groundtruth) of two CVs. From Figure 3, we observe that the results
obtained by the proposed FCTN-TC method are markedly
superior to those by the compared ones, especially for therecovery of local details, such as ripples in the CV containe
and grasses in the CV bunny.
Traffic Data Completion. This experiment was realizedwith traffic data provided by the NeCS team from the Grenoble Traffic Lab6 . The testing traffic flow dataset is collectedfrom 19 road segments within 31 days from January 1, 2019,
to January 31, 2019, and the time interval is 2 minutes. The
size of it is 30×24×31×19 (minute×hour×day×segment).
In the traffic dataset, the damage to detectors usually leads
to the data missing over some time. Therefore, we consider
the slice (made up of the first and second modes) missing problem. The MR is set to be 40% and the RSE is
employed as the quantitative metric. We simply set Rkmax
1 ,k2(1 ≤ k1 < k2 ≤ 4 and k1 , k2 ∈ N+ ) as the same value, i.e., 5.
In Figure 4, we present the reconstructed results on the
2nd day and the RSE value of the whole dataset. As observed, the proposed FCTN-TC method achieves the best
approximation to the ground truth among different methods.
This illustrates the superior of the proposed FCTN decom6

Homepage: http://gtl.inrialpes.fr/.

position on the slice missing problem.
In summary, the above experimental results imply the superior capability of the proposed FCTN decomposition for
capturing the intrinsic information of higher-order tensors,
as compared to other tensor decompositions.

6

Conclusion

This paper proposed a novel tensor decomposition scheme,i.e., the FCTN decomposition, which factorizes an N thorder tensor into a set of N th-order factors with full connections. The FCTN decomposition showed its outstanding capability to adequately characterize the correlations between
any two modes of tensors and was proved to be essentiallytranspositional invariable. Meanwhile, an FCTN-TC model
was proposed with an efficient PAM-based solver, whose
convergence was theoretically guaranteed. Experimental results demonstrated that the FCTN-TC method delivered an
overall better performance than the compared ones.
Similar to CP and TR decompositions (Kolda and Bader
2009; Zhao et al. 2016), the proposed FCTN decomposition
faces difficulty in finding the optimal FCTN-ranks. In the future, we will work to solve this challenging problem, deeply
explore the essential feature of the FCTN factors, and employ the FCTN decomposition to more applications.

Acknowledgments
This work was supported by NSFC (Grant Nos. 61772003,
61876203, 62071132, 12001446), Key Projects of Applied Basic Research in Sichuan Province (Grant No.
2020YJ0216), Projects of Applied Basic Research in
Sichuan Province (Grant No. 21YYJC3042), and JSPS
KAKENHI (Grant No. 20H04249). The authors would liketo thank the CNRS/INRIA NeCS team for providing traffic
data from the Grenoble Traffic Lab.

References
Anandkumar, A.; Ge, R.; Hsu, D.; Kakade, S. M.; and Telgarsky,
M. 2014. Tensor Decompositions for Learning Latent Variable
Models. Journal of Machine Learning Research 15(80): 2773–
2832.

Attouch, H.; Bolte, J.; and Svaiter, B. F. 2013. Convergence ofDescent Methods for Semi-Algebraic and Tame Problems: Proximal Algorithms, Forward-Backward Splitting, and Regularized
Gauss-Seidel Methods. Mathematical Programming 137(1): 91–
129.

Phan, A.; Cichocki, A.; Oseledets, I.; Calvi, G. G.; Ahmadi-Asl,S.; and Mandic, D. P. 2020. Tensor Networks for Latent Variable Analysis: Higher Order Canonical Polyadic Decomposition.
IEEE Transactions on Neural Networks and Learning Systems
31(6): 2174–2188.

Bengua, J. A.; Phien, H. N.; Tuan, H. D.; and Do, M. N. 2017. Efficient Tensor Completion for Color Image and Video Recovery:
Low-Rank Tensor Train. IEEE Transactions on Image Processing
26(5): 2466–2479.

Xie, Q.; Zhao, Q.; Meng, D.; and Xu, Z. 2018. KroneckerBasis-Representation Based Tensor Sparsity and Its Applications
to Tensor Recovery. IEEE Transactions on Pattern Analysis andMachine Intelligence 40(8): 1888–1902.

Chen, Y.; Huang, T.-Z.; He, W.; Yokoya, N.; and Zhao, X.-L.
2020. Hyperspectral Image Compressive Sensing Reconstruction Using Subspace-Based Nonlocal Tensor Ring Decomposition. IEEE Transactions on Image Processing 29: 6813–6828.

Xu, Y.; Hao, R.; Yin, W.; and Su, Z. 2015. Parallel Matrix Factorization for Low-Rank Tensor Completion. Inverse Problems andImaging 9(2): 601–624.

Cong, F.; Lin, Q.-H.; Kuang, L.-D.; Gong, X.-F.; Astikainen, P.;
and Ristaniemi, T. 2015. Tensor Decomposition of EEG Signals:
A Brief Review. Journal of Neuroscience Methods 248: 59–69.
Ding, M.; Huang, T.-Z.; Ji, T.-Y.; Ji, T.-Y.; Zhao, X.-L.; and Yang,
J.-H. 2019. Low-Rank Tensor Completion Using Matrix Factorization Based on Tensor Train Rank and Total Variation. Journalof Scientific Computing 81(2): 941–964.
Gandy, S.; Recht, B.; and Yamada, I. 2011. Tensor Completionand Low-n-Rank Tensor Recovery via Convex Optimization. Inverse Problems 27(2): 025010.
He, W.; Yao, Q.; Li, C.; Yokoya, N.; and Zhao, Q. 2019. NonLocal Meets Global: An Integrated Paradigm for Hyperspectral
Denoising. In IEEE Conference on Computer Vision and Pattern
Recognition, 6868–6877.
Imaizumi, M.; Maehara, T.; and Hayashi, K. 2017. On Tensor
Train Rank Minimization : Statistical Efficiency and Scalable Algorithm. In Advances in Neural Information Processing Systems,
3930–3939.
Kolda, T. G.; and Bader, B. W. 2009. Tensor Decompositions andApplications. SIAM Review 51(3): 455–500.
Li, X.; Ye, Y.; and Xu, X. 2017. Low-Rank Tensor Completion
with Total Variation for Visual Data Inpainting. In Proceedingsof the AAAI Conference on Artificial Intelligence, 2210–2216.
Liu, J.; Musialski, P.; Wonka, P.; and Ye, J. 2013. Tensor Completion for Estimating Missing Values in Visual Data. IEEE Transactions on Pattern Analysis and Machine Intelligence 35(1): 208–
220.

Yao, Q.; Kwok, J. T.; Wang, T.; and Liu, T.-Y. 2019. LargeScale Low-Rank Matrix Learning with Nonconvex Regularizers.
IEEE Transactions on Pattern Analysis and Machine Intelligence
41(11): 2628–2643.
Yokota, T.; and Hontani, H. 2017. Simultaneous Visual Data
Completion and Denoising Based on Tensor Rank and Total Variation Minimization and Its Primal-Dual Splitting Algorithm. In
IEEE Conference on Computer Vision and Pattern Recognition,
3843–3851.
Yokota, T.; Kawai, K.; Sakata, M.; Kimura, Y.; and Hontani, H.
2019. Dynamic PET Image Reconstruction Using Nonnegative
Matrix Factorization Incorporated With Deep Image Prior. In
Proceedings of the IEEE/CVF International Conference on Computer Vision.
Yokota, T.; Zhao, Q.; and Cichocki, A. 2016. Smooth PARAFAC
Decomposition for Tensor Completion. IEEE Transactions on
Signal Processing 64(20): 5423–5436.
Yuan, L.; Cao, J.; Zhao, X.; Wu, Q.; and Zhao, Q. 2018. HigherDimension Tensor Completion via Low-Rank Tensor Ring Decomposition. In Asia-Pacific Signal and Information Processing
Association Annual Summit and Conference, 1071–1076.
Yuan, L.; Li, C.; Mandic, D.; Cao, J.; and Zhao, Q. 2019. Tensor
Ring Decomposition with Rank Minimization on Latent Space:
An Efficient Approach for Tensor Completion. In Proceedings of
the AAAI Conference on Artificial Intelligence, 9151–9158.
Zhang, Z.; and Aeron, S. 2017. Exact Tensor Completion Using
T-SVD. IEEE Transactions on Signal Processing 65(6): 1511–
1526.

Liu, Y.; Shang, F.; Fan, W.; Cheng, J.; and Cheng, H. 2014. Generalized Higher-Order Orthogonal Iteration for Tensor Decomposition and Completion. In Advances in Neural Information Processing Systems, 1763–1771.

Zhao, Q.; Sugiyama, M.; Yuan, L.; and Cichocki, A. 2019. Learning Efficient Tensor Representations with Ring-Structured Networks. In IEEE International Conference on Acoustics, Speechand Signal Processing, 8608–8612.

Lu, C.; Feng, J.; Chen, Y.; Liu, W.; Lin, Z.; and Yan, S. 2016.
Tensor Robust Principal Component Analysis: Exact Recovery of
Corrupted Low-Rank Tensors via Convex Optimization. In IEEE
Conference on Computer Vision and Pattern Recognition, 5249–
5257.

Zhao, Q.; Zhang, L.; and Cichocki, A. 2015. Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination. IEEE Transactions on Pattern Analysis and Machine Intelligence 37(9): 1751–1763.

Mian, A.; and Hartley, R. 2012. Hyperspectral Video Restoration
Using Optical Flow and Sparse Coding. Optics Express 20(10):10658–10673.
Mu, C.; Huang, B.; Wright, J.; and Goldfarb, D. 2014. Square
Deal: Lower Bounds and Improved Relaxations for Tensor Recovery. In Proceedings of Machine Learning Research, volume 32, 73–81.
Oseledets, I. V. 2011. Tensor-Train Decomposition. SIAM Journal on Scientific Computing 33(5): 2295–2317.

Zhao, Q.; Zhou, G.; Xie, S.; Zhang, L.; and Cichocki, A. 2016.
Tensor Ring Decomposition. arXiv preprint arXiv:1606.05535 .
Zhao, Q.; Zhou, G.; Zhang, L.; Cichocki, A.; and Amari, S. 2016.
Bayesian Robust Tensor Factorization for Incomplete Multiway
Data. IEEE Transactions on Neural Networks and Learning Systems 27(4): 736–748.
Zheng, Y.-B.; Huang, T.-Z.; Zhao, X.-L.; Jiang, T.-X.; Ma, T.H.; and Ji, T.-Y. 2020. Mixed Noise Removal in Hyperspectral
Image via Low-Fibered-Rank Regularization. IEEE Transactions
on Geoscience and Remote Sensing 58(1): 734–749.