Robust Tensor Decomposition via Orientation Invariant Tubal Nuclear Norms
Andong Wang,1,2,3 Chao Li,2 Zhong Jin,*1,4 Qibin Zhao*2,3
1School of Computer Science & Engineering, NJUST 2 Tensor Learning Unit, RIKEN AIP 3 School of Automatation, GDUT
4Key Laboratory of Intelligent Perception and System for High-Dimensional Information of Ministry of Education, NJUSTCorresponding authors: Zhong Jin (zhongjin@njust.edu.cn), Qibin Zhao (qibin.zhao@riken.jp)

Abstract
Low-rank tensor recovery has been widely applied to computer vision and machine learning. Recently, tubal nuclear norm
(TNN) based optimization is proposed with superior performance as compared to other tensor nuclear norms. However,one major limitation is its orientation sensitivity due to lowrankness strictly defined along tubal orientation and it cannot
simultaneously model spectral low-rankness in multiple orientations. To this end, we introduce two new tensor norms
called OITNN-O and OITNN-L to exploit multi-orientational
spectral low-rankness for an arbitrary K-way (K ≥ 3) tensors. We further formulate two robust tensor decomposition
models via the proposed norms and develop two algorithms as
the solutions. Theoretically, we establish non-asymptotic error
bounds which can predict the scaling behavior of the estimation error. Experiments on real-world datasets demonstrate thesuperiority and effectiveness of the proposed norms.

Introduction
Tensor decomposition has become a paradigm in modern
multi-way data analysis. Due to various reasons like sensor
failures, occlusion in videos, or abnormalities, the multi-way
data are often corrupted by noises and gross corruptions. For
example, the embedded noises in hyper-spectral image isprobably a mixture of small dense noises and sparse grosscorruptions (Zhao et al. 2015a). To tackle both small noises
and gross corruptions, the robust tensor decomposition (RTD)(Gu, Gui, and Han 2014) is studied to robustify traditional
tensor decompositions like CANDECOMP/PARAFAC (CP)decomposition (Harshman 1970) and Tucker decomposition(Tucker 1966) which are sensitive to gross corruptions.
In many real-world applications, most variation of themulti-way data can be linearly dominated by a relatively
small number of latent factors due to intrinsic correlations andredundancy. Thus, such data can be well approximated by a“low rank” tensor. Thanks to the multiple definitions of tensor
rank function, such as CP rank (Harshman 1970), Tucker
rank (Tucker 1966), TT rank (Oseledets 2011) and Tubal
rank (Kilmer et al. 2013), multi-way data can be modeledwith different types of low-rank structures.
To recover a low-rank tensor, one natural way is to solve
the rank minimization problem (RMP) (Liu et al. 2013).
Copyright c 2020, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

Unfortunately, RMP is NP-hard in general for matrices(2-way tensors) (Candès and Tao 2010) and even harder for higher-way tensors (Hillar and Lim 2009). In lowrank matrix estimation, matrix nuclear norm is proposedas the convex envelop of rank function (Fazel 2002) for
tractable algorithms. Motivated by the great success of matrix nuclear norm, its tensor extensions have been extensively studied, like tensor trace norm (Yuan and Zhang 2016),
overlapped Schatten-1 norm (SNN) (Tomioka et al. 2011;
Liu et al. 2013), latent Schatten norm (LatentNN) (Tomioka and Suzuki 2013), squared nuclear norm (SqNN) (Muet al. 2014) and tubal nuclear norm (TNN) (Zhang et al.
2014). Among existing tensor nuclear norms1 , TNN is induced by the tensor singular value decomposition (t-SVD)(Kilmer et al. 2013) and has shown superior performancein various applications, such as image/video inpainting/denoising (Zhou and Feng 2017; Zhang and Aeron 2017;
Lu et al. 2019), clustering (Xie et al. 2017) and WiFi
fingerprint-based indoor localization (Liu et al. 2016b).
In real multi-way data like images and videos, there is anubiquitous “spatial-shifting” correlation making such data
spatial-temporally smooth (Liu et al. 2016a). From a signal processing standpoint, smoothness in original domain
often reflects the existence of some simple patterns in spectral domain (Yokota et al. 2018). TNN is quite suitable tocapture such simple patterns since it exploits spectral lowrankness for 3-way tensors. However, by computing nuclear
norms of frontal slices after 1D-DFT on the mode-3 fibers, it is strictly orientation sensitive and fails to capture thecomplex intra-mode and inter-mode correlations in multipleorientations for higher-order tensors. To improve the limited representation ability and flexibility of TNN in modelingmulti-orientational correlations, we propose two orientation
invariant tensor norms for K-way (K ≥ 3) tensors and apply
them to RTD. Main contributions of this paper are three-fold:
1) We propose two tensor norms via a novel 3d unfolding operation on K-way tensors, which are orientation invariant,thus can be exploited for the multi-orientational spectral
low-rankness.
2) The new norms are employed to formulate RTD as two
1

In this paper, “tensor nuclear norms” refer to tensor extensionsof matrix nuclear norm instead of the nuclear norm induced by CP
decomposition (Yuan and Zhang 2016).

convex models, together with corresponding algorithms.
3) Error bounds of the proposed models are analyzed andprovided, which enables us to predict approximately thescaling behavior of the estimation error.

Notations and Preliminaries
Notations. Matrices and tensors are denoted by uppercase
boldface, and calligraphy letters, respectively. Let [n] :={1, · · · , n}, ∀n ∈ N+ . Without specification, a K-way tensor
refers to a tensor of 3 or higher ways, i.e., K ≥ 3. If the sizeof a tensor is not given explicitly, then it is in Rd1 ×···×dK . Fora matrix MPwith singular values σi ’s, define its nuclear normkMk∗ := i σi and spectral norm kMk := maxi σi . Given
T ∈ Rd1 ×···×dK , define its l0 -norm kTkl0 := kvec(T )k0 ,l1 -norm kTkl1 := kvec(T )k1 , F-norm kTkF := kvec(T )k2 ,and l∞ -norm kTkl∞ := kvec(T )k∞ , where vec(·) denotes
the vectorization (Kolda and Bader 2009).
For notationQ
al simplicity, let dK+1 = d1 , D = k∈[K] dk , d\k =p√p D/(dk dk+1 ), d˜k =dk+1 dk + d\k , ∀k ∈ [K].
Given T ∈ Rd1 ×d2 ×d3 , let T(i) := T (:, :, i) denotes its ith
frontal slice. We use c, c0 , c1 etc. to denote constants whose
values can vary from line to line. Other notations are introduced when they first appear.

As proved in (Lu et al. 2019), TNN is the convex envelop of tensor average rank in unit tensor spectral norm ball.
Thus, TNN encourages a low average rank which means lowrankness in spectral domain according to Definition 3. It is
strictly orientation sensitive in the sense that just mode-3
fibers are chosen to perform DFT, thus only spectral lowrankness along orientation of mode-3 can be exploited. Since
TNN is orientation sensitive and defined for 3-way tensors, it
has limited representation ability for higher-way tensors.

Orientation Invariant TNNs
To overcome the drawbacks of TNN, we first propose a newtensor 3d-unfolding operation as follows.
Definition 4 (mode-(k, t) 3d-unfolding). For different k, t ∈[K], the mode-(k, t) 3d-unfolding of T ∈ Rd1 ×···×dK is a
3-way tensor T[k,t] ∈ Rdk ×(D/(dk dt ))×dt obtained by thefollowing two steps (see Fig. 1.).
000First, permute T to Z ∈ Rd1 ×d2 ×···×dK whose 1st andK th modes are respectively the k th and tth modes of T , withthe rest modes permuted circularly. Second, reshape Z to
−1 −1
T[k,t] ∈ Rdk ×(Ddk dt )×dt obeying the equation as follows(T[k,t] )i1 jiK = Zi1 i2 ···iK
PK−1
Pl−1
where j = 1 + l=2 (il − 1)Jl with Jl = m=2 d0m .

Tensor singular value decomposition
We briefly recall the tensor singular value decomposition.
Definition 1. (Kilmer et al. 2013). Given T1 ∈ Rd1 ×d2 ×d3
and T2 ∈ Rd2 ×d4 ×d3 , their t-product T = T1 ∗ T2 ∈Rd1 ×d4 ×d3 is a tensor whose (i, j)th tube T (i, j, :) =Pd2
k=1 T1 (i, k, :) • T2 (k, j, :), where • is the circular convolution.
With notions like tensor transpose, orthogonal tensor, andf-diagonal tensor (Kilmer et al. 2013), t-SVD can be defined.
Definition 2. (Kilmer et al. 2013). Any tensor T ∈Rd1 ×d2 ×d3 has a tensor singular value decomposition as
T = U ∗ S ∗ V >,where U ∈ Rd1 ×d1 ×d3 , V ∈ Rd2 ×d2 ×d3 are orthogonal tensors, and S ∈ Rd1 ×d2 ×d3 is an f -diagonal tensor. The tubal
rank of T is defined as the number of non-zero tubes of S:
ranktb (T ) := # i S(i, i, :) 6= 0 .
(2)
Definition 3. (Lu et al. 2016). Given T ∈ Rd1 ×d2 ×d3 , let
Te be its Fourier version2 in Cd1 ×d2 ×d3 . The tensor averagerank rankavg (·), tubal nuclear normk·k? of T are defined as
the averaged rank and nuclear norm of frontal slices of Te :rankavg (T ) :=

d3
d3
1 X
1 X
e(i) ), kTk? :=e(i)k∗ ,rank(TkT
d3 i=1d3 i=1

whereas tensor spectral normk·k is the largest spectral norm:
(i)

e k}.
kTk := max {kTi∈[d3 ]

2

Figure 1: Illustration of 3d-unfolding.

(1)

The Fourier version Te is obtained by performing 1D-DFT on
all tubes of T , i.e., Te = fft(T , [], 3) ∈ Cd1 ×d2 ×d3 in Matlab.

Intuitively, by viewing a K-way tensor T as a “(K-1)-wayarray T” of size d1 × d2 × · · · × dt−1 × dt+1 × · · · dK whose
entries are mode-t tubes, the mode-(k, t) 3d-unfolding T[k,t]can also be analogously viewed as a “mode-k unfolding” of−1
T with size dk × (Dd−1
k dt ) whose entries are mode-t tubes.
Generally, the mode t of this 3d-unfolding can be any mode
except k. In the sequel we simply set t = k + 1, such thatmode t traverses all the K orientations when k slides from
1 to K, by which some orientation invariant measures canbe defined. For simplicity, let T[k] := T[k,k+1] and call it themode-k 3d-unfolding3 of T .
Based on 3d-unfolding, two tensor ranks are defined.
Definition 5. The Orientation Invariant Tubal Rank (OITR)~rt and Orientation Invariant Average Rank (OIAR) ~ra of any
T ∈ Rd1 ×···×dK are defined as the following vectors:~rt (T ) := ranktb (T[1] ), · · · , ranktb (T[K] ) > ∈ RK ,(3)~ra (T ) := rankavg (T[1] ), · · · , rankavg (T[K] ) > ∈ RK .
3

Using circular order of modes, let dK+1 = d(K+1)modK = d1 .

(a) OITNN-OkTk?o(b) OITNN-LkTk?ι

Figure 2: Illustration of two OITNNs for 3D tensors T ∈Rd1 ×d2 ×d3 . (a): OITNN-O encourages simultaneously low
tubal rank structure in all orientations; (b): OITNN-L models
T as a mixture of three low tubal rank tensors {L(k) }.
As shown in Eq. (3), OITR serves as a complexity measurein the original domain, whereas the OIAR measures lowrankness in the spectral domain. They have the following
relationship with the classical Tucker rank ~rTucker .
Lemma 1. It holds for any tensor T ∈ Rd1 ×···×dK that~ra (T ) ≤ min{~rt (T ),~rTucker (T )},(4)
where the partial order “≤” is defined entry-wisely.
Lemma 1 indicates that low OITR or Tucker rank resultsin low OIAR. Thus, the low OIAR assumption is weaker thanthe popular low Tucker rank assumption. By relaxing averagerank to its convex envelop in each orientation, we naturally
define the following norm.
Definition 6. The Overlapped Orientation Invariant Tubal
Nuclear Norm (OITNN-O) of T ∈ Rd1 ×···×dK is defined as:
XK(5)
kTk?o :=
wkkT[k]k? ,k=1
Pwhere wk ’s are positive weights satisfying k wk = 1.
OITNN-O encourages a low OIAR structure, which means
low-rankness in spectral domain of all orientations. Thus in
the original domain, it models a data tensor as simultaneously
low tubal rank in all orientations (See Fig. 2(a)). It differsfrom SNN (Liu et al. 2013) which only considers low Tucker
rank. As special cases, if K = 3, OITNN-O degenerates totriple TNN (Wei et al. 2018); If K = 3, (w1 , w3 ) → 0, thenit approximates TNN.
Although the assumption of low OIAR is weaker than low
Tucker rank, it may still be strict for some real data tensors.
In (Tomioka and Suzuki 2013), it is observed that a latent
Schatten norm (LatentNN) induced by a mixture model ismore suitable than SNN for tensors only low rank in certain
modes. Motivated by this, we define the latent OITNN torelax the low OIAR assumption.
Definition 7. The Latent Orientation Invariant Tubal Nuclear Norm (OITNN-L) of T ∈ Rd1 ×···×dK is defined as
kTk?ι := P inf(k) =T
kL

K
X

(k)

vkkL[k] k? ,

(6)

k=1

P
where vk ’s are non-negative weights satisfying k vk = 1,(k)and L[k] is the mode-k 3d-unfolding of latent component
L(k) , ∀k ∈ [K].

OITNN-L seeks K latent components {L(k) } to minimize
a weighted sum of their TNNs in each orientation. Thus, it
models T as a mixture of K low tubal rank tensors in original domain (see Fig. 2(b)). According to Definitions 6
and 7, both OITNN-O and OITNN-L can exploit spectral
low-rankness in all orientations and are invariant to circular permutations. Since TNN has been shown to be more
powerful than the matrix nuclear norm (Zhang et al. 2014;
Lu et al. 2019), we expect that OITNN-O and OITNN-L
outperform SNN and LatentNN in some applications respectively. This expectation will be verified by experiments onreal datasets in the experiment section.
We now give the dual norms of OITNN-O and OITNN-L.
Lemma 2. The dual norms of k·k?o and k·k?ι , denoted byk·k∗?o andk·k∗?ι respectively, are given as follows:no(k)kTk∗?o := inf P X (k) =T maxk wk−1kX[k] k ,
k
(7)
XK
∗
kTk?ι :=
vk−1kT[k]k.
k=1

The dual norms play key roles in the statistical analysis of
OITNN-based RTD models.

Robust Tensor Decomposition via OITNNs
Observation model
Suppose we observe Y ∈ Rd1 ×···×dK by the following model
Y = L∗ + S ∗ + E,
∗

(8)

∗

where L is the true low-rank tensor, S stores entry-wisely
sparse corruptions, and tensor E represents dense small noise(see Fig. 3 (Zhao et al. 2015b)). The goal of RTD is to recoverL∗ and S ∗ from Y. If E = 0, RTD degenerates to the TRPCA(Lu et al. 2019); If S ∗ = 0, it becomes the noisy tensor
decomposition (Tomioka and Suzuki 2013).

Figure 3: Observation model of RTD.

Incoherence conditionsFirst, to guarantee separability of low-rank L∗ and sparseS ∗ , we suppose L∗ satisfies the non-spiky condition withparameter α (Agarwal, Negahban, and Wainwright 2012;
Klopp, Lounici, and Tsybakov 2017):kL∗kl∞ ≤ α.

(9)

(k)∗

Second, let {L} be any latent components obtained
while computingkL∗k?ι in Eq. (6). Then, the signal L∗ canbe written as
XK
(10)
L∗ =
L(k)∗ .
k=1

For separability of latent tensors L(k)∗ ’s, an incoherence
condition with parameter β is further assumed to hold:(k)∗kL[l] k ≤ β d˜l , ∀l 6= k ∈ [K],

(11)

p
√
p 
where d˜l = dl+1 dl + d\l . The motivation of Eq. (11)is to force each latent component L(k)∗ to be low tubal rank
only in mode-k 3d-unfolding, and behave like a Gaussian
random tensor4 in any mode-l 3d-unfolding (l 6= k).

Proposed RTD models
Using the proposed tensor norms and the l1 -norm to encourage multi-orientational spectral low-rankness and sparsity
respectively, we propose the following two models for RTD:
Model I: RTD-OITNN-O
min l(L, S) + λokLk?o + µokSkl1 ,
L,S

(12)

s.t. kLkl∞ ≤ α.
Model II: RTD-OITNN-L
X
X(k)min l(
L(k) , S) + λι
vkkL[k] k? + µιkSkl1{L(k) },S

k

k

X
(l)
s.t. kL(k)kl∞ ≤ α, kL[k]k ≤ β d˜k , ∀l 6= k,k(13)where λo , µo , λι , µι denote regularization parameters, squareloss l(L, S) = kY − L − Sk2F /2 is the data fitting term. ModelI explicitly uses OITNN-O as the regularizer of L, whereas
Model II implicitly adopts OITNN-L with incoherent latentcomponents {L(k) }.

Statistical Performance
We analyze statistical performance of the proposed models.
Let (L̂o , Ŝo ) and ({L̂(k) }, Ŝι ) be any solution to Problem (12)and Problems (13), respectively. We establish both deterministic and non-asymptotic bounds on the estimation errors, i.e.,
Eo , Eι , Eιcom (defined in Table 1), of the low-rank componentL∗ and the sparse component S ∗ in their sum.

Theorem 1 indicates that once parameters (λo , µo ) exceed
certain quantities of the noise E, estimation error of ModelI can be upper bounded linear by the OITR of L∗ and thesparsity of S ∗ .
Theorem 2. If λι ≥ 2 maxk {kEk∗?ι + vk−1 (K − 1)β d˜k } andµι ≥ 2(kEkl∞ + 2α) in Problem (13), then it holds that:X
Eιcom ≤ c3 λ2ι
vk2 rιk + c4 µ2ι s,kEι ≤ c3 λ2ι min vk2 rok + c4 µ2ι s.
kTheorem 2 shows that when (λι , µι ) exceed some thresholds in terms of E, estimation error Eιcom involving the latentcomponents {L(k) } is upper bounded by the “latent tubal
ranks rιk ” of L∗ and the sparsity of S ∗ , whereas the error Eι
for (L∗ , S ∗ ) is bounded by the “minimal” OITR of L∗ andthe sparsity of S ∗ .

Non-asymptotic bounds
For a typical setting where the noise tensor E represents thetensor of i.i.d. N (0, σ 2 ) entries, we have the following twotheorems.
P
Theorem √3. If parameters λo = 2σK −2 k (d˜k /wk ) andµo = 8σ log D + 16α in Problem (12), then with highprobability it holds thatEo ≤c1 σ 2 X d˜k 2 X p o 2
wk rk + c2 (σ 2 log D + α2 )s.
K4wkk

Theorem√4. If parameters λι = cσ maxk {d˜k /vk } andµι = 8σ log D + 16Kα in Problem (13), then with highprobability it holds that:d˜k 2 X 2 ιvk rk + c6 (σ 2 log D + α2 )s,Eιcom ≤ c5 σ 2 max{ }kvkkd˜k 2Eι ≤ c5 σ 2 max{ } min vk2 rok + c6 (σ 2 log D + α2 )s.
kkvk
To understand Theorems 3 and 4 intuitively, we have thefollowing remark whose correctness is verified in the experiment section.
Remark 1. Given a K-way cubical tensor L∗ ∈ Rd×d×···×d ,suppose its OITR is (ro1 , · · · , roK ). Letting parameters wk =vk = 1/K, ∀k ∈ [K], then we have the following bounds onthe entry-wise estimation error with high probability:EoEι- σ 2 (ro + s log D), and- σ 2 (rι + s log D),
D
D
(14)
2
P p
where ro = K −1 k rok /d and rι = mink {rιk /d} act
as the “averaged” and “minimal” OITR complexities of thesignal L∗ , respectively, and s = s/D is the sparse ratio of
the corruption S ∗ .
As discussed in Remark 1, OITNN-L tends to find theorientation with lowest tubal rank, whereas OITNN-O considers the tubal rank in all orientations. The upper bounds in
Theorems 1-4 are consistent with the intuition that RTD forcomplex L∗ (with higher OITR) and denser S ∗ is harder. We
give the following remark on the identifiability issue in our
analysis.


Table 1: List of some notations

Error of (L∗ , S ∗ ) by Model I
OITR of true tensor L∗

Error of (L∗ , S ∗ ) by Model II
Error of ({L(k)∗ }, S ∗ )Tubal rank of component L(k)∗Sparsity of corruption S ∗Eo = kL̂o − L∗k2F +kŜo − S ∗k2F
~ro = (r o1 , · · · , r oK ), r ok = ranktb (L∗[k] )PEι = k k L̂(k) − L∗k2F +kŜ − S ∗k2F
∗ 2
kL̂(k) − L(k)∗k2
F +kŜι − S kF
k
(k)∗
ι
ι
ι
~r = (r 1 , · · · , r k ), r k = ranktb (L[k] )s = kS ∗kl0

Eιcom =P

ι

Deterministic bounds
When E in the observation model (8) represents any noise, webound the estimation error in the following theorems where
the dual norms in Lemma 2 are used.
Theorem 1. If λo ≥ 2kEk∗?o and µo ≥ 2(kEkl∞ + 2α) in
Problem (12), then any solution (L̂o , Ŝo ) satisfies:X
p 2
Eo ≤ c1 λ2o
wk rok + c2 µ2o s.
k4Note that a random d1 × d2 × d3 tensor with i.i.d. standard
Gaussian entries has full tubal rank
probability
and its√ with√ high√tensor spectral norm scales as O
d3 ( d1 + d2 ) (see Lemma
8 in the supplementary material).

kRemark 2. In the noiseless setting (i.e., E = 0), the proposederror bounds do not vanish, which means our analysis cannot
guarantee exact recovery. This is because the incoherence
conditions in our analysis are less strict than the ones definedin terms of singular vectors (Huang et al. 2015; Lu et al.
2019) which intrinsically ensure separability between lowrank and sparse components.

G0 ∈ Rp1 ×···×pK . Then, we repeat
the recursive opera
tion Gk = F−1
(U
∗
F
G
),
∀k
∈ [K − 1], where
k
k
k−1
k
Uk ∈ Rdk ×pk ×pk+1 are also standard Gaussian tensors
×···×pK
and Gk ∈ Rn1 ×···×nk ×pk+1. We further generate−1
GK = FK (UK ∗ FK GK−1 ) with standard Gaussian tensor
UK ∈ RdK ×pK ×d1 . Finally, we let L∗ = GK /kGKkl∞ .

Optimization Algorithms
We develop two algorithms to solve Model I and Model II
respectively. By adding auxiliary variables to Problem (12),
we obtainX
minl(L, S) + λo
wkkKkk? + µokTkl1 + δαl∞ (K)L,S,T ,K,{Kk }k

Kk = L[k] , ∀k; T = S; K = L,s.t.

(a) Eo vs ro with s = 0.1(b) Eo vs s with ro = 0.4478(c) Eι vs rι with s = 0.1(d) Eι vs s with rι = 0.275

where δαl∞ (K) is the indicator function of tensor l∞ -normball whose value is 0 ifkKkl∞ ≤ α, and +∞ otherwise.
Adding auxiliary variables to Problem (13) 5 also yields
X

L(k) , S)+λι

X

vkkKkk? +µokTkl1 +δαl∞ (K)

min

l(

s.t.

Kk = L[k] , ∀k; T = S; K =S,T ,K,{L(k) },{Kk }

k

(k)

k

X
k

L(k) .

Then we continue solving Model I and Model II by
ADMM presented in Algorithm 1 and Algorithm 2 respectively, where all the sub-problems can be solved inclosed forms6 . In each single iteration of Algorithms 1
and 2, the main cost comes from updating the low tubal
rank components which involves FFT, IFFT and d3 SVDs of d1 × d2 matrices for tensors of size d1 × d2 × d3 .
Hence Algorithms P
1 and 2 have per-iteration
 complexity−1
O KD log D + D k min(dk , d−1
k dk+1 D , which is thesame order as ADMM-based algorithms for SNN (Gu, Gui,and Han 2014) and LatentNN (Tomioka and Suzuki 2013).
The convergence of Algorithms 1 and 2 naturally holds since
Problems (12) and (13) can be reformulated as the standard
form of the two-block ADMM framework (Boyd et al. 2011).

Experiments
Correctness of the proposed error bounds
To validate the correctness of Theorem 3 and Theorem 4, we
conduct simulations to check whether the proposed upperbounds in Eq. (14) can predict the scaling behavior of theestimation error.
Generation of L∗ . We generate the low-rank tensor L∗ ∈Rd1 ×···×dK in the following manner. Given K random integers pk < dk , ∀k ∈ [K], we first generate a standard
Gaussian tensor (i.e. tensors with i.i.d. N (0, 1) entries)
5
The constraints on tensor spectral norm in Problem (13) areremoved to get rid of K(K − 1) auxiliary variables in decoupling
the constraints, and K(K − 1) projections on tensor spectral normball, which is rather space and time-consuming.
6
Due to space limitation, the description of Algorithms 1 and 2
are shown in the supplementary material. Matlab implementations
can be found in https://qibinzhao.github.io

Figure 4: The element-wise estimation errors versus the rankcomplexity and sparse ratio for tensors in R40×40×40 .
We form the sparse corruption tensor S ∗ by choosing
its support uniformly at random according to (Lu et al.
2019). We generate the noise tensor E with√entries drawing i.i.d. from N (0, σ 2 ) with σ = ckL∗kF / D to keep a
constant signal noise ratio. For simplicity, we consider cubical tensors, i.e., d1 = · · · = dK = d. We test tensors ofsize 40 × 40 × 40. We randomly choose pk ∈ {2, 3, · · · , 10}
to generate L∗ . We generate the corruption tensor S ∗ withsparsity s = sD where s ∈ {0.02 : 0.02 : 0.3} and form thenoise tensor E with noise level c = 0.1. We run the proposed
Algorithm 1 and Algorithm 2 and then compute the estimation errors Eo /D and Eι /D for 500 random choices of pk ’s.
We computed the OITR (ro1 , · · · , roK ) of L∗ , since it is notequal to (p1 , · · · , pK ) in general. We then compute ro andrι in Eq. (14). We will check whether the errors Eo /D andEι /D scale like a1 ro + b1 s and a2 rι + b2 s, respectively, withsome constants a1 , a2 , b1 , b2 .
Fig. 4 shows the results of Eo /D versus ro and s, andι
E /D versus rι and s by keeping other variables fixed. From
Fig. 4, we can see that the errors Eo /D and Eι /D have approximately linear scaling behavior with respect to ro and s,
and rι and s, respectively. Thus, it can be said that the proposed bounds can approximately predict the scaling behaviorof the estimation error.

Effectiveness of the proposed OITNNs
We evaluate effectiveness of the proposed norms in comparison with other nuclear norm-based models on real datasets.
The competitor norms include SNN (Liu et al. 2013), LatentNN (Tomioka and Suzuki 2013), SqNN (Mu et al. 2014),

TNN (Zhang and Aeron 2017), twist TNN (t-TNN) (Hu et al.
2017) and matrix nuclear norm (NN) (Candès and Tao 2010).
We first conduct RTD on color images and color videos, andthen carry out color image inpainting to further demonstrate
the power of the proposed norms. RTD models based on the
aforementioned norms are formulated by replacing OITNNO in Problem (12) and the corresponding optimization problems are solved by ADMM via our own implementationsin Matlab. We use the Peak Signal Noise Ratio (PSNR) to
measure the recovery quality.
Robust image recovery In this experiment, nine color images of size 256 × 256 × 3 are tested (see Fig. 5(a)). Given acolor image M ∈ Rd1 ×d2 ×3 , we randomly pick the supportof S ∗ with probability s and add i.i.d. Gaussian noise√ withstandard deviation σ = cσ0 , where σ0 = kMkF / 3d1 d2 .
We test two cases with (s, c) = (0.05, 0.1) and (0.15, 0.15).
Given a color image and a corruption level, we test 10 times
and report the averaged PSNR.
Parameters for OITNN-O are set as w1 : w2 : w3 = a1 :1 : a1 , with a1 ∈ [0.1, 0.5], and OITNN-L v1 : v2 : v3 = 1 :a2 : 1 with a2 ∈ [0.025, 0.055]. The weight parameters α of
SNN are chosen to satisfy α1 : α2 : α3 = 1 : 1 : 0.01 as suggested in (Liu et al. 2013).
√ The “sparse/low-rank” parameter√
ratio µ/λ of NN is 1/ d2 (Candès et al. 2011), and 1/ 3d2
for SqNN, TNN and t-TNN. We tune the “sparse/low-rank”
parameter ratio for OITNN-O and OITNN-L. Other parameters of the algorithms are manually tuned.

bridge-far, carphone, claire, coastguard, container and foreman. Due to computational limitation, we use the first 32
frames of each video, resulting in seven 144 × 176 × 3 × 32
tensors. We conduct robust video recovery against sparse corruptions and Gaussian noise with (s, c) = (0.15, 0.15) and(0.2, 0.2). NN is tested for matrices of size (144·172·3)×32;
SqNN is tested for matrices of size (144 · 32) × (176 · 3);
TNN and t-TNN are tested on 3 (the channel number) tensors of size (144 × 176 × 32). The “sparse/low-rank” parameter ratio of NN, SqNN, TNN and t-TNN are set by
the suggestion of RPCA and TRPCA (Candès et al. 2011;
Lu et al. 2019). We tune other parameters for better performances in most cases. The PSNR values are reported in Fig. 6.
It can be seen that the proposed OITNNs-based models havebetter performances thanks to their flexibility in exploiting
the multi-orientation correlations in color videos.

(a) (s, c) = (0.15, 0.15)(b) (s, c) = (0.2, 0.2)

Figure 6: Quantitative comparison on seven color videos.
(a) Nine test images.

(b) (s, c) = (0.05, 0.1)(c) (s, c) = (0.15, 0.15)

Figure 5: Test images and quantitative comparison of RTD
models based on different norms on color images.
For quantitative comparison, PSNR values on the nine images are reported in Fig. 5(b)-(c). An visual example is shownin Row 1 of Fig. 7 for qualitative evaluation. As illustrated
in Fig. 7, the proposed norms obtain higher visual quality
than the competitor norms. According to Figs. 5 and 7, theproposed OITNN-O and OITNN-L have better performancein most cases on color images.
Robust video recovery The performance comparison iscarried out on the widely used seven YUV videos7 : akiyo,
7
The videos are available from https://sites.google.com/site/
subudhibadri/fewhelpfuldownloads.

Robust recovery of UGV data Experiments on a dataset 8
for unmanned ground vehicle (UGV) are also conducted. Thisdataset contains a sequence of gray camera images and point
cloud data acquired from a Velodyne HDL-64E LiDAR. A
scenario containing 32 frames (Frame Nos. 65-96) is selected.
The camera data is resized to a tensor of size 128 × 256 ×
32, and the point cloud data is formatted into two tensors(distance data tensor and intensity data tensor) sized 64 ×
436 × 32. We conduct RTD against sparse corruptions andGaussian noise with (s, c) = (0.15, 0.15) and (0.3, 0.2). The
parameters are tuned for better performances in most cases.
The PSNR values are reported in Table 2. We can see that the
proposed norms perform better on UGV data.
Table 2: The quantitative comparison on the dataset for UGV.
Norms
NN
SNN
TNN
t-TNN
SqNN
LatentNNOITNN-OOITNN-L(s, c) = (0.15, 0.15)
Camera Distance Intensity
23.12
24.49
21.61
24.29
25.32
22.21
25.54
25.86
22.88
25.19
25.92
23.13
23.45
24.71
21.86
23.61
24.67
21.97
26.12
25.97
23.31
25.79
26.35
23.28

(s, c) = (0.3, 0.2)
Camera Distance Intensity
21.43
23.41
20.91
22.55
24.49
21.56
23.36
25.08
22.08
23.22
25.37
22.35
21.75
23.77
21.38
21.89
23.79
21.45
24.08
25.42
22.41
23.87
25.79
22.45

8
Scenario B and Scenario B-additional dataset from http://www.
mrt.kit.edu/z/publ/download/velodynetracking/dataset.html

(a) Observation(b) OITNN-O(c) OITNN-L(d) TNN(e) SNN(f) LatentNN

Figure 7: Visual performances of the proposed OITNN-O and OITNN-L compared with tightly related TNN, SNN and LatentNN.
Row 1: robust image recovery with corruption ratio s = 0.05 and noise level c = 0.1. Row 2: image inpainting with 90% random
missing entries. Row 3: image inpainting with missing columns and rows (total missing ratio 85%).
Color image inpainting To further show the effectivenessof the proposed OITNNs, we also apply them to the classicalimage inpainting problem. Specifically, we consider two settings of missing patterns on the nine test images in Fig. 5(a).
In Setting I, 90% of the entries are missing randomly, whereas in Setting II some rows are first missing and columns of
the rest rows are then randomly sampled with a total missing
ratio of 85%. Note that Setting II is very challenging since
all the three matricizations of an input image suffer frommissing columns which can hardly be recovered by matrix
low-rankness in original domain.
For qualitative comparison, inpainting examples in Setting
I and Setting II are shown in Row 2 and Row 3 of Fig. 7,
respectively. The quantitative comparison in PSNR is presented in Fig. 8. Thank to their ability in exploiting multiorientational low-rankness in spectral domain, the proposed
OITNNs outperform the competitors in most cases, especially when the missing pattern conflicts with low-rankness inoriginal domain (like Setting II).

(a) Setting I(b) Setting II

Figure 8: Quantitative comparison in image inpainting.

Conclusions
Two new tensor norms for general K-way (K ≥ 3) tensors are first defined to exploit the low-rankness in spectral
domain for all orientations. We then adopt them to robust
tensor recovery and rigorously establish upper bounds onthe estimation error. Correctness of the error bounds is verified through simulation study. Experiments on real datasets
demonstrate the effectiveness of the proposed norms. A maindrawback of the proposed models is that we cannot automatically determine the optimal tuning parameters, and it isinteresting to develop a suitable tool for parameter tuning(like (Zhao et al. 2015b)) as future work. Future research
directions also include developing fast algorithms for the
proposed models using techniques like (Wang et al. 2019;
Wang, Jin, and Tang 2020).

Acknowledgments
The authors thank Jin Wang, Bo Wang and Dongxu Wei
for their long time support. This work is partially supported by National Natural Science Foundation of China[Grant Nos. 61872188, U1713208, 61972204, 61672287,
61861136011, 61773215, 61703209, 61972212]. This work
is also partially supported by JSPS KAKENHI (Grant No.
17K00326), and the National Key Research and Development Program Intergovernmental International Science andTechnology Innovation Cooperation Project (MOST-RIKEN)
under Grant 2017YFE0116800.

References
Agarwal, A.; Negahban, S.; and Wainwright, M. J. 2012.
Noisy matrix decomposition via convex relaxation: Optimal

rates in high dimensions. The Annals of Statistics 1171–1197.
Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; and Eckstein, J.
2011. Distributed optimization and statistical learning via
the alternating direction method of multipliers. Foundations
and Trends R in Machine Learning 3(1):1–122.
Candès, E. J., and Tao, T. 2010. The power of convex relaxation: near-optimal matrix completion. IEEE TIT 56(5):2053–
2080.
Candès, E. J.; Li, X.; Ma, Y.; and Wright, J. 2011. Robust
principal component analysis? Journal of the ACM 58(3):11.
Fazel, M. 2002. Matrix rank minimization with applications.
Ph.D. Dissertation, PhD thesis, Stanford University.
Gu, Q.; Gui, H.; and Han, J. 2014. Robust tensor decomposition with gross corruption. In NIPS 2014, 1422–1430.
Harshman, R. A. 1970. Foundations of the parafac procedure:
Models and conditions for an “explanatory” multi-modal
factor analysis.
Hillar, C. J., and Lim, L. 2009. Most tensor problems are
np-hard. Journal of the ACM 60(6):45.
Hu, W.; Tao, D.; Zhang, W.; Xie, Y.; and Yang, Y. 2017.
The twist tensor nuclear norm for video completion. IEEE
TNNLS 28(12):2961–2973.
Huang, B.; Mu, C.; Goldfarb, D.; and Wright, J. 2015. Provable models for robust low-rank tensor completion. Pacific
Journal of Optimization 11(2):339–364.
Kilmer, M. E.; Braman, K.; Hao, N.; and Hoover, R. C. 2013.
Third-order tensors as operators on matrices: A theoreticaland computational framework with applications in imaging. SIAM Journal on Matrix Analysis and Applications
34(1):148–172.
Klopp, O.; Lounici, K.; and Tsybakov, A. B. 2017. Robust
matrix completion. Probability Theory and Related Fields
169(1-2):523–5642.
Kolda, T. G., and Bader, B. W. 2009. Tensor decompositions
and applications. SIAM Review 51(3):455–500.
Liu, J.; Musialski, P.; Wonka, P.; and Ye, J. 2013. Tensor
completion for estimating missing values in visual data. IEEE
TPAMI 35(1):208–220.
Liu, X. Y.; Aeron, S.; Aggarwal, V.; and Wang, X. 2016a.
Low-tubal-rank tensor completion using alternating minimization. arXiv preprint arXiv:1610.01690.
Liu, X.; Aeron, S.; Aggarwal, V.; Wang, X.; and Wu, M.
2016b. Adaptive sampling of rf fingerprints for fine-grainedindoor localization. IEEE Transactions on Mobile Computing
15(10):2411–2423.
Lu, C.; Feng, J.; Chen, Y.; Liu, W.; Lin, Z.; and Yan, S. 2016.
Tensor robust principal component analysis: Exact recoveryof corrupted low-rank tensors via convex optimization. In
CVPR 2016, 5249–5257.
Lu, C.; Feng, J.; Chen, Y.; Liu, W.; Lin, Z.; and Yan, S. 2019.
Tensor robust principal component analysis with a new tensor
nuclear norm. IEEE TPAMI 1–1.
Mu, C.; Huang, B.; Wright, J.; and Goldfarb, D. 2014. Squaredeal: Lower bounds and improved relaxations for tensor recovery. In ICML 2014, 73–81.

Oseledets, I. V. 2011. Tensor-train decomposition. SIAM
Journal on Scientific Computing 33(5):2295–2317.
Tomioka, R., and Suzuki, T. 2013. Convex tensor decomposition via structured schatten norm regularization. In NIPS
2013, 1331–1339.
Tomioka, R.; Suzuki, T.; Hayashi, K.; and Kashima, H. 2011.
Statistical performance of convex tensor decomposition. In
NIPS 2011, 972–980.
Tucker, L. R. 1966. Some mathematical notes on three-mode
factor analysis. Psychometrika 31(3):279–311.
Wang, A.; Song, X.; Wu, X.; Lai, Z.; and Jin, Z. 2019. Latent
schatten tt norm for tensor completion. In ICASSP 2019,2922–2926. IEEE.
Wang, A.; Jin, Z.; and Tang, G. 2020. Robust tensor decomposition via t-svd: Near-optimal statistical guarantee andscalable algorithms. Signal Processing 167:107319.
Wei, D.; Wang, A.; Feng, X.; Wang, B.; and Wang, B. 2018.
Tensor completion based on triple tubal nuclear norm. Algorithms 11(7).
Xie, Y.; Tao, D.; Zhang, W.; Liu, Y.; Zhang, L.; and Qu,
Y. 2017. On unifying multi-view self-representations forclustering by tensor multi-rank minimization. IJCV (4):1–23.
Yokota, T.; Erem, B.; Guler, S.; Warfield, S. K.; and Hontani,
H. 2018. Missing slice recovery for tensors using a low-rank
model in embedded space. arXiv preprint arXiv:1804.01736.
Yuan, M., and Zhang, C. H. 2016. On tensor completion via
nuclear norm minimization. Foundations of Computational
Mathematics 16(4):1–38.
Zhang, Z., and Aeron, S. 2017. Exact tensor completion
using t-svd. IEEE TSP 65(6):1511–1526.
Zhang, Z.; Ely, G.; Aeron, S.; Hao, N.; and Kilmer, M.
2014. Novel methods for multilinear data completion andde-noising based on tensor-svd. In CVPR 2014, 3842–3849.
Zhao, Q.; Meng, D.; Kong, X.; Xie, Q.; Cao, W.; Wang, Y.;
and Xu, Z. 2015a. A novel sparsity measure for tensor
recovery. In ICCV 2015, 271–279.
Zhao, Q.; Zhou, G.; Zhang, L.; Cichocki, A.; and Amari, S.-I.
2015b. Bayesian robust tensor factorization for incomplete
multiway data. IEEE TNNLS 27(4):736–748.
Zhou, P., and Feng, J. 2017. Outlier-robust tensor pca. In
CVPR 2017, 3938–3946.