Euclidean-Norm-Induced Schatten-p Quasi-Norm Regularization for Low-Rank Tensor Completion and Tensor Robust Principal Component Analysis
Authors: Jicong Fan
Lijun Ding
Chengrun Yang
Zhao Zhang
Madeleine Udell
Venue: Accepted by TMLR ()

Abstract: The nuclear norm and Schatten-$p$ quasi-norm are popular rank proxies in low-rank matrix recovery. However, computing the nuclear norm or Schatten-$p$ quasi-norm of a tensor is hard in both theory and practice, hindering their application to low-rank tensor completion (LRTC) and tensor robust principal component analysis (TRPCA). In this paper, we propose a new class of tensor rank regularizers based on the Euclidean norms of the CP component vectors of a tensor and show that these regularizers are monotonic transformations of tensor Schatten-$p$ quasi-norm. This connection enables us to minimize the Schatten-$p$ quasi-norm in LRTC and TRPCA implicitly via the component vectors. The method scales to big tensors and provides an arbitrarily sharper rank proxy for low-rank tensor recovery compared to the nuclear norm. On the other hand, we study the generalization abilities of LRTC with the Schatten-$p$ quasi-norm regularizer and LRTC with the proposed regularizers.  The theorems show that a relatively sharper regularizer leads to a tighter error bound, which is consistent with our numerical results. Particularly, we prove that for LRTC with Schatten-$p$ quasi-norm regularizer on $d$-order tensors, $p=1/d$ is always better than any $p>1/d$ in terms of the generalization ability. We also provide a recovery error bound to verify the usefulness of small $p$ in the Schatten-$p$ quasi-norm for TRPCA. Numerical results on synthetic data and real data demonstrate the effectiveness of the regularization methods and theorems.

Published in Transactions on Machine Learning Research (01/2023)
Euclidean-Norm-Inducee Q Quasi-Norm Regular- ization for Low-Rank Tensor Completion and Tensor Robust Principal Component Analysis
Jicong Fan
Junjicong@cuhk.cuu edu.cr
The Chinese University of Hong Kong, Shenchen, and Shenchen Research Institute of Big Data
Lijun Ding
ljding@@ww.cc edu
University of Washington
Chengrun Yang
cy438@cornell.ed edu
Cornell University
Zhao Zhang Hefei University of Technology
eszzungg@gmaillccom com
Madeleine Udell
udellSstan ford. edu
Stanford University
Reviewed on OpenReview: https: /ttp://ppepe openreview. net/ forum? id= Vd=Gr88800
Abstract
The nuclear norm and Schatten-p quasi-norm are popular rank proxies in low-rank matrix recovery. However, computing the nuclear norm or Schatten-p quasi-norm of a tensor is hard in both theory and practice, hindering their application to low-rank tensor completion (LRTC) and tensor robust principal component analysis (TRPCA). In this paper, we propose a new class of tensor rank regularizers based on the Euclidean norms of the CP component vectors tensor and show that these regularizers are monotonic transformations of tensor Schatten-p quasi-norm. This connection enables us to minimize the Schatten-p quasi-non norm in LRTC and TRPCA implicitly via the component vectors. The method scales to big tensors and provides arbitrarily sharper rank proxy for low-rank tensor recovery compared to the muclear norm. On the other hand, study the generalization abilities of LRTC with the Schatten-p quasi-norm regularizer and LRTC with the proposed regularizers. The theorems show that a relatively sharper regularizer lcads to tighter error bound, which is consistent with our numerical results. Particularly, we prove that for LRTC with Schatten-p quasi- norm regularizer on d-order tensors, p = 1/d is always better than any p > 1/d terms of the generalization ability. We also provide a recovery error bound to verify the uscfulness of small p in the Schatten-p quasi-norm for TRPCA. Numerical results on synthetic data and real data demonstrate the effectiveness of the regularization methods and theorems.
1
Introduction
Low-rank tensor completion (LRTC)
(Gandy ct al] 201 Acar of all, 2011: Liu all 2012 Romera-
&
PonLil, 2033; Kressner el. all 2014 Yuan & Zhang 2016 Cheng el all 2016 Zhou el all, 2017:
pt
al
20TES:
Ghadermarzy et al. 20P im A Motaa 2121: Wimalaammee & Mamitsuka
2021 Yang et all
2021:
Far
2022). as a high-order generalization of low-rank matrix completion (LRMC) (Candès Recht
Hamii 20E, Pan Chow, 2017). aims to recover the missing entries of low-rank tensor. One may
organize LRTC methods into different. categories according to the types of decomposition model, e.g., CP

---

Published in Transactions on Machine Learning Research (01/2023)
(CANDECOMP) SAADDECCOM/PARAAAA decomposition based LRTC (Accar et all, 2011 Jain &r Ohl, 2014 Zhao et all,
RUE Lin & Moitra 2. Tucker decomposition bassed LRTC (Xu all, 2013 Xu & Yin, 201 Kasai A
Mishral 2 Xie et all 201 Kong et all 2018), and tensor ring based LRTC (Yuan et all 201
This
paper will focus on CP decomposition based LRTC.
Tt known that the tensor nuclear norm hard to compute in practice. One has consider other tractable
solutions such as learning a CP model directly from incomplete data (Acar et all, 2011 Jain & Ohl, !IT!! tensor of rank r can be recovered from 0/23/2 log (n))
Jain & On (QUE) proved that
X randomly sampled entries, via alternating minimization. Barak Moitra (20TT)), Potechin & Stenred (
and [Foster & Risteski (20119) used the sum-of-squares hicrarchy
tractable relaxation to the tensor nuclcar norm. For 3rd-order lensor completion, Bazerque et al. (201K) used the sum of squared Frobenius norms
as a regularizer and showed that it is related to the 22/3 norm of the weights in CP decomposition. Yang al (2016) applied group-sparse regularization to LRTC and showed that the regularizer related to the 1/3 norm. Shi et all (201)) proposed to directly minimize the l norm of the weights in CP dccomposition for LRTC. The regularizers presented in the above three works are closely related to the tensor Schatten-p (quasi) norm with p 1, 2/3, or 1/3. Notice that these works (Bazerque et all, 2013 Yang et al. 2MT at 2MTZ) are purely ampirical-motivtee and have no thcoretical guarantee on the tensor completion performance. Moreover, the regularizations are limited in the discrete values {1, 1/33/ and only for 3rd- order tensors. One may expect to exploit Schatten-p quasi-norm with arbitrary p on arbitrary-order tensor and have theoretical guarantees for the recovery.
Besides LRTC, tensor robust principal component analysis (TRPCA) is another important problem of tensor recovery. TRPCA is generalization of robust PCA (De Torre & Black, 2001 Ding all, 2008; Camis aL IU Haeflele & Vidal, 2019 Dan & Chow, 2020 and aims to decompose noisy tensor to the sum of low-rank tensor and a sparse tensor. Many recent works on TRPCA can be found in (Anandkumar et all, 2016 Ltl 2016 et all, 2018; Goldiarb & Qin, BUTE Zheng et all, 20TH; Latet_all 2014 Wang et all, 2020). For example, Lu ot all (201 defined a new tensor muclear norm based on the t-product (Kilmer X MArRIT (01II) of lensors and provided sufficient conditions for exact recovery. Notice that these TRPCA algorithms have high computational costs on large-scale data. One approach to reducing the computational costs is using low-rank factorization, which, however, requires the estimation of rank.
In this paper, we focus on fast and accurate LRTC and TRPCA. Our contributions are two-fold:
We propose class of regularizers as a tensor rank proxy for tensors of arbitrary order. These are based on the Euclidean norms of the component vectors in the form of CP decomposition. We show that the regularizers are monotonic transformations of Schatten-p quasi-norms, where p could be any positive value. We also provide asymmetric variational forms for the tensor Schatten-p quasi-norm with discrete p. When applying the regularizers to LRTC and TRPCA, empirically, the recovery performance is robust to the choice of initial rank and the recovery accuracy is high when p is much less than 1.
We provide generalization error bounds for LRTC with Schatten-p quasi-norm regularization and LRTC with our regularizers. We show that a smaller p (but not too small) in the tensor Schatten-p quasi-norm smaller 9 in the proposed regularizers leads to tighter generalization error bound. More importantly, our theory indicates that for LRTC on d-order tensors, p 1/d is always better than any p > 1/d in terms of the generalization error bound. Note that our bounds are also applicable to 2-order tensors. In other words, our bound works for LRMC. We also provide a recovery error bound for TRPCA with Schatten-p quasi-norm regularization, which verifies the usefulness of small p TRPCA.
The experiments of LRIC and TRPCA on synthetic data, image inpainting, and image denoising demon- strate the effectiveness of the proposed regularization methods comparison to a few baselines. Morcover, the numerical results related to the Schatten-p quasi-norm or the proposed regularizers are consistent with the error bounds in theorems.
2

---

Published in Transactions on Machine Learning Research (01/2023)
2 Euclidean Norm Regularization (ENR) for Tensor Rank
First of all, recall the following definitions in terms of the CP docomposition.
Definition 1. Let 2 E R i E [r], E [d]. The rank of a tensor X E R xna.xan is defined as the minimum number of rank-one tensors that sum to X:
rank( min TEN: X
Σ 1=1
x
(1)
a
(d)
Definition 2. The nuclear norm (Priedland F Lim, 201 of a tensor X is defined as
| inf Σ |ss1: X
s Σ
(1) (2)
u; (d) ( 1 11,
Definition Q shows that. the tensor nuclear norm is a convex relaxation of tensor rank. However, both the the tensor rank and tensor nuclear norm are NP-hard to compute (Friedland & Lim 2018). Similarly, we may define a tensor Schatten-p quasi-norm that extends matrix Schatten-p quasi-norm. The p-th power of the tensor Schatten-p quasi-norm is a nonconvex relaxation of tensor rank.
Definition 3. The Schatten-p quasi-norm (0 < 1) of tensor X is defined as
1/p
| inf
Σ
s
X
stU1 u, u; l 6) = r,,, rEN, 0<D.I..
(1)
(2)
(d)
For convenience, we make the following definition.
(6) jeld Definition 4. Let d, le E N and given set of vectors { lie(s] Define CP = Ek= 2/ 2(( ozz (2) (2)...
a (
Note that ( ( is just shorthand for the of the i outer products of d vectors. We provide the following variational form of the tensor Schatten-p (quasi) norm (p > 0):
Theorem (Symmetric Regularizer") The tensor Schallen-q/d (quasi) norm for any real positive q and positive integer d (tensor order) be represented function of the Euclidean norms of the CP compo- nents:
k
d
g/d
inf x x-CP((1()
|
1
7
Note that in the theorem & 2 rank(2)) is assumed implicitly via the constraint X = (a. (1)). Com- pared to the definition (Definition G of the tensor Schatten-p quasi-norm, || given by Theorem M internalizes the weight factors into the vectors u and removes the unit-norm constraints on u. This reduces decision variables and the computational cost of calculating the gradient in optimization. In ad- dition, for some choice of p. there are no nonsmooth functions on the factors Theorem M, while there are always nonsmooth functions in Definition Hence, the formulation of Schatten-p quasi-norm in The- orem M is more tractable than that in Definition gl For instance, in Theorem letting d, 2, or 1, we have | = inf x (P 1 E || (5) |x| |x1/// = inf x-cP((m!")) 1 Σ Σ [ (t) 1|? and
X 1/d inf {P E | respectively. These three special cases are based on convex functions of Euclidean norms of component vectors, and hence possibly easier to handle in optimization.
||,
IIt worth mentioning that the Theorem (Cheng special of our Theorem (when p == and d p = 2/3 and d= 3). The earliest works exploring the p 2/3 and 1/3 regularizers.co (Bazerque all and (Yang all AUTEE respectively.
2006 and the Proposition 1 of (Lacroxx cl
ATE) two
3

---

Published in Transactions on Machine Learning Research (01/2023)
According to Theorem M1 for relatively low-order tensor, when we want to obtain sharp enough regularizer, we have to use sufficiently small p for all and j. Thus, every term (0|a [ can be nonconvex and nonsmooth, making difficult to solve the optimization problem of low-rank tensor recovery. The following
]ie(k]
theorem provides a class of asymmetric regularizers that have fewer nonconvex and nonsmooth terms than those in Theorem
Theorem 2 (Asymmetric Regularizer). Suppose q E (1,1/2, Let Pt =1 + qd 9) and P2 = (2/(2 + qd - q). We have
(a) ||
inf (=
P1 Σ
111 +
(1)
Σ
||0 (m.
9
j=2
d
(b) || = inf {aCp(((("))
1 +
Σ
||
11)
P2
j=
In Theorem 0 (b), the terms of j 2 are convex and smooth while those in Theorem 0 (a) are convex but nonsmooth. Therefore, the optimization related to Theorem (b) is casier. Since 3rd-order tensors more prevalent than tensors with other orders, we list their symmetric
(e.g. color images and videos) and asymmetric regularizers with only convex terms in Table M for convenience. Note that the last two regularizers in the table are not from Theorem M The derivations are in Appendix DM
Table 1: Regularizers (R(X)) given by the sum of only convex terms for 3rd-order tensor (x (x= -CP Characterization based on Euclidean norm
R(X))
values of q. P1. P2 in Theorems and
Asymmetric Symmetric
|
Σ i=1
||a x (s))
q 3 (Theorem M)
|
2/3
>
| (3) (2)
q = 2 (Theorem
| l|
1/3
3 >
|||
|
q = 1 (Theorem M)
Syya
X Il 1/2
xf D
9 1, P2 = 1/2 (Thcorem 22) derived from Appendix DB
$1y2
imi
| 2/5
10
E (1
(3)
Sayo
5
XX| 13/77
3/7
81
E (1
(2)
+ 0
derived from Appendix DB
7
In sum, the regularizers we proposed this section cover all Schatten-p (quasi) norms with any 0 < p S for any-order tensors. Some of the regularizers, especially those asymmetric ones, are based on convex or/au or/and smooth functions of the tensor factors, which convenient for application and optimization. These regularizers can be applied to LRTC and TRPCA that enjoy a variety of real applications in machine learning and computer vision.
The tensor regularizers we presented in this paper are closely related to the variational forms of matrix nuclear norm and Schatten-p quasi-norms (Shang et all 2016; 2017: Ean et all 2019 Giampouras et all, 2020). For instance, the squared sum of Frobenius norms of two factors of matrix lower bounded by the nuclear norm of the matrix, which is a special case of our Theorem II with et all, R the authors provided class of SVD-free variational forms of the matrix Schatten-p quasi-norm with discrete p that can be arbitrarily small. Our tensor regularizers can be regarded as generalization of the variational form of Schatten-p quasi-norm from matrix to tensor. For example, in Thcorem MI when d = 2 and = 1/2, the regularizer is equivalent to the FGSR-1/2 regularizer of (Dan el all 201)), which is related to the Schatten-1/2 quasi-norm of matrix. In Theorem (b),, when oquivalent to the FGSR-2/3 regularizer of (Fan all, 2019), which related the Schatten-2/8 quasi-norm of matrix. Nevertheless, theoretical guarantees about these tensor regularizers in low-rank tensor recovery are more difficult to derive than their matrix counterparts.
2 and p 1. In (Lan
and q = 1, the regularizer is
4

---

Published in Transactions on Machine Learning Research (01/2023)
3 Low-Rank Tensor Completion with ENR
3.1 LRTC-ENR algorithm
Let X' E R Xnd be rank-r tensor. Suppose we observed few noisy entries of X randomly (without replacement):
Plinie...ja [X -i + [ Wjsre..aaa (d. E Ω
where consists of the locations of the observed entrics and each entry of the noise tensor N is drawn from NV(0, o²). To recover X from D, one may solve
minimize Pa (D X)) 1 + + X 2
(1)
where (ia D if ( 5d) Ω and (P)(Di)inn-- 0 otherwise. The solution of ( is an estimate of X However, Problem (II) is intractable because the computation of the Schatten-p quasi-norm is NP-hard. Instead, based on the analysis in Section A assuming & 2 r, propose to solve
Pa (D-CPA(a!!)) + AR (lm
minimize (a/²)
2
(2)
where R ((a) denotes a certain regularizer in Theorem M. Theorem 2. or Table II e.g.,
d a (3) 110
R (a
X (1) 1
(3)
where x(1 = [2 (5)
a 1. Similarly, the regularizers in Theorem 2 (a) and (b) can be formulated as 12. Σラ x (12.)) and 1,
respectively. Note that even finding a stationary point of (II) is hard due to the computation of the Schatten-p quasi-norm while finding a stationary point of (2) is computationally feasible. For convenience, we call problem
(2) Low-Rank Tensor Completion with Euclidean Norm Regularization (LRTC-ENR). LRTC-ENR is an LRTC framework that covers all the regularizers presented in Theorem Theorem 2, and Table where the p 1,2/3, 1/3 regularizers for 3rd-order tensors studied by (Bazerque et al, 2013 Lacroix et all 2018) are special cases.
Cheng et al, 2016
Yang et all, 2016: Shi et all, 2017:
We propose to solve (z) by Block Coordinate Descent (BCD) with Extrapolation (BCDE for short) (Xn I Yiu, 20ι), which usually more efficient than BCD alone in practice. The decision variables can be organized into blocks (d matrices, i.c., X(), 1,.,,....
Then we need to iteratively solve d subproblems related to the by norm minimization. When q < 1, we integrate BCDE with iteratively reweighted method (Lui, ZUEE) If we use the symmetric regularizers given by Theorem M with q 1, need to solve d nonsmooth subproblems (related to || j= l......,d d) in every iteration and when perform the itcratively reweighted method for || 1,....,d d. In contrast, if we use the asymmetric regularizers given by Theorem 0 (b), the number of nonsmooth subproblems (related to [1 is reduced to and when q < we only need to perform iteratively reweighted method for ||x 122.. Therefore, the optimization related to the asymmetric regularizers more efficient than that related to the symmetric
need to
regularizers for the same problem.
We may also use quasi-Newton methods such L-BFGS (Lin & Nocedal, when the objective function is nonsmooth. The details of the optimization for are in Appendix A1
BSS solve problem
even
It is worth mentioning that according to Definition B, one may consider the following LRTC problem
1 Pn D - CP (1 (1) +
minimize (or
Pa|
(LLRTC-Schatten--))
subject to
||x 1 j E (d]
5

---

Published in Transactions on Machine Learning Research (01/2023)
where CP & (12) )) s (1) ox; ....,)"" ( Nevertheless, it is more difficult to solve Wi
than LRTC-ENR due to the following reasons. First, [RTC-Schatten-g has onc more block of variables 8, of which the gradient computation is costly (it requires evaluating every rank-one component of X). Second, constrained optimization LRFC--chhalen-- is generally harder than unconstrained optimization. Heuristically, we suggest using BCDE with iteratively reweighted minimization embedded solve TRiKe
Schatten- It is compared with LRTC-ENR in Figure @ of Section
3.2 Generalization Error Bound of LRTC
In this section, study the generalization error bounds of LRTCC-chattens and LRTC-ENR. The gener- alization error of tensor completion is defined as the difference between the prediction error for all entries and the training error for the observed entries, i.e.,
GÊTσ = E(D,X, [n] x [n]) 8(D,X,9)).
In this study, we let E(D,& X, [m] X ... x [n]) - D I| and ((, = Vini PP (D) though
their squares also be used. Tt should be pointed out that, compared to LRMC, is much more difficult to analyze the generalization ability of LRTC. The main reason is that we may not have orthogonal factors in CP decomposition. Thus, we first consider the case of orthogonal CP decomposition. We will also provide generalization ion error bounds for the general cases (without the restriction of orthogonality).
Without loss of generality, consider the case of hyper-cubic tensors, denoted by X E Rn For conve- nience, we define the following two tensor sets.
Definition 5 (Orthogonal CP tensor sets). Let S be the set of hyper-cubic tensors with orthogonal CP factors. Denote the Schalten-p quasi-norm of X E St by || Lel Sd,mpp be the set of lensors in St and with bounded (by 1p)) Schatten-p quasi norm. To be more precise,
(a) 8h,n {x E RR : x= Σ s:ss (1) (2)
u ... uu 1 [d], ut) (T) ui = 1 1 1, (3) ui =Offit)
...
(b) Shmpp = 18 E S |111s I vph.
We have the following covering number result. Thcorem 3. The covering numbers (denoted by N) of S.mp with respect to the Frobenius norm satisfy
1 + 1 2 p
CVp
log ((S.mppp ll (IF &
nd (log(d + 1))
where is universal consland and 0 < < 2.
Note that although Theorem does not include the case p 2, it is much easier obtain the covering number of Stm,. which will not be detailed in this paper because || is useless in regularizing the tensor rank.
Based on Theorem f we derive the following gencralization error bound for the Schatten-p quasi-norm regularized orthogonal tensor completion (minimizeexss xEst L1 (D - x)) || - + \||
Theorem 4. Suppose D od X E St., max D |xx ||10 S e, and 0 < < 2. Then there erists
numerical constant such that with probability at least 2n
1/4
( + Ind Log(d (d +1)
||
D X1p
Po (D- - <
(4)
nd
12
e dn

---

Published in Transactions on Machine Learning Research (01/2023)
In the theorem, since || (EV 1, the bound is U-shape function of p when 0 < 2. Therefore, there exists a threshold p = argminocpe22 (1/2 + (IP) Is+
((v/d)) 2n/(2-0) such that when p S p < 2, a smaller p will lead to a tighter error bound. However, is difficult to obtain p analytically. Here we use toy example
Definition E, we generate 8 [2", 1.9", ........, 0.2%, 0.2%, 0.1") and normalize it by 8/ Σ; 8t. We choose from (0.1,1,5, 10, 20, 50) and generate six different We see that a larger leads to higher decay rate of the element of 8. We use these six s together with three random orthogonal matrices U of size 100 x 20 to form six low-rank tensors of size 100 x 100 x 100 and rank 20. These six tensors have different 'low-rankness" because of the different v. For instance, the tensor corresponding to v = 50 can be well approximated by a rank-4 tensor, where the relative error is less than 0.01%. We let [St] = 0.1n and compute (( + mn log(d +
illustrate the result of Theorem EL According
[[[[]=([[ ((sssss/ = 1/4 A A for each tensor. The six and average A (corresponding to each 8) of 100 repeated trials are shown in Figure M. We see that in each case, smaller but not too small will lead to a smaller A. When the decay rate is higher, the approximate rank is lower, which leads to a smaller A. On the other hand, when the decay rate is lower, reducing p is more useful for reducing the error bound A.
(a) distribution
by different p
20
2
docey
decay
decoy rate 2
decay rate
15
decay 3
decay rate
decay
1.5
decay
dacal rate 5
decay rate
value of
decey
dccay rall
10
4
0.5
10 index of
Figure 1: An intuitive example of the error bound of Theorem The decay rates 1, 1,... correspond to 50 respectively.
1/a
Now study the generalization error of LRTC-ENR (Z). For convenience, let || Eg || (10 and define
Sk d,ngg = x E RRn x= =C || S saf), |X Tjr [d]
(5)
( where ( [x] 22 2 (1)
We have
Thcorem 5. The covering numbers of Synn with respect to the Frobenius norm satisfy
log Oog (ll,,)) I c(n + log(ek))
ddpa (5)
2-4
g
T/E
<<q22, 2, and for any 0 <
d Σ
depox ()
NSs gr |l (1r,,)) s d'nl:2la-1) 11/9 log(2nk)
C/C
for any g 2 2, where o = 11 and c, d' are universal constants.
Based on Theorem E, we have the following generalization error bound for LRTC-ENR (2) with R((x.")))
Σ Σ ||0

---

Published in Transactions on Machine Learning Research (01/2023)
Theorem 6. Suppose D Rne X S Smn. IT Y and max || S
Denote Q the Then with probability at
inder set of the missing entries of D suppose [R]] (0), and let [12|+
[0
least 1 1-6 å over the random partition f and f2, we have
1 12
Pn (D x)1
Pa x) + = + Bs)
4
nd
1
where B8-
+ 12
log
and
/
12/122|
5
C1
nk2 13/2 (ono-))//log(2niie (2g()kk) Ej=1
doa G)
log
[22]
if
[$2|
09j
BR
C2k
V
(n + log(ek))) 9)
Σj=1
dda (1)
2 1
<f0<9<1
[2]]
with constants and e2.
We that in Theorem D. the bound is not continuous around g In the theorem when 0 < 4 1, the bound is U-shape function of q. It indicates that smaller q but not too small leads to tighter error bound and for smaller [S] reducing the value of becomes more useful. We show an intuitive example in Figure Z to illustrate the role of q and [S2] in the error bound of Theorem F. In the example, we use d = 3, n = 100, and k 20 to generate synthetic random tensors X' Σ o;
(3) where x; .... x; are drawn from Gaussian distribution and ||~["|| = ... = | 5,. We consider six different decay rates for 81...., 620 corresponding to different levels of low-rankness. In general, a larger decay rate means an easier tensor recovery problem. We let p= nd and
(1) xx!")
[2]
(n + log(ek))
4)² d Σ
dopa (f)
2
02 1
(6)
0(2-29)²
Enj
where 0 < q < 1. In the sub-figures (b,c,d), we see that smaller g but not too small provides a tighter error bound. When the decay rate is smaller, reducing the value q becomes more useful, which is consistent with the result of Figure M. In addition, when p is smaller, namely the problem is harder, reducing the value of q bocomes much more effective.
disribution of
0b1 A given by diffarent (pm0.1)
151.4 givon by diffarento 1
(d) A. given by diflerntt a (1-0.01)
200
0.4
0.4
0.4
Cocay raze
cocay
-5
cocay
0.3
0.3
cecay
0.25
0.25
0.25
0oc0y
5
0.2
0.15
0.15
decay rate
decay rate
0.15
decey mate
docay
decay rate
docay
0.05
0.05
decay rale
0.05
docdy
decay rale
dondy
0.8
Figure 2: An intuitive exxample for the error bound of Theorem f
Based on Theorem we can obtain the generalization error bound for (0), which is shown in the following corollary.

---

Published in Transactions on Machine Learning Research (01/2023)
Corollary 1. Suppose
D
R Po X R"ee, max
|| I E, || is attained at X
()) ), and ja
X 1l S7.
Denote Q the inder set of the missing entries Df D, suppose [92] > |92],
and let == [1] R
Then with probability at least 1 - over the random sampling of Q2 we have
[0 m
1 PP (P (D - x)12 < ?2
PP x) + e (BR + Bs)
[
4
nd
1
where BB
+ 12
log
and
$1 [2)
|2/
C1K
nk2(pdd 1)/md log(2nk)) d2d=1)
2
||x
1 Sp
log [S2]
ifz 1/d
[
BR
C2%
(n + log(ek)) pd)2
djdd11 8
2pd/(2-pd)
|
2p/(2-
12|
[2]]
p(2 2pd)2
ss
with constants C1 and cz.
In Corollary D as well Theorem E, the error bounds are for L PP -D)1) and are almost linear with [0]]
[ In contrast, in Theorem HI the error bound is for V IDD X and is linear with ( ( 1/4 Therefore,
the bounds of Corollary and Theorem are tighter than that of Thcorem B, however, at a price of breaking the continuily al 1 p = 1/d.
Consider the terms related p in BR of Corollary with p 2 1/d, i.c., 2 1)/pd X X1s 2/d A Tp. Let 1/d 5 P2 Pl. Using the power-mean incquality we have 1 || || llsp, k 1/p || llsp, It follows that X I1 2/d s.,, Tpp where the equality holds if and only if $1 = $2 = = Sk (it will not happen practice almost surely). Therefore, when 1/d S p2 < Pı, the error bound given by pa is always tighter than that given by pt- This provides a rule of thumb for real applications that p should be at most 1/d. Together with the result of Corollary M1 for 0 < p 1/d, we suggest using p 1/2d.
S,
Tp. 2 1)/p/d)) || 2/d
Sp. S RR(pdd-11/vad (1//
Comparison with previous work Barak & Moitma (201))) Foster & Risteski (201M) and Wimalawann
& Mamitsuka (202T) have also studied the generalization error of CP based tensor completion. Their bounds are based on the nuclear norm (or Schatten-1 norm equivalently). We compare their bounds with our bound in Corollary M, in terms of third-order tensor with unit nuclear norm and r rank. The generalization error bound given by (Barak Moitral, 20TG) scales as Orr33/2 log" n//92). |Foster & Risteski (2ITg) provided an empirical risk bound for orthogonal tensor completion that scales as nn22n3/2 log n n/(22)) The generalization error bound (Theorem 1(b)) given by (Wimalawarne Mamitsuka 2021) is O(rn3/2smuss m /(2)) where l/r < Smax < 1. In our Corollary M, let d = 3, p 1, r, 7 1, and || 1, our bound becomes 2 V log((2))) log [[]/) We see our bound is tighter than all others r "log(22))) log [Ω] S 788mx-
4 Tensor Robust PCA with ENR
4.1 TRPCA-ENR algorithm
Let X" E X111XX2X-XXP4 be rank-r tensor. Suppose X is corrupted as
D= N E.
(7)
2oor any 21, 22: 2n 2 if > >>>>>>> have E 2 (2 +
with equality if and only
21 Zq-
9

---

Published in Transactions on Machine Learning Research (01/2023)
where N is dense noise tensor drawn from No o²) and E" is sparse noise tensor with randomly
distributed nonzero entries. To recover X' from D, we wish to solve
] ID
minimize X,E
X E I + *
(8)
but the problem is intractable. Then, based on the analysis in Section 2, we propose to solve
minimize
1/1 D (
1
(1) z x
oz
2
o xi (d)
ArR (fal")) + de dellE111.
(9)
2
where A is a penalty parameter for the sparse tensor E. For convenience, we call (9) TRPCA-ENR. Similar to LRTC-ENR, TRPCA-ENR is a TRPCA framework that covers all the regularizers presented in Theorem M. Theorem and Table M, where the p 1,2/3. 1/3 regularizers for 3rd-order tensors studied by (Bazerque et all 20R; Cheng ct all 2016: Yang ct all 2016; Shi ct all, 2017; Lacroix all, 20)) are special cases. Regarding problem (9), we proposed to update the d ++) 1 blocks of decision variables (i.e. & and ( = (m) , 1 l...., d) alternately. Namely, we need to itcratively solve d subproblems related to the b (0 < 9 2 2) norm minimization. Similar LRTC-ENR, we use the iteratively reweighted method (L. 2HEH) to solve the subproblems associated with g 1. Particularly, if we the symmetric regularizers given by Theorem D, when 2, use alternating minimization to solve (HI because every subproblem has closed-form solution; when S 1, there are d subproblems having no closed-form solution. If we use the asymmetric regularizers given by Theorem Ø (b), there is only one subproblem having no closed-form solution and hence we propose to solve (Hl by the (nonconvex) alternating direction method of multipliers (ADMM) (Wang et all 20B). We see that the asymmetric regularizers lead to much easier optimization problems than the symmetric counterparts do. The optimization for (9) is detailed in Appendix
R
4.2 Recovery Error Bound of TRPCA
Currently, it difficult to provide recovery guarantees for problem (8) and problem ( because of the non- convexity and non-smoothness. Instead, consider the following constrained orthogonal tensor recovery problem
minimize |D- - X E XeSi E
(10)
subject to || | I R 1 S Re
where p.p' E 10, the orthogonal CP tensor set S was defined by Definition G. and the observed tensor D was generated by (7) with m = n..... = na = n. In terms of the regularization on E, problem (III) is more general than (S) and ( because here we consider the ly' regularizer. However, compared to (8) and
(0) we have to consider the orthogonal lensor set for simplicity. We provide the following bound of recovery error.
Theorem T. Let ppp' (0, 1], I| Rg, and ||E"| Rg' Suppose &,E is the optimal solution of (m) and max(1]2* >0 | |bo) I a. Then with probability at least - 4n
X - 11 -/= + 3 -11
5(24 16v2) (22v20 dn log(5d) + dd logg())
2-p Rg (2a + 20 / 220+2oVdloglo dlog(n)
2-p' Rgd
In this theorem, for convenience, let c = 20 / dn log(5d) + log((n) and C2 = 2a + 20 dlog(n). When p and p' decrease, - and c₂ 2-p' increase but R and Re decrease, provided that there are a few elements in (refer to Definition ( and elements in Ex larger than 1. Therefore, when ej and 02 not too large,
10

---

Published in Transactions on Machine Learning Research (01/2023)
reducing the value of p or p' will lead tighter recovery error bound for X' and E Although Theorem Ø is for (III) rather than (8) and (g), it verified the superiority of smaller of the tensor Schatten-p quasi-norm in TRPCA.
5 Numerical Results
In this section, we conduct experiments of LRTC and TRPCA on both synthetic data and real image data. All the tensor computations are implemented in the MATLAB Tensor Tool Box of (Bader et all, 2 We use a MacBook Pro with 2.6 GHz Intel Core (17) and 16 GB RAM. is worth noting that the main goal of the experiments is to show the ivenes of the symmetric and asymmetric regularizers in LRTC and TRPCA and the influence of p and q on the recovery performance, not to compare optimization strategies with previous works (Bazerque et al 2013 Cheng et all 2016, Yang et al. 2UIE; Shi al, 2017: Lacroix et al, 208). In most cases, q (or p 1/3) (Yang et all 2 on the 3rd-order tensors has the best performance. The asymmetric regularizers slightly outperform the symmetric regularizers in the experiments TRPCA. In addition, the experiments show that ENRs, though simple, can outperform a lew strong baselines of LRTC and TRPCA.
5.1 Experiments of LRTC
We compare LRTC-ENR with a few baselines on synthetic low-rank tensors and multi-spectral images. We use Relative recovery error
- to evaluate the tensor completion performance, where T is the original complete tensor and F denotes the tensor recovered by tensor completion method. The minimum value of the metric is zero. A meaningful value of the metric is in the range of [0, 1].
5.1.1 Synthetic data
With the size for cach dimension n 50, we generate noisy low-rank synthotic tensors D = T Ruxax (3) The entries of (5) E TR" (i E [r], j E [3]) are drawn from (O, 1). The entries the noise tensor W are drawn from (O, (uOT)?), where oT denotes the standard deviation of the entries of T and v mcans the noise level. We randomly mask fraction (which we call missing rate) of the entries to test the performance of tensor completion.
where T Ei= x; x; o x;
We compare the performance of LRRCC and LRTC-ENR (solved by BCDE and LBFGS) in Figure G. in which we set r = 10 and considered different noise levels, missing rates, and values. In all methods, we set = 2r- = 20, Imax 500, and select. from {0.01, 0.5, 1, 5, 10, 50, 100, 500}. We can see that:
a. Regularization is helpful. In Figure & (a-d), the recovery error when there is no regularization (i.e., ==0) 0) higher than the others.
b. Smaller leads to lower recovery error? In almost all cases, < outperforms 1, verifying the superiority of Schatten-p quasi-norm over nuclcar norm LRTC (both LRTC-ENR and LRTC- Schatten-p). LRTC-ENR solved by BCDE and LBFGS, smaller p provides lower recovery error provided that p not too small (e-g- p 2 1/6), which matches Theorem E and Corollary
LRTC-ENR v.s. LRTC-Schattenpp Compared to Euclidean norm minimization, direct Schatten-p norm minimization has higher recovery error and time cost becanse the optimization problem is more difficult to solve.
d. BCDE u.s. LBFGS When p is too small (i.c., smaller than 1/6), the recovery error of LRTC-ENR solved by BCDE does not change, but the recovery error of LRTC-ENR solved by LBPGS increases. One possible reason is that LBFGS is not effective in handling nonsmooth objective functions and often stuck in bad local minima or even saddle points, especially when p very small. When p < 1/3, LRTC-ENR has at least one nonsmooth nonconvex subproblem, which brings difficulty LBFGS. However, the time cost of LBFGS is less than that of BCDE.
11

---

Published in Transactions on Machine Learning Research (01/2023)
(a) noise level=0.1, missing rate=0.5
(b) noise level=0.1, missing rate=0.8
0.03
0.055
LRTC-Schatten-p
LRTC-Schatten-p
Relative recovery error
0.028
LRTG-ENRRSym-BCDE)
Relative recovery error
0.05
(RTC-ENR(Smm-BCDE)
LRTC-ENNRSym-LBBFGG)
LRTC-ENNR(ym--LFFGG
0.026
LFTC-EENR(aym-BCDEE)
0.045
RRTC-EENR(aSm--BDDE
LRTC-EENR(aymLLBFGGG)
LRTC-ENN((aSmm-LEERR
0.024
0.04
0.022
0.035
0.02
0.018
0.03
0.016
0.025
NoReg
2/3
1/3
1/6
10
10
10
NoReg
2/3
1/3
1/6
10
10
10
p value of Schatten-p norm
p value of Schatten-p norm
(c) noise level=0.3, missing rate=0.5
(d) noise level=0.3, missing rate=0.8
0.09
0.16
LRTC-Schatten-p LRTC-EENR@ym--BCDE
Relative recovery error
Relative recovery error
CRTC-Schatten-p
0.08
LRTC-ENRI/Sm-LLFGG)
0.14
CRTC-ENN[(ym--BR
LBTC-EENR(BymM-BCDE)
LRTC- ENR/sym-LBFGGS LBFGS)
(BTC-EENR(Byy-LLBFGG))
LRTC-ENR (ATrC-ENR(asym-BBR (asy--
0.07
LRTC-EN CATC-EENRaaymm LBFGS)
0.12
0.06
0.1
0.05
0.08
NoReg
1/6
10
10
10.3
NoReg
1/3
1/6
10
10
p value of Schatten-p norm
p value of Schatten-p norm
Figure 3: Performance (average of 20 repeated trials) of Schatten-p (quasi) norm with different in the case of different noise level for the noise distribution (O, (voT)²); "NoReg" means LRTC without regularization
(Acar el al, IM the time costs (500 iterations) of the five methods are 8.6s, 3.0s, 2.1s, 2.8s, and 2.3s
respectively). The results of LRTC-ENR with symmetric regularizers of p 1, 2/3, 1/3 are attributed (Cheng all 20D). [Bazerque all 203 (Yang et all 2UT respectively.
Symmetric regularizer u.s. asymmetric regularizer It can be found that the performance of asym- BCDE and sym-BCDE are very similar and sym-LBFGS outperforms asym-LBFGS in many cases. These empirical results are not consistent with our intuition that the asymmetric regularizers are casier to optimize than the symmetric regularizers. for g = 1 and iteratively reweighted method for q < 1 of the symmetric regularizers the gradient descent for q 2 of the asymmetric regularizers. When p 1/3, the in asym- LBFGS is much less than the in sym-LBFGS and hence leads to higher instability in computing the gradient and Hessian for LBFGS.
possible reason that the soft-thresholding
as effective
Based on the above results, we suggest using BCDE to solve LRTC-ENR on small datasets and using LBFGS to solve LRTC-ENR on large datasets. In Schatten-p quasi norm, suggest using p 1/3 (Yang et al. 2016) or 1/6.
We compare LRTC-ENR, with HaLRTC (Lin atl 2012), TenALS A 2012), TMac (Xuett all auk). BCPF (Zhao all 201)) Rprecon Kasai Mishal 20I6), KBR-TC (Xie of all, 20E). TRLRF (Yuan all, 201). In TenALS, TMac, BCPF Rprecon, TRLRF, and LRTC-ENR, we need determine the factorization size (or the initial rank in other words) beforehand. These methods, compared to HaLRTC and KBR-TC, may apply to large tensors efficiently
Comparison with other tensor completion methods
12

---

Published in Transactions on Machine Learning Research (01/2023)
provided that the ranks are sufficiently small. Particularly, in TMac, BCPF, and LRTC-ENR, the rank is adjusted adaptively.
Figure B shows the recovery of LRTC-ENR (p = 1/3(Yang et all 2016), solved by LBFGS) and seven baselines on the synthetic data with = 10. all methods except HaLRTC and KBR-TC, one has to
determine the initial rank beforehand. For these methods except Rprecon, we have set the initial rank because in practice is difficult to know the true rank. The multi-rank of Rprecon set to (r,r, because
it performs the best. The results in the figure show that Rprecon, BCPF, and LRTC-ENR (p 1/3 Yang outperformed other methods.
et all 201G)
0.3
(8)
(b)
HaLRTC
0.5
KBR-TC
TenALS
Relative recovery enor
BCPF
Relative recovery error
0.40
Time cost (second)
0.2
TMac
Rprecon
0.3
KBR-TC
30
TALRF
TenALS
0.15
LRTC-ENR
0.2
BCPF
20
TMac
0.1
LRTC-ENR
0.1
10
0.05
100
1912
0.3
0.4
0.5
0.6
0.7
0.8
0.9
KBR-TC TenALS
RCPF
TMac
LRTC- LATC-ENR
Missing rate
0.2
0.5
0.8
0.9
Missing rate
Figure 5: Low-rank tensor completion on synthetic data:
Figure Low-rank tensor completion on
LRTC-ENR (p = 1/3 (Yang alj, 201R) v.s. baseline meth-
synthetic data (r 10): LRTC-ENR (p 1/3 (Yang et al, 2016)) v.s. seven baseline methods.
ods, 50; (a) recovery error with different missing rates;
(b) average time cost in all cases of missing rates.
When the missing rate is 0.9 in Figure H. observed 12, 500 entries, much more than the minimum number (1,500) of freedom parameters required to determine the tensor uniquely. It means the tensor completion problem is too easy. Hence we increase r to 50 and report the recovery error and computational time of KBR-TC, TenALS, BCPF, TMac, and LRTC-ENR (p = 1/3 (Yang et al, 2016)) in Figure EL where we did not report the results of other methods because their recovery errors are much higher than those reported methods. We see the recovery error of BCPF and LRTC-ENR = 1/3 (Yang et all 2m))) are lower than those of other methods. When the missing rate sufficiently high, LRTC-ENR (p 1/3 (Yang all (ооо) has less recovery error than BCPE. Moreover, LRTC-ENR (200 iterations) is at least 15 times faster than BCPF and 5 times faster than KBR-TC.
5.1.2 Multi-spectral image inpainting
We use the Columbia multi-spectral image database (Yasuma et all, 2008) to show the performance of tensor completion methods in image inpainting problems. The dataset consists of the multi-spectral images of 32 real-world scenes a variety of wollworld materials and objects. The spatial resolution of the images is 512x512 and the number of spectral bands is 31. Thus the data of each image is tensor of size 512 x12xx12
In our experiments, we pre-scale the image of every channel [0, 1]. Since TRLRF (Yuan all 2018 and Rprecon (Kasai & Mishral 20CC have extremely high computational costs these tensors, omit their implementations here. In (Xie et all, 2mx), it has been shown that BCPF (Zhao_etaal et 205) significantly outperformed HaLRTC (Lin et all, 2012) as well as few other basclincs on this dataset, so we will not compare HaLRTC. The initial rank of TMac (( el all, 20K) and LRTC-ENR are set to 100. When the initial rank is 100, it takes TenALS (Jain OI, 2m1 and BCPF (Zhao et all 2ME) more than 1500 seconds on each image, thus we set the initial rank to Since the tensor rank very small compared to the size and the images are noiseless, we here consider highly incomplete images of which the missing rates are no less than 0.95.
13

---

Published in Transactions on Machine Learning Research (01/2023)
As an example, Figure R shows the recovery errors of LRTC-ENR (at different p) and the competing methods the first image of the dataset when the missing rate is 0.95, 0.97, or 0.99. When the missing rate is 0.95, KBR-TC outperformed LRTC-ENR. When the missing rate is 0.99, LRTC-ENR outperformed all other methods. In Figure R (a), for LRTC-ENR, p = 1/6 is the best choice, while in Figure B (b) and (c), P = 1/3
(Yang el alj 20T6) has the least recovery error. These results are consistent with the theorems: a smaller p but not too small leads to a lower recovery error; p = 1/d is better than any p > 1/d.
missing rate=0099
missing rate-0099
0.16
0.2
0.7
- LRTC-ENR
LRTC ENR
LATC-ENR
0.14
TanALS
0.18
TenALS
TenALS(-00.9
BCPF
BCPF
BOPF
Relstive recovery
0.12
KBR-TC
Relalive recovery
0.16
KBR-TC
TMac
0.5
TMac
KBR-TC
0.14
0.1
0.4
0.12
Relalive
0.08
0.08
0.08
0.2
0.04
0.06
0.1
NoReg
1/3
1/6
101
10 73
103
10-
10
NoReg
2/3
1/
1/8
10
10 /3
5
NoReg
1/8
10
5
value Schatten-p nomm
p Schallen-p nom
p Schallen-p norm
Figure 6: Recovery error on the first image of the MSI datasct. The results of LRTC-ENR with p =
1, 2/3, 1/3 are altributed (Cheng et all 2016). (Bazerque all 2013) YYang el all 2010) respectively.
Figures 0 and IS visualize the recovery performance on the first image when the missing rates are 0.97 and 0.99 respectively. Visually, the recovery performance of LRTC-ENR (p = 1/3 (Yang et al, 2016) is much better than those of other methods. The average results (PSNR) on the 32 images are reported in Table a KBR-TC and LRTC-ENR (p = 1/3 (Yang et all, 20T6) outperformed other methods significantly. When the missing rate 0.97 or 0.99, LRTC-ENR, (p 1/3 (Yang et all 2016)) outperformed KBR-TC, and the improvement is significant according to the paired t-test. In addition, the time cost of LRTC-ENR ((Yang et al 20TT) is only 15% of that of KBR-TC.
Table 2: Average recovery performance (PSNR) the Columbia MSI dataset of 32 images (the p-value is from the paired (-test between KBR-TC and LRTC-ENR)
Missing rate
0.95
0.97
0.99
Time
TenALS (Jain & Of,, 2
30.114.44
25.9-13.22
13.3:14.9
500s
BCPF (Zhan et all 201
30.4+5.8
26.8+5.6
20.2+3.3
450s
TMac (Xi ef all, 2016
33.3+5..4
30.6+4.99
17.9++3.1
190s
KBR-TC (Xie et all 201
37.114.9
31.4+4.9
20.5412.8
730s
LRTC-ENR (p 1/3
(Yang al. 2016)
35.4+4.4
32.415.1
26.1
110s
p-value (t-test)
5x10
5x10
2x10-1
0
5.2
Experiments of Tensor Robust PCA
5.2.1
Synthetic data
The low-rank tensor T is given by T = =E was (1) a (2) a; where w, = i/r and the entrics of a R (i E [r], j E [3] are drawn from N/ 1). N is dense noise tensor drawn from (0, (0.1oT)?) and E is sparse noise tensor drawn from (N o7). We set 50, 25 and evaluate the TRPCA performance in recovering T in the case of different sparsity
We generate synthetic tensors by D=
14

---

Published in Transactions on Machine Learning Research (01/2023)
Original image
Incomplete image (0.97)
TenALS (PSNR-28.9)
BCPF (PSNR-26)
TMac (PSNR-35)
KBR-TC (PSNR-35.2)
LATC-ENR (PSNR-36.6)
Figure 7: Inpainting performance on the first image (band 16) of the MSI dataset when the missing rate is 0.97. In LRTC-ENR, 1/3 (Yang et all, 2016)
Original image
Incomplete image (0.99)
TenALS (PSNR-7.1)
BCPF (PSNR-17.6)
TMac (PSNR-17.9)
KBR-TC (2SNR-20.4)
LRTC-ENR (PSNR-30.6)
Figure 8: Inpainting performance on the first image (band 16) of the MST dataset when the missing rate is 0.99. In LRIC-ENR, 1/3 (Yang et al., 2016).
(termed as noise density) of E. The evaluation metric is the relative recovery error defined by
Relative recovery error T - -11l
15

---

Published in Transactions on Machine Learning Research (01/2023)
2018). TRPCA (denoted by T-TRPCA) proposed by eLl 20A) and the robust tensor decomposition method OITNN-T, proposed by (Wang et all 2020) are under the assumption of t-product (not CP decomposition) and hence are not compatible in our setting of syuthotic data. We only compare them on real data later. The typer-parameters
We compare TRPCA-ENR with KBR-PCA et
KBR-RPCA and
TRPCA-ENRE are sufficiently tuned provide their best performance. Figure B(a) shows the recovery errors of KBR-RPCA and TRPCA-ENR (with p = 2/3 (Bazerque et all 2013), 1/3 (Yang al, 20TD), and 1/6) when the noise density increases from 0.1 0.7. We see that TRPCA-ENC consistently outperformed KBR-RPCA In TRPCA-ENR, p 1/6 is better than p 2/3 and 1/3 but the difference is not obvious. In Figure [b),, we show the influence of different p the recovery error. It can be found that smaller p (but not too small, e.g. larger than 10- yields less recovery error.
(b)
0.14
KBR-RPCA
TRPCA-EE ENR (noise density-0.33 TRPCA-ENR (ncise densily-O.S)
TRPCA-ENR (p=2)3)
TRPCA-ENR (0-1-3)
0.045
Relative recovery error
TRPCAVENR (p=148)
Relative recovery error
0.1
0.04
0.06
0.035
0.04
0.02
0.03
0
0.2
0.3
0.6
2/3
1/3
10"
10
10
10
Noise density
p value of Schatten-p norm
Figure 9: Performance of TRPCA on synthetic data (average of 20 repeated trials): (a) KBR-RPCA v.s. TRPCA-ENR (initial rank-2r); (b) relative recovery error of TRPCA-ENR with different p. The results of TRPCA-ENR with p - 2/3, 1/3 are attributed to (Bazerque al. 2013 (Yang all 2016)) respectively.
In Figure II compare the performance of symmetric regularizers and asymmetric regularizers in TRPCA- ENR. We see that in all cases, the recovery error and time cost given by the asymmetric regularizers are lower than those given by the symmetric regularizers. The reason is that there are more subproblems in the optimization associated with the symmetric regularizers that have no closed-form solutions. The optimization with asymmetric regularizers reaches the stop criterion 200 or 300 iterations while the optimization with symmetric regularizers requires much more iterations or even does reach the stop criterion in 500 iterations.
5.2.2 Color image denoising
We compare TRPCA-ENT with KBR-PCA el 2018), T-TRPCA eLu 201)), and OITNN-L (Wang et all 2121 in the task of color image denoising on nine color images (displayed by Figure IT) of size 256 x 256 x 3 used in (Wang et all, 2020). For each image, we randomly set 10% of the tensor elements random values in [0, 1]. We tuned all hyper- ppprrpparaeeters carefully within wide ranges provide the best set À 2 3. In OITNN-L,
denoising performance of the methods. As a result, in KBR-RPCA, set X 1/v7688 2/V768, In TRPCA-ENR, we set
set d 4 or 5 and Äs 0.16. In T-TRPCA, the initial rank to relatively large value 200 because the approximate rank of the image tensors is not too small and the method can adjust the rank adaptively; we set X 0.02 and consider the cases of p = 2/3, 1/3, 1/6, and 1/10, for which X₂- = 0.1, 0.1, 0.02, and 0.015.
The average PSNR with standard deviation across repeated trials are reported Table R. We see that the PSNRs of TRPCA-ENT methods are much lower than those of other methods in all cases. In addition, TRPCA-ENR with smaller p has higher PSNR and TRPCA-ENR with p 1/10 performs the best. Figure
TThroughout this paper, / 10 and max for Algorithms E and
16

---

Published in Transactions on Machine Learning Research (01/2023)
[8]
3.5
2.5
symmetric asymmetric
Relative recovery emror
symmetric asymmetnic
symmetric asymmetric
symmetric aesymmettic
1.5
Relalive recovery
3
Time cost (8)
Time cost (5)
1.5
2.5
3.5
p-1/3
p-1/8
P-1/10
p-1/3
p-1/8
p-1/10
p-1/8 p-1/10
p-1/3 p-1/8
Figure 10: Comparison of symmetric and asymmetric regularizers in TRPCA-ENR on the synthetic data (average of 20 repeated trials): (a) relative recovery error when the noise density 0.3; (b) relative recovery error when the noise density is 0.5; (c) time cost when the noise density is 0.3; (d) time cost when the noise density is 0.5 (the maximum iteration 500 and the stop criterion is that the relative change of the decision variables is less than 10 4).
7
8
Figure 11: Nine color images for denoising
I2 visualizes the denoising performance on Image 1, showing that TRPCA-ENR methods are better than other methods. These results provided evidence that tensor Schatten-p quasi-norm minimization is able to provide higher recovery accuracy in TRPCA when a relatively smaller is used.
6 Conclusion
We presented a framework Fuclidean-Norm-nndccee Regularization (ENR) for LRTC and TRPCA, though some special cases were already studied in previous works (Bazerque et all 2U33 Cheng all 2uEE Shi gt all, A0T: Lacroix et al, 20N). We in this work focused more the theory of Schattern-p quasi-norm and ENR in LRTC and TRPCA than the numerical comparison of different LRTC or TRPCA methods. We proved that the Schattern-p quasi-norm with a decently small or ENR with decently small g provide lighter generalization error bounds for LRTC. More importantly, our theory indicales that for LRTC on d-order tensors, p = 1/d is always better than any p > 1/d in terms the generalization error bound. We also proved that in TRPCA for orthogonal tensors, smaller p Schattern-p quasi-norm can lead a lower recovery error bound under some mild conditions. addition to the theoretical results, our numerical results verified the effectiveness of ENR in comparison to few baselines of LRTC and TRPCA.
17

---

Published in Transactions on Machine Learning Research (01/2023)
Table 3: PSNR of color image denoising.
The results of TRPCA-ENR with symmetric regularizers of
p 2/3, 1/3 are attributed to [Bazerque et all 2013, (Yang all 20Th) respectively.
Image
Image 2
Image
Image 4
Image5
KBR-RPCA (Xie et all 2018
30.25=0.06 31.16=0.05
33.36=0.22
31.93=0.12
31.8710.08
35.08:0.12
T-TRPCA (La ct all, 2019)
32.75=0.06
32.87=0.11
32.52+00.00
33.91+0.10
OITNN-O (Wang et all 2020
28.46=0.04
29.99=0.03
29.16=0.05
28.13=0.04
29.86+10.03
TRPCA-ENR (p=
3: sym)
34.23=0.12
35.44+0.09
34.82+0.18
34.23++0114
37.14+0.06
TRPCA-ENR (p= 3: sym
34.68=0.18
36.8810.16
37.5210.12
34.5311.31
37.78:10.04
TRPCA-ENR p
asym
34.81=0.16
37.0441..06
37.6140.19
34.92:10.28
38.16:10.10
TRPCA-ENR p
asym
34.96=0.40
36.94=0.12
37.57=0.33
35.12:0.11
38.1440.11
TRPCA-ENR 10 asym)
35.45+0.12
37.14+0.100
37.76+0.14
35.38
38.28+0.13
Image
Image 7
Image
Image 9
KBR-RPCA (Kie ell
all 201
31.36 0.09
30.08
32.41+0.05
34.28+0.12
T-TRPCA (Lu al, 2019)
28.96=0.06
29.36+0.09
31.4910.11
33.6710.14
OITNN-O (Wang et all 2020
27.39=0.05
27.46=0.05
28.61#0.07
30.06=0.06
TRPCA-ENR (p= 2
/: sym)
sym
35.09=0.12
33.67=0.10
35.66=0.16
36.12=0.05
TRPCA-ENR (p=
33.21=0.54
34.10+0.23
36.09+0.14
37.95=0.166
TRPCA-ENR [ asym)
33.54=0.71
34.2911.118
36.3840.09
38.1310.12
TRPCA-ENT [ asym)
33.62-0.76
34.44+0.12
36.49++0.08
37.96-00110
TRPCA-ENR 10 asym)
35.1840.35
34.57-0.14
36.7110.06
38.01
Orignaliaap Inago
Notay Image
KBR RPCA (PSNR-30.22)
T-TRPCA (PSNR-31.25)
OINNN-O (PSNR-28.52
(P-2))) (P5NR-34B1))
ENR 13) IPENR-34.85 B5)
(2-1/6) (SNNR-35.08)
ENR (0-1/10) 1/) (PSN3-36
Figure 12: Denoising performance on Image 1.
Acknowledgements
Jicong Fan gratefully acknowledges support from the Youth program 62106211 of the National Natural Science Foundation of China and the rescarch funding T00120210002 of Shenzhen Rescarch Institute of Big Data. Zhao Zhang gratefully acknowledges support from the National Natural Science Foundation of China under Grant no. 62072151 and Anhui Provincial Natural Science Fund for the Distinguished Young Scholars (2008085.33)). Madeleine Udell gratefully acknowledges support from NSF Award IIS-1943131, the ONR Young Investigator Program, and the Alfred P. Sloan Foundation. Jicong Fan and Madeleine Udell the corresponding authors of this paper.
18

---

Published in Transactions on Machine Learning Research (01/2023)
References
Evrim Acar, Daniel M Dunlavy, Tamara G Kolda, and Morten Mørup. Scalable tensor factorizations for incomplete data. Chemometrics and Intelligent Laboratory Systems, 106(1):41 56, 2011.
Anima Anandkumar, Prateek Jain, Yang Shi, and Uma Naresh Niranjan. Tensor vs. matrix methods: Robust tensor decomposition under block sparse perturbations. In Artificial Intelligence and Statistics, pp. 268-276 2016.
Brett W. Bader, Tamara G. Kolda, et al. Matlab tensor toolbox version 3.1. Available online, June 2019.
Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, pp. 417-445, 2016.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. Xiviv preprint arxi: 706.0068 08498, 2017.
Juan Andrés Bazerque, Gonzalo Mateos, and Georgios В Giannakis. Rank regularization and bayesian inference for tensor completion and extrapolation. IEEE transactions signal processing, 61622):5689- 5703, 2013.
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Compulational Mathemalics, 9(6):717-777 772, 2009. ISSN 1615-3383. doi:
Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? J. ACM, 58(3):1 37, 2011. ISSN 0004-5411. doi: 10.1145/19703922.9773355
Hao Cheng, Yaoliang Yu, Xinhua Zhang, Eric Xing, and Dale Schuurmans. Scalable and sound low-rank tensor learning. In Arthur Gretton and Christian C. Robert (eds.), Proceedings of the 19th Interna- tional Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 1114 1123, Cadiz, Spain, 09 11 May 2016. PMLR.
Fernando De la Torre and Michael J Black. Robust principal component analysis for computer vision. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume 1, pp. 362 369. JEÉE, 2001.
Chris Ding, Ding Zhou, Xiaofeng He, and Hongyuan Zha. R 1-pca: rotational invariant: 1-norm principal component analysis for robust subspace factorization. In Proceedings of the 23rd international conference on Machine learning, pp. 281 281-288, 2006.
Ran Yaniv and Dmitry Pechyony. Transductive rademacher complexity and its applications. Journal of Artificial Intelligence Research, 35:193 234, 2009.
Jicong Fan. Multi-mode deep matrix and tensor factorization. In International Conference Learning Representations, 2022.
Jicong Fan and Tommy W. S. Chow. Exactly robust kernel principal component analysis. IEEF Transactions on Neural Networks and Learning Systems, 31 (3)77979-77 2020. doi: 10.1109 TTT.TTNN...SS..NNNN....
Jicong Fan and Tommy W.S. Chow. Matrix completion by least-square, low-rank, and sparse self- representat ions. Pallern Recognition, 71:290 305, 2017. ISSN 0031-3203. doi: https///doi.org/10.0000
pa1cco.2017.05.011
Jicong Fan, Lijun Ding, Yudong Chen, and Madeleine Udell. Factor group-sparse regularization for efficient low-rank matrix recovery. In Advances in Newral Information Processing Systems 32, pp. 5104-5114. Curran Associates, Inc., 2019.
19

---

Published in Transactions on Machine Learning Research (01/2023)
Dylan J. Foster and Andrej Risteski. Sum-of-squares meets square loss: Fast rates for agnostic tensor completion. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirly-Secome Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1280 1318. PMLR, 25 28 Jun 2019.
Shmuul Friedland and Lek- Lek-Heng Lim. Nuclear norm of higher-order tensors. Mathematics of Computation, (((311):1255-11) 2018.
Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):025010, 2011.
Navid Ghadermarzy, Yaniv Plan, and Özgür Yilmaz. Near-optimal sample complexity for convex tensor completion. Information and Inference: A Journal of the IMA, 9(3):577-615 2019.
Paris Giampouras, René Vidal, Athanasios Rontogiannis, and Benjamin Haeffele. A novel variational form of the schatten-p quasi-norm. Xix preprint arXiv:2010. 13927, 2020.
Donald Goldfarb and Zhiwei Qin. Robust low-rank tensor recovery: Models and algorithms. SIAM Journal on Malria Analysis and Applications, 35(1):225 253, 2014.
Benjamin D Haeffele and René Vidal. Structured low-rank matrix factorization: Global optimality, algo- rithms, and applications. IEFE transactions pattern analysis and machine intelligence, 42(6):1468-- 1482, 2019.
Moritz Hardt. Understanding alternating minimization for matrix completion. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS),, 651-660. IEEE, 2014.
Aicke Hinrichs, Joscha Prochno, and Jan Vybíral. Entropy numbers of embeddings of schatten classes. Journal of Functional Analysis, 273(10):3241-322) -2261,, 2017. ISSN 0022-1236. doi: https://doi.org/10.000 j.jfa.2017.08.000
Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information. Processing Systems, pp. 1431-1439, 2014.
Hiroyuki Kasai and Bamdev Mishra. Low-rank tensor completion: riemannian manifold preconditioning approach. In International Conference on Machine Learning, pp. 1012 1021, 2016.
Misha E Kilmer and Carla D Martin. Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):641166)) 658, 2011.
Hao Kong, Xingyu Xie, and Zhouchen Lin. t-schatten-p norm for low-rank tensor recovery. IEEE Journal of Selected Topics in Signal Processing, 12(6):1405 1419, 2018.
Daniel Kressner, Michael Steinlechner, and Bart Vandereycken. Low-rank tensor completion by riemannian optimization. BIT Numerical Mathematics, 54(2):447-455 2014.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pp. 2863 2872. PMLR, 2018.
Allen Liu and Ankur Moitra. Tensor completion made practical. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18905-18916. Curran Associates, Inc., 2020.
Dong Liu and Jorge Nocedal. On the limited memory bigs method for large scale optimization. Mothe- matical programming, 45(1-3):503-528, 1989.
Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. IEFE transactions on pottern analysis and machine intelligence, (:(1))208 2200 2012.
20

---

Published in Transactions on Machine Learning Research (01/2023)
Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan. Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 5249 5257, 2016.
Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan. Tensor robust principal component analysis with new tensor muclcar norm. IEEE transactions pattern analysis and machine intelligence, 42(4):925 938, 2019.
Zhaosong Lu. Iterative reweighted minimization methods for 1 Lp regularizod unconstrained nonlinear pro- gramming. Mathemalical Programming, 147(1-2):277-300) 2014.
Sebastian Mayer and Tino Ulrrich. Entropy numbers of finite dimensional mixed-norm balls and function space embeddings with small mixed smoothness. Constructive Approzimation, 53(2):249-22)) 279, 2021.
Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and Trends@ in Optimizalion, 1(3): 127-239, 2014.
Aaron Potechin and David Steurer. Exact tensor completion with sum-of-square.. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1619-1673. PMLR, 07-10 Jul 2017.
Bernardino Romera-Paredes and Massimiliano Pontil. new convex relaxation for tensor completion. Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, pp. 2967-2975, 2013.
Nicolas Schreuder. Bounding the expectation of the supremum empirical processes indexed by h3 older classes. arviv preprint Xix:200033 133500,0 2020.
Fanhua Shang, Yuanyuan Liu, and James Cheng. Tractable and scalable Schatten quasi-norm approximations for rank minimization. In Artificial Intelligence and Statistics, pp. 620-629, 2016.
Fanhua Shang, James Cheng, Yuanyuan Liu, Zhi- Zhi-Quan Luo, and Zhouchen Lin. Bilinear factor matrix norm minimization for robust pca: Algorithms and applications. IEEE transactions pattern analysis and machine intelligence, 40(9):2066-2D)) 2080, 2017.
Qiquan Shi, Haiping Lu, and Yiu-ming Cheung- Tensor rank estimation and completion via cp-based nuclear norm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 949-958, 2017.
Ryota Tomioka and Taiji Suzuki. Spectral norm of random tensors. arXio preprint arXiv: 2014.
Andong Wang, Chao Li, Zhong Jin, and Qibin Zhao. Robust tensor decomposition via orientation invariant tubal muclcar norms. In AAAI, pp. 6102-6109, 2020.
Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence of admm nonconvex nonsmooth optimization. Journal of Scientific Compuling, pp. 35, 2015.
Kishan Wimalawarne and Hiroshi Mamitsuka. Reshaped tensor muclcar norms for higher order tensor completion. Machine Learning, 110(3))507-531 2021.
Q. Xie, Q. Zhao, D. Meng, and Z. Xu. bannckkr-bbssi--rppeeenttee based tensor sparsily and its ap- plications to tensor recovery. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(8): 1888-1902 2018.
Yangyang Xu and Wotao Yin. A block coordinate descent method for regularized multiconvex optimization with applications nonnegative tensor factorization and completion. SIAM Journal on imaging sciences, 6(3):1758-177) 1789, 2013.
Yangyang Xu, Ruru Hao, Wotao Yin, and Zhixun Su. Parallel matrix factorization for low-rank tensor completion. aixio preprint arxi 1312. 1254, 2013.
21

---

Published in Transactions on Machine Learning Research (01/2023)
Bo Yang, Gang Wang, and Nicholas D Sidiropoulos. Tensor completion via group-sparse regularization, In 2016 50th Asilomar Conference on Signals, Systems and Computers, pp. 1750-1754 IEEE, 2016.
Chengrun Yang, Lijun Ding, Ziyang Wu, and Madeleine Udell. Tenips: Inverse propensity sampling for tensor completion. In International Conference Artificial Intelligence and Statistics, pp. 3160-3168. PMLR, 2021.
E. Yasuma, T. Mitsunaga, D. Iso, and S.K. Nayar. Generalized Assorted Pixel Camera: Post-Capture Control of Resolution, Dynamic Range and Spectrum. Technical report, Nov 2008.
Longhao Yuan, Chao Li, Danilo Mandic, Jianting Cao, and Qibin Zhao. Tensor ring decomposition with rank minimization on latent space: An efficient approach for lensor completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 9151-911111 9158, 2019.
Ming Yuan and Cun-Hui Zhang. On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics, 16(4):1031-106 2016.
Qibin Zhao, Liqing Zhang, and Andrzej Cichocki. Bayesian cp factorization of incomplete tensors with automatic rank determination. IEEE transactions pattern analysis and machine intelligence, 37(9): 1751 1763, 2015.
Yu-Bang Zheng, Ting-Zi Zhu Huang, Xi-Le Zhao, Tai-Xiang Jiang, Tian-Hui Ma, and Teng- Yu Ji. Mixed noise removal in hyperspectral image via owwfiibred-rram regularization. IEEE Transactions on Geoscience and Remote Sensing, 58(1):734-749, 2019.
Pan Zhou, Canyi Lu, Zhouchen Lin, and Chao Zhang. Tensor factorization for low-rank tensor completion. IEEE Transactions on Image Processing, 27(3):1152 1163, 2017.
22

---

Published in Transactions on Machine Learning Research (01/2023)
A Optimization for LRTC-ENR
A.1 Block Coordinate Descent with Extrapolation
There are blocks of decision variables in problem (0), ie. (x()) where X = [x] 2
(1)
We propose to find a critical point of (2) by Block Coordinate Descent (BCD) with Extrapolation (BCDE for short) (Xu &z Yin, 2013), which more efficient than BCD. For simplicity, here we only present the optimization of (2) with the regularizer shown in (G). The optimization can be easily exlended to (22) with
other regularizers we proposed in Section A
Let
C ((xx(0iieeu))
2
M *
D -
Σ i=1
ai
(4) (0)0011)
F
May
(Di) x
and
R Rpd (X (1)
Σ 1 (i) 1pd
where ((x()))) = ( ..... @ x(++1) @ x(-1) @ 2 x(), We initialize (x6)) randomly and
rescale æ to have unit Euclidean norm:
= ~(0.11,, a. t (1) /||= 5 l. iE [k], [d].
(11)
Then iteration 4, for j = 1,2,.... we first perform an extrapolation
x x + + -x(1)
(12)
where wy 2 controls the size of the extrapolation at iteration t. Then we perform a proximal step as
Lig x - x(2 + XR
x (1) argmin X
(V V C, x01 - -x-1
(13)
A prox
(111)
L v x(3) t).
In
3 L (M ((
x (x (
(xx()) (xx(0))))0
X ...
x
X 1) .... x(1), and Eg is larger than the Lipschitz constant of V x L. We approximate
it by
3 = eV
Ω
[xx0) (1x00)00001 Seoss]
(14)
74
23

---

Published in Transactions on Machine Learning Research (01/2023)
where 2 =0.,, 1, or 2. The derivation of (LEI is follows. For convenience, we denote a perturbed copy of ( by 2,0) We have
x C V 2 G|FF
(M (D6) - (x 000e
( ( ((x()))))
- -(M (D6) - - (x O1 (xx )
<](((X(0)) Oi |11 (
(x (X - 2 (x()), I|
?
<II((X (0) O 11
1 1|F
T4
50
n4
I n4
Here 0 <<
is some suitable constant.
[22]
when p = 1/d, prox) = xx (Y), where is the column-wise soft-thresholding operator (Parikh defined by
(1vll
if 1 A; otherwise.
(3)
0,
Lie Y. When p 2/d, we can estimate x by gradient descent. Eye. + 2X
When p 2/d, prox YY)
When
1/d, IK is nonconvex and nonsmooth. Then we update X with iteratively reweighted method (La
2014
which is given by Algorithm M.
Algorithm miny J/lY G112 + A
1
Require: G, A, E.
1: Y +G. G.
for = 1.2.....44 do
W diag( (11 + +) 9-2
..... (11yxl +e) "22)
y= G(I 21
end for Ensure: Y.
In
12 the parameter Wjt is determined
4j4-1 8y 2
(15)
where 5 < 1. We set 8 = 0.95 for simplicity. The whole procedure is summarized in Algorithm 2 The convergence analysis when 2 1/d can be found in (X Yin, 207). When < 1 1/d, suppose Algorithm M returns the optimal solution, we can get similar convergence result as the case = 1/d. Empirically, we found that there is no need to find the exact solution for the subproblem and instead we just perform Algorithm for few itcrations, which can still provide satisfactory result. Currently, proving the convergence is out of the scope of our paper.
A.2 L-BFGS
Though faster than BCD, the computational cost per iteration of BCDE is high when is small because need to compute X (x(((()))))))))))))))) for d times in every iteration. One may consider the Jacobi-type
24

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 2 solve LRTC-ENR by BCDE
Input: D. M, K, A, fmax.
1: Initialize {x, sield [se(k] with [II,, let
repeat.
t 1.
for ........ d do
if t <== 2 then
6:
- O.
7:
else
8:
Compute Wj.t-1 by 16
end if
Compute X by
10:
11: Compute 1- by
Compute X (1) by IKC or Algorithm MI
12:
13:
end for
14:
Remove the zero columns x j E [d].
15: until converged or fmax
Output: T = I x1 x(1) X2 X (2)
x (d))
iteration (cheaper computation but slower convergence) rather than the Gauss-Seidel iteration in BCD and BCDE. In practice, we can use quasi-Newton methods such L-BFGS (Lin Nocedal, [98M to solve problem (2) even though the objective function is nonsmooth. Particularly, drop the columns of x (j E [d]) with ncarly-zero Euclidean norms for acceleration. The corresponding algorithm shown in Algorithum B.
Algorithm 3 solve LRTC-ENR by LBFGS
Input: D. M, k, A, tmax.
1: Initialize {x, (ill [iE(k]
with [I],, let
repeat
t
Compute the search directions by LBFGS.
Use line search to determine the step size.
Update x("), j [d].
For E [d], remove the columns of x() (i) with Euclidean norms less than a small threshold, e.g. 10 10-5.
7:
8: until converged or = fmax
Output: + = I x(2) X2 x! (2)
(1)
X (d)
Optimization for TRPCA-ENR
When p 2/d, we use alternating mininization solve the optimization of TRPCA-ENR because every subproblem has closed-form solution. When p == 1/d, we may, like Section A. use block coordinate descent with extrapolation (X Yin, 20R However, the additional variable & further slows down the convergence. We hence propose to solve ( by the (nonconvex) alternating direction method of multipliers (ADMM) (Wang et al], 2015). Specifically, by adding auxiliary variables ( -ー we reformulate (0) as
2 D - -x() (x)))000) EGD) l|2 + AoR
(1) jeld hE(() + Ael
minimize (X pa
E
subject to ( X x jj = 1,,, 1,2,...,d.
"The implementation this paper based the ménFune MATLAB toolbox M. Schmidt: http://vwu.c ca/ #schiidta/Sofffare//iiitt htmll
25

---

Published in Transactions on Machine Learning Research (01/2023)
Let { be Lagrange multipliers and solve
minimize
D
- (x)0(0)) E(j))
(XOL
2
(16)
h
d
d +
pd + xellE111
Σ E(r()) -x()-x(), z + 6 1 12. 2=1
where y is the augmented Lagrange penalty parameter. Then update (x(i, y and & sequentially to minimize
[ and update (z 1d lastly. The procedures are summarized into Algorithm H where
x - ( + z
(1x (0))0o))) + pl)
(17)
r1 Dxe/1 (x(1) Z6//1/
(18)
z z + m1 (,1)) -x(
(19)
&, = VxA D x X2 x (2)
x
(20)
V is the element-wie wise soft- toft-hhresholdig operator Parikk et all 2014 defined by
1 (v) sign(v) max |al Xe).
Algorithm 4 TRPCA-ENR (p= 1/d) solved by ADMM
Input: D, li de de; n, Imax- Whle 1: Initialize {xe JaEl with [T];; for j = 1,..., d, let Yo x and Z = 0; let t = 0 and E = 0.
2: repeat
1 1. for 2, d do
5: Compute (1) by
Compute Y by
Update Z by 114
8: end for
9: Compute E, by (21)
10: until converged or fmax
Output: T = I X (1)
X2 x X (d)
In [ when p & {1/d,2/d 2/d), the optimization becomes more difficult because all d groups of the regularizers are nonconvex and nonsmooth. Thanks to Theorem & especially its (b), we can obtain arbitrarily sharp Schatten-p quasi-norm regularization by using only one group nonconvex and nonsmooth regularizers on the component vectors. The corresponding problem is
k
d E 11))) j=2
minimize (m!") p
D
x
o
(d) x
E
1
+ de Ae|(E]]
(21)
1=1
We propose to solve (21) by ADMM with the iteratively reweighted update (Algorithm W) embedded, which is shown in Algorithm E. In the algorithm, for j 2,...,,, d, the subproblem of x!") has closed-form solution, which makes the algorithm more efficient than Algorithm H especially when d is large. Note that the time complexity per iteration of Algorithum M and Algorithm B are od + dk + (d + 1)knd) and O(dk2n + d + (d + 1)knd + tnkkn) respectively, which are similar because tn is much less than (d+ 1)knd for high-order low-rank tensors. If p < 1/d and we do not use the asymmetric regularizer given by Theorem (b), the time complexity per iteration of the optimization is which is higher than that of Algorithm El
3 +(d+ +
26

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 5 TRPCA-ENR when p 11/d.2/d)
Input: D, ki 9, Xz, de; 14, fmax-
1: Initialize { jEld with (LI)); let t = 0 and & = 0; let Yot)) = =x and 2 0.
2: repeat
3: t 1.
4: Compute X (1) by (TZ).
Compute Y (1) by Algorithm M.
6: Update z() by (I
7:
for 2....... d do
8: Compute x ( by x (D (0) (1xx [000))) )ad
9: end for
10: Compute & by (20)
11: until converged or Imax
Output: F = I X X2 X X X (d)
C More experimental results
C.1 Theoretical bound v.s. empirical error
We apply LRTC-ENR (with symmetric regularizers) to the synthetic lensors used in Figure M and Figure D, where we let the noise-signal ratio be 0.2. We let A
[ - 1 x)) /e", where 8 max (1 oo: || [bo)- Now in Figure we compare Á with the theoretical error upper bound A defined by (G) A is in log scale for better visualization. We see the empirical reconstruction error is much less than the theoretical error (upper) bound. One reason is that the bound involves e², which is much larger (often 100 times) than the average of square entries of D and X.
given by different q (p-0.02)
10-1
decay rate
decay rate
0.35
decay rate 3
decay rate
0.3
10
decay rate
0.25
decay rate
4
0.2
14
decay rate
0.15
decay rate
0.1
decay rate
10
decay rate
0.05
decay rate
decay rate
10-5
0
0.2
0.4
0.6
0.8
0.0050.05
0.2
0.4
0.8
Figure 13: Left: theoretical upper bound A (Theorem 0 Right: empirical reconstruction error Å. The sampling rate p is 0.02.
C.2 Iterative performance of LRTC-ENR
Figure [- shows the value of the objective function and relative recovery error of LRTC-ENR in each itcration on the synthetic data used in Section m We see that the optimization converged quickly and the relative recovery error decreased when the iteration number increased.
27

---

Published in Transactions on Machine Learning Research (01/2023)
x10
8
0.8
6
relative recovery error
objactive function
5
0.6
4
3
0.4
2
0.2
0
0
50
100 iteration
150
200
Figure 14: Iterative performance of LRTC-ENT EETC-EENRRAE (p 1/3 (Yang et all, 20166)
C.3 LRTC-ENR on higher-order tensors
We compare LRTC-ENR with HaLRTC, KBR-TC, and BCPF on a synthetic 4-order tensor of size 30x30x30x30 and rank 50. The relative recovery errors (average of ten trials) are reported Table LRTC-ENR (p 1/3) outperformed the baselines.
Table 4: Tensor completion on 4-order tensor of size 30x30x30x30. The data generating model is similar to the used in Section 5.lIl In LRTC-ENR, we p 1/3
(Yang al. 20T)).
missing rate
methods
0.7
0.9
HaLRTC
0.98
0.99
KBR-TC
0.34
0.67
BCPF
0.11
0.21
LRTC-ENR
0.03
0.05
D Proof of the theorems
D.1 Proof of Theorem M
()) Proof. Let a!!)) =a: where |z (1) 1. Then 11
||x
11
agj
=
We have
1/d
(10
11a
Σ
II
a U pppa
Σ
12.19/d
in which the inequality holds according to the AM-GM inequality. When aa 0:2 ...Oid |A/2//, the equality of AM-GM inequality is true. Replacing with pd, we have
pd
1=1
28

---

Published in Transactions on Machine Learning Research (01/2023)
D.2 Proof of Theorem 2
Proof. (1) We have
d
*
1/9
2
1
+
-
|
1)
Σ
Σ
1 11 +
Σ f=2
| 11)
9
1=1
y=2
k
1/4
1t 12
+
d 1)
II
||
11
q
1=1
1=1
2=
k
d 11
14-0-0
Σ
+ d 1)
q
+
qd 9 k
|1.1
1+ 2
1 + gd - 9
|
|x|]
(1+gdd 9)
S 000000-00>
(2) We have
d
k
2/g
d
1 + Σ
|a(0113)
= Σe
Σ
x
(1)
119
+
> (12)
jm
5
1//4
d II
2+gd
2
+ d - 1)
II
||:2]
(
i=1
1=1
j=2
2+ 9
Σ
2
d - 1)
II
|
( 1/2
9
im1
2 gdl
2+ad-a
2g
2 qd 9
2g/ (2/(2+gd-0)
(20/(2+00-0)
q
q
The equality in the second row of formula (1) (also (2)) holds when all terms in the parenthesos are equal, for each i.
D.3 Proof of the last two in Table II
Proof. Recall the definition of Ai...., dp- We have
164/5
k
||o
111 + ||ae
+ ||=c;(0) 1I)
5
1=1
161/5
k
||,o(")1 (11
21 _ || (2) || + / |10
1
(3)
||+
1
|
(3)
||
5
2
1=1
164/5
k
1/5
Σ
(1)
122 a
(2)
|||
(2) ||| .m
(3) |1|00 (00
5
16
1=1
1/3
Σ
(1:08(2)
|1 (2) 1 (000000))
2//2/5 > || X
2/5
12/3
29

---

Published in Transactions on Machine Learning Research (01/2023)
Similarly, we have
81
||
1| + |
+ ||,! ||,o{
7
81//7
||00
1013
+ Σ
3
100
(2) + 3 | (3) 1))
7
3
==1
817/7
|| (011 1/7
|2
(2)
7
36
(112)" (1) |||| m2?2)
|1| (00
1//33/2 2
|| S///
D.4 Proof of Theorem E
First, give the following lemma, which is proved in Appendix P 1.
Lemma 1. Let 2.n.2 = (X E Sgn rank(2 S k; ||*1|s S 1}. Then the covering numbers of S with
respect to || l1ss satisfy
log ( ()) S ccd++ 1) (2
where e > 0 is universal constant.
Proof. We follow the idea of Theorem 4.3 of (Hinrichs el all 2017) and analyze the entropy number first.
According to the monotonicity of dyadic entropy numbers, it is enough to let n = 2 and = 22,23, where 1 a < 3 are natural numbers. We have n/n = 2-8. Let X E St,,p with sb = 1. The orthogonal CP (1)
decomposition of X' is denoted by X' = Ei s ou, u, and 81 2 s2 2 ... 2 sn. We define
X
1
(2)
(d)
s = -s,, Os......... .))
(22)
mm
and, for j 2.3,......
n
2
X, Σ 3 o u
(1)
(2)
ou!"
8, = (O..... $2........ 821 821-1 0, O).
(23)
It follows that rank( (), S 2 E [8].
Then have || 1, and j = 2......, B,
1/4
2
| |251|s
Σ
<
12i-1 1)-1)) 1/u = -(001)//0 1) 1/p
(2)
1=26-1
(24)
1/p
2
<2(111//1
< (20-11110-11/))
25-1
1=1
30

---

Published in Transactions on Machine Learning Research (01/2023)
where the last inequality holds because of Σin1 88 S Now we can decompose X as
x=
X +
22 2
(25)
Suppose q 2 p, we have
A
||
Σ
Σ
9 P
28
2=
1=
t= 2
2
(26)
1
Σ
Σ
20
2n
2
8(g
/)/p X
53
X
= 2 8(a p)/p
/)/1
[
S
A(a -(a--)(12 p//p
It follows that
8 X
X3
=
=||x8| 57
S 228(1/4-111),
i=1
8/
We focus on the case q = 2.
We see that 20/-1(1/p-1/1) E ST.=22 Let N₂ S S2 be an cy-net,
j E [8], and define
: =
2 (j 1/-1))//-1////
1/2) Z; E, j j 18]
Then N an e-net of Stmpp with yb
|| Ilss. where
2 ( -0-00000 2201/221/11///
j=1
and W| -1, |Ng1-
Now let 6 = c2l: -220--011/p11/21) where e is the constant in Lemma M. We have
8
2 11- 10-9101/--1/2100-9 2201/211/p)
- (1 (11)))1)---)) 1/2)
Σ 1=1
2(0 + 2211/221/9))
<c'2 50'2-8(1/8 8(1/p-1/2)
1/p-1/2
n1
where d' constant. Then we have
c'
2p/(2-p)
17 S n
(27)
31

---

Published in Transactions on Machine Learning Research (01/2023)
Using Lemma M and the definition of Nj, obtain
02'
c(d+1) 1)
log [V] = log [
S log II
-20-B11/-11/242
j=1
j=1
f
-2--
d25-1
+ +22-1 log (d 1)2(8 1)2(0-51000112211
11
2
==1
8
dn23-1 ((B-))(1/p 1/22/ 1) log (d+ + 1))
j=1
(28)
5(1/p 1/2 1)dlog(d+ + 1)n Σ 2/-1 (B - j)
(1/p-1/2+ 1/ 1)n2 Σ 20- (B (8-1)
5(1pp11/2 - 1/2
- 1/2 1/2/p-112++)mddlg c 2p/(2-p)
Now using a general vp instead 1, we finish the proof.
D.5 Proof of Theorem g
Before proving the theorem, we give the following lemma.
Lemma 2.
Let S be set of d-order hyper-cubic lensors of side length Suppose the e-covering numbers of S with respect to the Frobenius norm are upper-bounded by B. Suppose max||| || S E. Then the following inequality holds with probability at least 1 2n -d
2e
dlogg + log B) 1/4
sup X
D
X1F
Pa D - -D-x))lF
+
Vl
V/Ω
2/22
The proof of the lemma be found in Appendix DEC
Now prove Theorem as follows.
Proof. According Theorem B, the covering numbers of Sp.- with respect to the Frobenius norm satisly
(p/(2p))
log 1 (1/2+ md (log(d+ + 1))
log B,
(29)
32

---

Published in Transactions on Machine Learning Research (01/2023)
where 0 is universal constant. Now substituting log B into Lemma D and letting CrEVdn, get
sup XES
D
X1EF
Pa(DD
x)11F
Vnd
/12
2p/(2-1)
1/4
dlogn + (2 + Ind (log(d + 1))
2e
2s
V122
2|12|
||
(p/(2-p)
1/4
(30)
dlogn + (2 + nnd (log(d + 1))
2CTEV 2cTEVdn dn
crv
2e
2/12|
| evdn
(p p)
( + mmd (log(d + 1))
<de
where we have let and o' is universal constant. This finished the proof.
D.6 Proof of Theorem
The following lemma (proved in Appendix D3 will be used in the proof of the theorem.
Lemma 3. Define B21 = {X E Bunk
X 2.g S 1}. Then the covering numbers of B with respect to
the Frobenius norm salisfy:
(a) (B [|F E) S (n + log(ek))) 29/(2-9), 4) when 0 < q < 1,
(b) log. (B || c) (n 1)/ae -21 log(2nk),, when q 2
where Cg = 0
x, x() ..... Xa (d) be the CP (or Tucker equivalently) decomposition of X Sh where I super-diagonal. tensor of 1s.
Proof. Let X IIXx,
33

---

Published in Transactions on Machine Learning Research (01/2023)
Let X = I x() ... xa x and denote ||C||s. Let |X6) - x s 2II 35', , [d.. We
have
| - X
= =| x x X2 ... x X I x X X2 ... X x ||
= =|I x x
2.... Xd ( II+ x X (1) x x X(1)
II x1 (1) X2 X X (d-1) X X (d)
= II x1 x11) X2... x X (d-1) X ((1)
- I x1 (1)) X2... X x(1111
I X1 x(1) X.... X (X (d) (X -x(d))
|F
+ II ( X2 xd-1 (X(1-1) ((--)) x 8 1
+ + I x1 (x (1) ) X2 x ... xa 8
1 opl
X (1) lop.... || (d 1lop | (d) X |1
+ | oop X llop ... || (d-1)) X (dd-1)) || X ( 1lop
+... + |
| (1) x
(1) X
lop (d llppl ( llop
c +
c
................................ +
d
d
=c
Denote @ = 11 T5.
When 0 < < 1, the the covering number of Sk d,n.g can be bounded as
doprag (5) 73
2// 4)
NSS |l (I II exp cg(n + log(ek))
6
where is a universal constant. Tt follows that
log. DogN(Sh ll Ill,e e) s c(n + log(ek))
d
doog (
20/(2-0)
9
where e is constant.
When q 2 1, the the covering number of Sh,n, can be bounded as
ddoay (1) -1 7/
NiS ll pl < II exp ('nk2(0-1)/0 log(2nk)
==1
where we have converted the ceil operation into multiplying a constant d' for simplicity. It follows that
doba ()))))))1
ls mm ll e) e) <c'
1)/9 log(2nk) E
D.7 Proof for Theorem
The following lemma provides a sample complexity bound for transductive learning.
Lemma 4 (Corollary of (EEYany Pechyony, 200g), reformulated). Let F be fixed hypothesis set and suppose suP,.IXER / (Yy, X1)) S 7t. Suppose fixed set S of distincl indices is uniformly and randomlly
34

---

Published in Transactions on Machine Learning Research (01/2023)
split to two subsets Strain and Stest; where random split, we hame.
|Stest|
Strain
Then with probability at least 5 over the
l e(Yi,, Xty) + (Srtriil + |Seest 1)
Σ
((Yi,
Σ
Rs((eFF)
Stest
Serainl
Straiu
Seest
Etes)
(kd))Suaii
(31)
11 (1Strainl + Stest
(IS urain
Scest 1)
+ 37e
log
SSeusill Stest]
Strain
Swest
Before proof, we give the following lemma, which is a variant of the Dudley entropy integral bound on Rademacher complexity.
Lemma 5 (Theorem 3 of (Schreuder, 2020).. Let F (s: X R3 be any class of measurable functions conlaining the uniformly zero function and let Sn(F) supyer || Then
12
Sn(F)
Rn, S inf
4T +
(32)
T20
vn
In the lemma, [ is defined as [If
= E1 f(X))² which means
N(FF
NF(F. ||,, VTC).
(33)
Then we have
12
Sa(F)
R₂ (J)
inf
4T
log.N(F, 11 II, Vnc)dc
730
Vn
(34)
4T
12
S.UVVE
inf
Vlo.N(FFF 1111,
7>0
Vn
Now we use Theorem 5 and in LRTC-ENR. When
62 to obtain the Rademacher complexity of the tensor decomposition model
1, we have
45
12
[
c(n log(ek))
d Σ
ddag
(5)
x
(F) S inf +50
de
S122|
Q
7GE
21
47
12
c(n + log(ek))
d
(i)
x-
f p [5
inf r>0
2 de
[
q
45
12
c(n + log(ek))
dopa (1)
(2 (2-9) 9
((EV (22))
2-29
inf 750
2-4
2-4
S22
q
7/3
2 2q
(35)
46
+
12
c(n + log(ek))
Σ
dépo
(1)
2-q
2 (2
(EV
(2)
2-29 2-
[22
[22 \
9
2 - 2g
1=1
21.
(n + log(ek)) (
[22]
2-1
doa (i)
I
12
q(2 2g)²
7/1
1=1
(n + log ek)))( =212
1
d
(5)
2-
q(2 - (2
Eni
35

---

Published in Transactions on Machine Learning Research (01/2023)
where d' is suitable numerical constant.
When q 2 L, we have
47
12
dooa
(
g(1)
2
(F) (F)
inf 720
cnk 11/4 log(2nk)
Σ
de
[2
[02]
Nye
4T
12
d
doog 7j
(3)
rovial
= inf 720
cnk2(g-11/) 11/9 log(2nk)
E de
V192|
(36)
4T
12
deprad ?5
inf 720
enk 11/9 log(2nk) 2nk)
log
[22]
|22|
T
d
doaa (5)
2
nk2(g-1)/9 log (2nk)
log [S2].
[22
7j
1=1
where d' suitable numerical constant.
Note that
of (E)
(37)
where ne the Lipschitz constant of function In this work, is the square loss, which means ne 4s. Finally, integrating (S and (3Z) with Lemma El and renaming the constants, we get the desired results.
D.8 Proof of Corollary II
dda!?" og
Proof. In Theorem letting 0 = Ei=1
we have
d5
0
(a
(38)
where t 2 or (2 q) Recall that in the proof for Theorem D, the equality holds only when 011 = 0:22 = ... = |A, 1/d for all i [kt]. Here we have ag = (Eie 2/P That means we can get
X syya only when ag
(1) = ag =... ag ||
Sppa"
1/d Then we have
( (d7d-1)
0 < d
||
t/d 1874"
(39)
Now in Theorem we have
CiK
nk2(0-1)/4 (on(k)))dd
ddyd=1 2
||*;1
||
2/d 15,1d
log [S2|
if y 2
BR S
C2k
(n+tlg(ck)) 9) 2-9
dgd-1
29/(2-9)
||
(g/(2-4)/d Saaa
if < <1
[
0(2-2q)
Letting g pd, we arrive at
CiK
nkk((dd-1)/ap 1)/pd log (2nk)d (jdd1)
|| 113 2/d
log [S2]
if p 1/d
BR
O2K
(n+tlg(ck)) pdl d=dd-1
2pd/(2 (2dp/(22p))))) pd)
| 1211332/
2p/ (2-pd)
Ω 1
if < 1/d
pd[2 od(2-2pdj²
36

---

Published in Transactions on Machine Learning Research (01/2023)
Now rename NR as the upper bound, we finish the proof.
D.9 Proof of Theorem Z
Proof. The following three lemmas will be used. Their proof are in Section E
Lemma 6. For any R7 and O for, the following inequality holds
||/|| S p/2
1/ ||
(40)
Lemma Suppose the entries of N E Rnou are drawn from o2) independently. Then the following inequality holds with probabilily al least 1 2n-d
IW s 2020 dn log(5d) + (llg(nn..
Lemma Suppose the entries of N Rnee are drawn from NNO, o²) independently. Then the following inequality holds with probability at least 1 - 2n-
W I 20 / dlog(n).
Let & be the optimal solution of (III) We have
D x E S
D X' - E
(41)
Since X= + + E,, we obtain
+ + -- X 3
(42)
It follows that
X2 - 1 + 11 - E1
2(X" Nx, -((x" E2 - E) 2(E E,A²'
(43)
22 X E11s IV' -21EE- -Ell1 (112* -111 +lw0
Using Lemma
we obtain
X - 2 1ss ST. S/11:/2112 - 1111 |1 - 1x11'== + + 11 111
(44)
$//"1 - -81l + -
and
3[ ε1| -0-1 STz v/ 12121111' -11 ||E- Elp + r 1
(45)
STz 4 12 - El 2R 272- Rg
which hold for any 7 > 0 and
> 0. Substituting B and
45
into
we have
|X 1 + || - E1E
2T 2/2 / 2R N ||a||x** - 111FF
(46)
+ 2 // 2R (1x-- 11x-x11- 11 + 1| (10 11E- 11ll
+ 171 1 W/
-472-- ne' (122- - 20 + 11
37

---

Published in Transactions on Machine Learning Research (01/2023)
For convenience, let
| X
8 3 E
1 2r 2/2 V2R | ||
2 = 2Tz 12 215 (1 - -x + 1l0%
03 = 47 - R |
12 + + - Red (120- - 2 + 110%
20 2 1 1000
82 W lo00
Y 2 \
We rewrite (iG) as
u² + 2² + +2
S(a + c2)
(47)
S(c + 02) o x2)
Because C3 > the quadratic inequality of vu² +2 has non-emply solution. We have
max (, v2(c + +2) - 22(c1 + 02) + 4c3
V2(a + 62) + v 2(1 + )2 + 4e3
S v2² +2
(48)
2
Let TI = y and T2 = 2a +
We have
V + 12 22 v Rs + 2(2a - VVVVV Re
-2/ (11-8 11-8VV22
RR- RS (2a + -31-- 4 v Rio0
+ + (2a + 3)2 Re
(49)
-2---3 / Rh + 2(22 + 832--1 v Re + 222 7--2 R + (2o: + -3-- v Re
-(2 (2+2 3/- / RR + (2a + - L/= V Re
It follows that
u² + 0² 5(12+8v2) (,'- + (2a + 13)1- +
Re
(50)
<(4 16v2) (,²-PR + (2a + 2) Re!)
Using Lemma Ø and Lemma E for y and B3 respectively, we have
| 81 + 1| -
<(24+ 16V2) ((2v20 / (5d dlog(n)
2-p
Rg + (2a 20 20 / /dlog(n)
2-
Rg
(51)
with probability at least 1 4n-d, This finished the proof.
38

---

Published in Transactions on Machine Learning Research (01/2023)
E Proof of the lemmas
E.1 Proof of Lemma II
Before proof, we restate Lemma 4.1 of (Hinrichs et all 2017) here.
Lemma 9 (Lemma 4.1 of (Hinrichs el all 20T7)). Define Vi = E U = Ik, E, n).
Let 0 <<< 1. Then
(c)
(c) ((n-(x+1)/2)
N(VE || -1l--lllllee- -lop, c) S
where > O is universal constant.
Proof. Let X' = C x1 x X2... ... Xa X be the orthogonal CP (or Tucker equivalently) decomposition of X E Sam. where C is super-diagonal. We have |Ci|s ||diag(C)]lz S 1. Then the covering number of C with respective to || llst is equal to the covering number of diag(C) with respect to || ll2. i.e.,
Wel s (3c-1) According to Lemma B. the covering number of x with respect to || - llep satisfies k(n-(k+11/2)
Wxxol S (ce-2)
, E [d]. We have
11 21ss st =||c 11 ( X2 x x(d) C X1 x1)
X2 ... x X (d)
5
=|CC x1 x (1) X2 X X (1) # X1 X (1) (1)
X2 X X (d)
#C x (11) X2 Xd-1 X xd X
... =C 1 X (1) X2 Xd-1 X (d-1)
x x (d) è x x1) (1) x2... Xa (00
(4)
$ 2 x1 (1) '2... ... Xd (X (d) -x
+ +|[C x1 ((1) X2 ... X (X X (d-1)) Xd X 11
+ [[C C) x1 (1)) X2 x ... xd X ( ||s]
S| 5 |X |X llp X (d-1)) 1) |lppl X (d) X (d) || lo
+ ||C||s s ||x (1) 1lap |X (d-1)
X (d-1) lop| x (d) llop
+ + ICC - -11ss || (2) |1pp X (2)
lap ... || (d- 1] |lop
X (d)
lop
=||0|| 5t | (d) (d) ll + ||C||s X (d=1) x (d-1) llp +
+ ||C||ss |x - x llop + ||c 1CC-Cl ClIss
Note that (a) holds owing to the triangle inequality of norms and (b) holds because the incquality ||AB|| |ss ||Allop op |B|s, (Bhatia, 2013 can be easily extended to orthogonally decomposable tensors. Now let ||C
Cllst S </((d+ + 1), and | 1 S e/(d+ + 1), jE E [d]. We arrive at
||
Elss S d+1 + +
c
Se.
d d+1
Then the covering number of L 2, can be bounded as
3(d+1)
k II [=1
cld 1)
1(o-(k+1)/2)
N d, |l -1ll-1lss els,, <
(d(
dk (x+1)/22)+
where d' is universal constant. This finished the proof.
39

---

Published in Transactions on Machine Learning Research (01/2023)
E.2
Proof of Lemma 2
Proof. For convenience, we define
1 ] [22
-Po(D-x)]lB ((x) 1 nd ID _iI X1
((x)
According to the following lemma
Lemma 10 (HHoefiding inequality for sampling without replacement). Let X1, X2...., Xs be set of samples laken without replacement from distribulion (2,..., , of meun u and variance o². Denote a min, 24 and b = max; Tt. Then
s 2exp (-a-(6- (s- (1--(--1))N(C a)3
201²
TP
Σ X
u
2
have
2/12//2
P Plhh- h| 21 1 exx
(T11- (192 1)/mzd)
where ç = =42.. Using union bound for all x E S yields
2/12/12
IP
sup [M(x) h(x) 2 s /||5|cx) exp
(1 (15) 1)/nd)(2
XSS
Or equivalently, with probability at least. 1 - 2n
52 log (15)
1
sup x
[Í(x) h-())())) -
2
nd red1 |2
Then we have
g( - sup [h(x() - h(22))
XES
22 logg n + log 1og(5))
2
[2
nd
nd [2]
Since Ivu - Vul S V Iu - 0 holds for any non-negative u and v, we have
V ((xx) vh(z)) s V())
sup E
Recall that c || 211 2 1P((X
X) we have
Vh(x)- - / /(x)
1
|D - xx11 - - -x011 s Vnd
Vnd
and
WM(x) Vi(xz) = P - - - - - !
It follows that
Vh(x) Vh(x))
sup Xes
Vh(xx) /Mxx)
V Vh((x) /M(X)) + VM(x)) vx(x))
< sup XEs
+ Vo(l2) + Vnd"
V12
40

---

Published in Transactions on Machine Learning Research (01/2023)
Using the definition of g(2) and letting 3d, we have
[(x)) vi())
sup X68
26
(5²
1
1
)) 2/4
(dlog log (S])
+
v [22]
[12]
na
2c
dllog n + log B)
1/4
v [22]
2/52|
E.3 Proof of Lemma C
Proof. Case (a) can be easily obtained by transforming the entropy number result of the special case
u = 2 (we have exchanged p and q) of Theorem 13 in (Mayer & Ullrich, 2121) to covering number. Specifically, let
(logekk/)) + 1/4-1/2
log(ek) + n
1/4-1/2
en S Cq
$ Cy
"
1
where Cy is a constant depending only q and Go O(1/g). It follows that
24/(2-4)
Cq cn
S (n + log(ek))
Then the covering number is bounded as
1og.V(B221 ll (IF,e)) S(n + log(ek))
Cg
(1/(2-a)
log
E
(n + log(ek)) (2-(2-g)
where cg = 0(14))
Case (b) is a special case of Lemma 3.2 of (Bartlett. et all 2017). Namely, in the lemma, letting X be an identity matrix and p g 2 and 1 + 1 = 1, renaming the variables, we have log |l (|F),)) s
1n/2(9-1)/9 log(2nk).
E.4 Proof of Lemma
Proof. Let S = {i 2 > T.. We have
| = ||sl|] +
Σ
S
SS + Σ
(52)
Since 2 < and <<pp 1, we have
7
| < V|S|||=|12+7
Σ
V|S|||=1|2 + +1'---10 11
(53)
iEg
On the other hand, we have
18|7 < Σ # ||
(54)
Combining
33
and
3
we arrive al.
|| S - - v 1211++ + -111||=1
(55)
7
41

---

Published in Transactions on Machine Learning Research (01/2023)
E.5
Proof of Lemma 7
This is special case of Corollary 2 in Tomioka & Suzuki (20114)
E.6 Proof of Lemma
Proof. The Chernof bound of Gaussian distribution indicates
Pl 2 t| 2e 25, (f1.Je..... ..... sa) E [n] [n].... [n].
(56)
Using Boole's inequality (union bound), we obtain
I
U
Wh
Σ
P PIWWssaa-d 2t). tl.
(57)
(j..a....aa))
It follows that
PII 51/21
2n "2 -00
(58)
Let 1 20 log(n2d). Then
P Wiloo 20 Vlog(())
2 2n-2
(59)
42


Reviews:
[{"review_id": "Mjf7yPwtvB", "reviewer": "Reviewer_ssb8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n1. The paper provides a good literature survey of existing works related to the propsed problem.\n2. Theorem 1 and Theorem 2 provide interesting variational form of the tensor Schatten-p quasi norm for CP-decomposed tensors.\n\nWeakness and Questions\n\n1. The paper writeup and presentation should be improved as its focus. Few comments related to this issue:\n\n\ta. The paper introduces the symmetric/assymmetric regularizers in Section 2. It also tries to justify the utility of assymmetric regularizers in Section 3. However, in Section 3, when the paper briefly discusses the optimization algorithm, no specific discussion is done for them. Does the paper suggest different optimization strategies for symmetric and assymmetric regularizers (since one class has less non-smooth terms)? If yes, then it should be discussed. Similar comment for Section 4.1. \n\n\tb. The discussion of generalization results in Section 3.2 should be improved. As an instance, the text below Theorem 4 has the phrase \".. a smaller p but not too small will lead to a tighter error bound ..\". Can such statements be concretized? For example, what does too small mean here. \n\n\tc. Regarding Figure 1 and similar toy experiments - While the intuitive example of error bound is useful in toy datasets, can some practical algorithm/heuristic be devised (for tuning p) from the given theoretical results?\n\n\td. The significance of the different theoretical results in this work should be made clearer. The paper should also discuss these results in the light of other generalization results on low-rank CP decomposition of tensors. \n\n\te. It is not clear how 'q' appears in LRTC-ENR (2) - for example see the sentence below fig 1 caption. Figure 2 also shows results w.r.t. q rather than p. \n\n\tf. If a section has only one subsection (Section 4 has only Section 4.1), then that subsection need not be made explicitly. \n\n\tg. The paper should ideally use the same size font everywhere in main text (except what is permitted by the style file). For example the discussion of fig 3 results is in smaller font size. \n\n\th. Figure 6 x-axis is not legible. \n\n\n2. In fig 3, it seems that LRTC-ENR symmetric performs similar to LRTC-ENR asymmetric. The paper states that \"the asymmetric regularization slightly outperforms the symmetric regularization in a few cases\". This seems incorrect as in plots (a)-(c), performance of asym-BCDE and sym-BCDE is similar while sym-LBFGS seems to do better than asym-LBFGS. Similar comment for (d), expect for p <0.1, when asym-LBFGS is better than sym-LBFGS. How does the paper reconcile the intuitive advantage of assymetric regularizers (in Section 2) with the empirical results?\n\n3. Rprecon is Tucker decomposition based low-rank tensor completion method. Its rank hyper-parameters should be different than CP-decomposition based methods. For example, Rprecon will take 3 difference ranks (r1,r2,r3) for d=3 tensor. Since the paper treats its rank same as CP-rank, it found Rprecon to have high computational costs. Please set (r1,r2,r3) for Rprecon according to the best practices of Tucker decomposition. \n\n4. In the experiment section, should not the results with Schatten-p quasi-norm p=1/3,2/3, and 1 be attributed to the formulations proposed in Bazerque et al.(2013), Yang et al.(2016), and  Shi et al. (2017), respectively? This is because these quasi-norms were first studied in these works. This may have a broader impact on the work's empirical contribution as the paper might need to empirically show the utility of non-standard p-norm values (those other than 1/3, 2/3 and 1) in the experiments. \n\n5. In Section 2, it is suggested that asymmetric regularizer (Theorem 2b) would be easier to optimize as it involves fewer non-smooth terms than those in Theorem 1. However, since Theorem 2b involves one non-smooth term, will not it make the optimization equally hard? It will be great if this intuition can be justified more rigorously, e.g., theoretically or empirically. It should be noted that empirically this does not seem to hold (see comment 2). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed a general class of tensor rank regularizers based on CP decomposition. This class of regularizers are monotonic transformation of tensor Schatten-p quasi-norm based regularizers (p<1). The paper propose two variations of such regularizers - symmetric and assymetric. Such regularizers enable minimize Schatten-p quasi-norms of low-rank (CP) tensors efficiently, without performing SVD. The paper employ these regularizers in two applications - low-rank tensor completion (LRTC) and tensor robust principal component analysis (TRPCA). The paper also provide generalization error bounds for LRTC problem with Schatten-p quasi-norm regularization and with the proposed regularizers. \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please refer to Strengths And Weaknesses section. It will be great if the concerns can be addressed. I will then revisit my recommendation. ", "broader_impact_concerns": "No comments.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "I46nxH1Wqy", "reviewer": "Reviewer_2bj2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe proposed family of regularizers is novel which includes the symmetric and asymmetric versions. Numerical results have shown they are useful in improving the tensor recovery accuracy. \n\nWeaknesses: \n1. Some definitions are confusing without a full explanation of each single notation.\n2. Complete discussion of exact recovery guarantees is missing.\n3. Although a standard ADMM is applied, algorithm description/convergence analysis should be provided in detail. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new class of tensor regularizers based on the mixed Euclidean norms of tensor CP factors, and then adopt it to the tensor completion framework and the robust tensor principal component analysis, respectively. The generalization error bound for low-rank tensor completion is discussed and provided. Numerical experiments on synthetic and image data sets have empirically shown the proposed performance. Overall, the work is interesting with certain novelty in the proposed tensor regularization framework. However, there are several issues that need to be addressed, e.g., clarity and organization. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. There are some minor typos and wording issues that should be carefully checked, e.g., \"syhthetic\" -> \"synthetic\" in the abstract, \"noise density\" -> \"noise level\".\n2. In Definition 4, what is the value or the proper range of $k$? Is it a pre-assigned integer or simply the rank of $\\mathcal{X}$?\n3. In Theorem 2, if $q=1/3$, then $p_1=1/5$ which is not included in Table 1. Besides, it would be clearer to specify the values of $p,q,p_1,p_2$ in Table 1 to get straightforward connections with Theorems 1&2. \n4. In the proposed model (2), should $k$ be replaced by $r$ since $\\mathcal{T}$ is a rank-$r$ tensor that is specified at the beginning of Section 3.1? In addition, if $k$ is a pre-assigned number, does that pose a hidden low-rank assumption on the unknown $\\mathcal{X}$? If this is the case, both proposed models in Section 3.1 may not be equivalent to the original unconstrained low-rank tensor completion models. \n5. In Figure 1, it is not clear how the different low rankness is assigned to get different decay rates. What are \"decay rates\"? Detailed description of generation of those curves in the figure should be given. Why is \"reducing $p$ is more useful when the decay is low\"? What is the usage of $p$ being small here?\n6. In Section 3.2, it mentions the \"generalization error\" which is not a common term and should be defined rigorously somewhere. \n7. In the comment after Theorem 6, \"a smaller $p$ but not too small\" is confusing.\n8. The organization of Section 5 could be improved. The computer configuration in p.10 should be moved to before Sec.5.1 if it applies to both experiment settings. Common comparison metrics should be defined or explained at the very beginning as well. On the right subfigure of Figures 3&6, the horizontal scale is strange since those values of $p$ are not evenly distributed. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0tATVCnssd", "reviewer": "Reviewer_Co8K", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n\nStrength 1: To the best of my knowledge, this is the first paper that extends the Shatten-$p$ (quasi-) norm from matrix to tensor under CP decomposition. The new (quasi-)norm is new and interesting. \n\nStrength 2: The rigorous theoretical analysis of the proposed tensor completion model is new and of theoretical significance. The covering number-based analysis sheds new lights on error analysis of tensor recovery. \n\nStrength 3: The empirical performance of the proposed algorithms is promising. \n\n[Weaknesses]\n\nWeakness 1: The writing can be improved by adding more explanations of the new notions. \n\nWeakness 2: The proposed algorithms seem a bit involved, and the implementation may require much effort in parameter tuning. \n\nWeakness 3: The relationship between the proposed norm and the matrix Shatten-$p$ (quasi-)norm seems not well explained. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper extends the Shatten-$p$ (quasi-)norm from matrix to tensor under CP decomposition. The proposed norm is applied for tensor completion and tensor RPCA. The authors also establishes upper bounds on the estimation error for tensor completion. Experiments on both synthetic and real datasets show the effectiveness of the propose algorithms. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "This proposal is new and interesting. I suggest several minor changes as follows:\n\nChange 1:  Before giving new notions with equations, it is suggested to add more explanations to make the new notions easier to follow. \n\nC1.1) Give interpretations of \"Definition 4. the inverse CP operator\". \n\nC1.2) In Definition 5, the set $\\mathcal{S}^{\\bot}_{d,n}$ is directly defined in equations. It is suggested to provide some literal interpretations for it. \n\n\nChange 2: The proposed algorithms seem a bit involved, and the implementation may require much effort in parameter tuning. Can the implementation be open-sourced with sufficient explains on the parameter tuning?\n\nChange 3: The relationship between the proposed norm and the matrix Shatten- (quasi-)norm seems not well explained. It is suggested to give such discussions. \n\nChange 4: Go through a thorough proofreading of the paper. ", "broader_impact_concerns": "It seems that this work has no  ethical implications. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As the reviews suggest, there are certainly new contributions to the norms' generalization and analysis of the problems. To this end, there seems to be no confusion in the reviewers’ minds on the merits. However, after having a deep look at the paper, especially at the experiments section, I feel certain things can be done properly (look at the comments of the reviewers) to show the benefit of proposed general norms or at least put them in the right perspective and not overselling them.

Statements like “The numerical results of LRTC and TRPCA on synthetic data, image inpainting, and image denoising corroborate the effectiveness and superiority of our methods over state-of-the-art baseline methods.” are not being justified from the experiments, and therefore, problematic. Please tone down such statements.

The font size of Figure 15 looks very odd.

I believe the paper can be accepted after some fair amount of revision that I would like to see and follow up:
1. both polishing the paper storyline and organization, and 
2. relooking at experiments to put the contributions in the right perspective, 
and hence, the decision. Please address all the comments of all the reviewers. 


Decision: Accept (poster)