Online Tensor Max-Norm Regularization via Stochastic Optimization
Authors: Tong Wu
Venue: Accepted by TMLR ()

Abstract: The advent of ubiquitous multidimensional arrays poses unique challenges for low-rank modeling of tensor data due to higher-order relationships, gross noise, and large dimensions of the tensor. In this paper, we consider online low-rank estimation of tensor data where the multidimensional data are revealed sequentially. Induced by the recently proposed tensor-tensor product (t-product), we rigorously deduce the tensor max-norm and formulate the tensor max-norm into an equivalent tensor factorization form, where the factors consist of a tensor basis component and a coefficient one. With this formulation, we develop an online max-norm regularized tensor decomposition (OMRTD) method by alternatively optimizing over the basis component and the coefficient tensor. The algorithm is scalable to the large-scale setting and the sequence of the solutions produced by OMRTD converges to a stationary point of the expected loss function asymptotically. Further, we extend OMRTD for tensor completion. Numerical experiments demonstrate encouraging results for the effectiveness and robustness of our algorithm. The code is available at https://github.com/twugithub/2024-TMLR-OMRTD.

Published in Transactions on Machine Learning Research (06/2024)
Online Tensor Max-Norm Regularization via Stochastic Optimization
Tong Wu
wutonggbigai..tt
Beijing Institute for General Artificial Intelligence
Reviewed on OpenReview: https: // openreview. net/ fttl/form? id- 13DpP30WmS
Abstract
The advent of ubiquitous multidimensional arrays poses unique challenges for low-rank modeling of tensor data due to higher-order relationships, gross noise, and large dimen- sions of the tensor. In this paper, we consider online low-rank estimation of tensor data where the multidimensional data are revealed soquentially. Induced by the recently pro- posed tensor-tensor product (l-product), we rigorously deduce the lensor max-norm and formulate the tensor max-norn into an equivalent tensor factorization form, where the fac- tors consist of tensor basis component and coefficient one. With this formulation, we develop an online max-norm regularized tensor decomposition (OMRTD) method by alter- natively optimizing over the basis component and the coefficient tensor. The algorithm is scalable to the large-scale setting and the sequence of the solutions produced by OM- RTD converges to stationary point of the expected loss function asymptotically. Further, we extend OMRTD for tensor completion. Numerical experiments demonstrate encourag- ing results for the effectiveness and robustness our algorithm. The code is available at http::://ggtabb..cco/m/ugttttiip
1 Introduction
In the last decade so, we have witnessed explosion in data generation due to the development of new, affordable consumer electronics and advances in data storage and communication technologies. Many information processing tasks involve data samples that are naturally structured as multidimensionall arrays, also known as tensors. Examples of tensor data include images, videos, hyperspectral images, tomographic images and multichannel olettronccehhalograplyy data. Low-rank tensor cstimation has attracted increasing atlention the research community owing to its successful applications within computer vision (Zhang) et al., 2014), data mining (Franz al. 2009), and signal processing (Sidiropoulos et al. (017)). In this work, spocifically, we consider observed threo-way data tensor 2, and attempt to learn low-rank tensor X' that best approximates grossly corrupted observations. This problem typically involves minimizing weighted combination of the approximation error and a penalty for the tensor rank.
This problem is well studied in the matrix domain, where the goal is to optimize the rank of the predic- tion matrix and this problem likely to be computationally infeasible. The muclear norm (Recht et al. 2010) and the max-norm (Srebro et al. 2004) are the two commonly used convex relaxations of the rank function (NP-hard). However, different from matrices, there are many tensor rank definitions because a tensor can be factorized in many ways. Common tensor decompositions include CANDECOMP PPAAAAAAAPAAACCCCC (CP) decomposition (Kolda & Bader 2009), Tucker decomposition (Tucker 1966), HOSVD decomposition Lathauwer et al.) 2000). tensor-train decomposition (Oscledets) 2011). All these decompositions consider low-rank structure in the original domain. However, there is an increasing realization that exploitation of low-rank structure in the frequency domain can lead to improved performance of many tasks (Lu et al. 2019 Song et al.] 2020). In particular, a new tensor decomposition method called tensor singular value decomposition (t-SVD) (Kilmer et al.) 2013 2021) has demonstrated that after conducting Discrete Fourier Transform (DFT) along the 3rd mode, 3-way tensor exhibit strong low-rankness in the Fourier domain.

---

Published in Transactions on Machine Learning Research (06/2024)
Several works for tensor robust principal component analysis (RPCA) relying on these decompositions are proposed (Anandkumar et al. 2016 Yang et al. 2020 Lu et al. 2020 Gao et al. 2021]. While these ap- proaches have been incredibly successful in many applications, an important shortcoming is that they are not scalable to large-scale tensor data because the memory requirements increase rapidly with the size of data. Moreover, such methods are all implemented in a batch manner, which cannot efficiently capture the dynamics of streaming data.
Motivated by the t-product (Kilmer & Martin 2011
rigorously deduce a new tensor max-norm for tensor decomposition. By utilizing the tensor factorization form of the proposed max-norm, we develop an efficient algorithm, termed online maz-norm regularized tensor decomposition (OMRTD), to solve tensor max-norm regularized problem. OMRTD processes only one sample per time instance, making it scalable to large-scale tensor data. We also extend OMRTD for the tensor completion problem, where low-rank tensor data, recovery is carried out the presence of missing data. Extensive experimental results on the tensor subspace recovery task illustrate that the proposed tensor max-norm always performs better than the tensor nuclear norm in dealing with large fraction of corruption. Effectiveness of the proposed algorithm is evaluated through online background subtraction.
The rest of this paper is organized as follows. Section brieffy discusses related work and Section 3 iintroduces some mathematical notations and tensor basics. Section presents the proposed OMRTD method in the presence of complete and missing data. We present experimental results in Section and provide concluding remarks Section f
2 Related Work
Low-rank models find applications in collaborative filtering (Srebro et al. 2004 hyperspectral image restora- tion (He et al. 2016), and background subtraction (Candès et al. 2011 To handle data contaminated by gross corruption, the matrix RPCA (Candès et al., 2011) decomposes the observed matrix into a low-rank component and a sparse component using nuclear norm regularization. The work in Srebro et al. (0004) con- sidered collaborative prediction and learned low-max-nort norm matrix factorizations by solving a semi-definite program. To establish the connection between the max-norm and the nuclear norm, [Srebro Shraibman (2005) considered collaborative filtering as an example and proved that the max-norm variant enjoys a lower generalization bound than the nuclear norm. In the large-scale setting, there are some efforts that attempted to develop efficient algorithms to solve max-norm regularized constrained problems (Rennie & Srebro, 2005 Lee et al. 2010 Fang et al. 2018). Yet, the applicability of such batch optimization methods is prob- lematic because of their high memory cost. To alleviate this issue, online learning approaches that are based on nuclear norm and max-norm matrix decomposition using stochastic optimization have been proposed in Feng el al. (2013) and [Shen et al. (2017), respectively. However, all these approaches are devised for 2-way data, thus limiting their abilities to exploit the intrinsic structure of tensors.
Besides the tensor max-norm used in this paper, there exist several different tensor rank definitions due to the complex multilinear structure of tensors. The CP rank [Kiers] 2000 is defined as the smallest number of rank one tensor decomposition. However, the CP rank and its convex relaxation are NP-hard to compute (Hillar & Lim 2013). To alleviate this issue, the tractable Tucker rank (Tucker 1966) is more flexible because it explores the low-rank structure in all modes. The num-of-nucleer--e norms (SNN) is defined as the sum of the nuclear norms of unfolding matrices (Liu et al.] 2013), which served as a convex surrogate for the Tucker rank. The effectiveness of this idea has been well studied in Goldfarb & Qin (2014) and HudnHnng et al.) (2014). But it was proved in RRomeao-PPaedee of the Tucker rank. Recently, based on the tensor-tensor product and tensor singular value decomposition (t-SVD) scheme (Kilmer et al. 2013), a new tensor rank called tensor tubal rank (Kilmer et al. 2013) is defined as the number of nonzero singular tubes of the singular value lensor in L-SVD. Correspondingly, a
& Pontil (2013) that SNN is not the tightest convex relaxation
new tensor nuclear norm is proposed and applied in tensor completion [Zhang & Aeron 2017): tensor robust PCA (Lu et al. 2020). and tensor data clustering (Zhou et al., 2001 Wu1 2023). As a tensorial generalization of k-support norm (Argyriou et al. 2012), the + #L-spectral k-support norm is proposed in Wang et al. (2021)
to exploit low-rankness in the spectral domain and has been applied for tensor recovery.
2

---

Published in Transactions on Machine Learning Research (06/2024)
Nonetheless, all these methods require memorizing all the samples in each iteration and they cannot pro- cess samples in a sequential way. To address this concern, several online methods have been developed for
streaming tensor data analysis (Yu et al. 2015 Mardani et al. 2015: Zhang et al.) 2016 Kasai 2019 Li
cct al. 2019 Gilman et al.) 2022). Among these works, Mardani et al. (2015) and Kasai (2019) obtain multi-
way decompositions of low-rank lensors with missing entries using the CP decomposition, whereas both
Zhang et al. (2016) and Gilman al. (2022) rely on the t-SVD framework. Note that Zhang et al. (2016) implements online tensor robust PCA using tensor nuclear-norm regularization, while our work adopts our proposed tensor max-norm for tensor decomposition. Indeed, since the tensor max-norm is more plicated mathematical entity, the development of online methods for the max-norm regularization requires more attention. Based on the tensor factorization form of the proposed tensor max-norm, we convert the problem inlo & constrained tensor factorization problem that is amenable lo online implementation.
3 Notations and Preliminaries
In this section, we introduce notations and some basic facts about 1-SVD that will be used throughout this paper. More related tensor facts can be found in Kilmer al. (2013 2021]. Throughout this paper, we use lowercase, bold lowercasc, bold uppercase, and bold calligraphic letters for scalars, vectors, matrices, and lensors, respectively. For three- way lensor A E Ruixxn Xmaxns its Ai)-th entry is denoted A.j.a. We use Matlab notation ;(),;,;), i(:,i;) and i(; or A to denote the i-th horizontal, lateral and frontal slices, respectively. Any lateral slice of size n1 x ny is denoted as A. In particular, we also use A. to denote the i-th lateral slice of A. The (i.j)-th mode-3 fiber is denoted by A(i, The transpose AT E R=2xn xxa is obtained by transposing each frontal slice of A and then reversing the order of the transposed frontal slices through ng. We use A fft(A., [.33) to denote the Discrete Fourier transform along mode-3 of A. Similarly, A can be computed from A using A ifft (1,3), The inner product between two tensors A and B in Xmaaxg is defined as (A. B) Eijj. A.j.B. B.j.k- The & and Frobenius
norms of A are defined as ||ll| = EigA |A. and ||A|| = Viih AA.,, respectively. For a matrix A, its (i,j)-th entry is denoted as Ar,. The i-th row and i-th column of A are denoted by anj and a respectively. The conjugate transpose of a matrix A denoted by A The f2,00 norm of is defined as the maximum l2 row norm, i.e., ||A||2, max; [/ The matrix nuclear norm of A ||||+ (A),, where (A)ss are the singular values of A.
Besides, for tensor A E I X we define the block vectorizing and its inverse operation as bvec(A)) AA (1); (2)): A (Rs)) E Baingxna and bvfold(bvec(A)) A, respectively. We denote A E China block diagonal matrix with its i-th block diagonal being the i-th frontal slice of A, i.e.,
A (1)
A (d)ag(A)
A (ma)
Finally, the block circulant matrix (circ(A) E Xaangg is defined as
(1)
A (mg)
A (2)
A (2)
A (1)
A
bcirc(A)
;
A (ms)
(ma
Desinition 1 (t-product (Kimmer & Martin 2011 B 1 xna is defined as
The I-product between two lensors E R Xn2 Xns and
C= b bvec(B))
R X
(1)
The t-product in the spatial domain corresponds to matrix multiplication of the frontal slices in the Fourier
domain; that is, C A * B is equivalent to C AB (Kilmer & Martin 2011). Note that when ny 1, the operator reduces to matrix multiplication.
3

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm (-SVD for third-order tensors
Input: A E R
A = fft(A,] [1.3..
for k 1,.... , 12 do
U,S V = SVD(AA (8)).
3:
U U, ( S, V( V.
end for
6: u = ifft(f,, (1.3), S = ifft (ff.(5.11.)) V = ifft(V.(]]])
Output: U R Kmy xns, V R 22ax"2X and S IR x such that A = U V".
Definition 2 (Identity tensor Kilmer & Martin 2011 ) The identity tensor I, muxxxnng is tensor
whose first frontal slice is the n x n identity matrix and all other frontal slices are zeros.
Definition 3 (Orthogonal tensor Kilmer & Martin 2011 A tensor Q E BR is orthogonal if Q
o O * $Q II.-
Now we introduce the t-SVD for third-order tensors.
Definition 4 (t-SVD Kilmer et al. 2013)). Let A E R X then it can be factorized as A U+S+V* where U E Th XRiXns and E X are orthogonal lensors and S R Xnaxng a lensor whose frontal slices ore diagonal matrices.
One can obtain t-SVD efficiently by performing matrix SVDs in the Fourier domain as shown in Algorithm I Again, t-SVD reduces to the matrix SVD when ny 1.
Definition 5 (Tensor average and tubal rank (Lu et al. 2020 For any A R Xnaxna, the tensor average rank of A is defined as
rank. (A) def
rank A) = rank(bcirc(AA)).
ng
n23
The lensor bubal rank (A) is defined the number of nonzero singular tubes of S, i.e.,
rank = #(1 ((i.
where S is from the t-SVD of A 4 VT.
Definition 6 (Tensor nuclear norm (Lu et al.
2020 ). Lel A = u+ V be the 1-SVD of A E IR Xn2xnn A|l (S = Ei= Sú,,1, where r = (AA).
The tensor nuclear norm of A is defined as
It known that the tensor nuclear norm is the convex envelope of the tensor average rank within the unit ball of the tensor spectral norm (Lu et al. 2020).
4 Method
In this section, we describe our approach for online max-norm regularized tensor decomposition. We begin our discussion by introducing proposed tensor max-norm and mathematically formulating the problem.
4.1 Problem Formulation
In this paper, we consider the problem of online recovering of low tubal rank tensor from sparsely corrupted obscrvations. Before going to the online scenario, start with the batch setting. Suppose we given third-order tensor Z E X xna consisting of N samples that can be decomposed as low tubal-rank component X and sparse noise tensor E. Our goal is to estimate the two components X' and & by solving the following convex program:
min | X.E
m + A11(E111 s.t. 2 x E,
(2)
4

---

Published in Transactions on Machine Learning Research (06/2024)
where || llmax is the tensor max-norm defined later that encourages X to be low-rank, and A1 0 is penalty parameter.
Recall that both the matrix max and nuclear norms are alternative convex surrogates for the rank of a matrix. Bounding the matrix rank corresponds to constraining the dimensionality of each row of L and R the factorization X = LR. (Srebro Shraibman 2005). The nuclear norm encourages low-rank approximation by constraining the average row-norms of and R, whereas the max-norm, which is defined ||||| promotes low-rankness by constraining the maximal row-norms of L and R. Note that the t-product in the spatial domain corresponds to matrix multiplication in the Fourier domain, i.c., X = LR Based on the property that || ng |X] (Lu et al. 2020 and the matrix nuclcar
[X min -. R [L |2,c
norm has an equivalent form
|X|| = R: 2 [ + [ Recht et al. 2010), the tensor nuclear
||:
norm can be written as the following tensor factorization form:
||
min CER"IXXXN RERVXPE Xxxxng
1112)1 [
1
[
X = C=
(3)
2nz
where r is an upper bound on the vensor tubal rank of X. As a theoretical loundation of the work Srebro et al. (2004), (rrebro & Shraibman (005)) provided the relationships between the rank, nuclear norm and max- norm as complexity mcasures of matrices, which gave us some intuition on why the max-norm regularizer could outperform the nuclear-norm regularizer in some applications, e.g., Lee et al. (2010) and Fang et al.) (2018). Motivated by this advantage, propose to define the maxxnormn of the tensor X' R" x using the same tensor factorization form by constraining all rows L and R to have small l norms as follows: Definition 7 (Tensor max-norm). The tensor mar-norm of X E R XNx is defined
X
mmxx
def
min
|| 2,00 ix = L R
(4)
CER REB Nxexns
where is an upper bound on the tensor tubal rank of X. We also have || |max = || IImax.
Now assume that the samples i(;, i= 1,..., N, are observed sequentially, our objective is to efficiently learn the low-rank component X' and error tensor & in an online fashion. To facilitate online optimization, instead of solving the constrained problem (2) directly, we relax the constraint by regarding it as a quadratic penalty, resulting
1 min 1 2 - L CT - E C.R.E 2
A1 111.00 R122, + A211E112,
(5)
2
where A and A2 balance the importance of each term in (5) Intuitively, the variable L corresponds to a basis for the clean data and each horizontal slice of R corresponds the coefficients associated with each sample. Notice that the size of the coefficient lensor R is proportional to N. In order to compute the optimal coefficients for the i-th sample, we need to compute the gradient of ||||2,,0. Moreover, each horizontal slice of RR corresponds to one sample, hence the computation of such gradient requires to access all the data. Fortunately, we have the following proposition that alleviates the inter-dependencies among the horizontal slices R, so that we can optimize them sequentially.
Proposition 1. Problem
5 equivalent to the following constrained program:
X1 I
min E.R.E 2
12 12-L E12 -
+
XellET11
s.t.
R 1R12,00 $1. 1.
(6)
Here, "equivalent" means the oplimal values of the objective funclions there exists an optimal solution (L","*, E** attained such that ||,00,,00 1.
5 and
(6) are the same. Moreover,
In the constrained program 6 the coofficients associated with cach individual sample (i.c., one horizontal slice of the coefficient tensor) are now uniformly and separately constrained. Let Z., R, and E, be the i-th lateral slices of tensors 2, R and E, respectively. We define
i ビ
def
से.
5

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 2 Online Max-Norm Regularized Tensor Decomposition
Input: Observed samples 2 E IR=xxXXng and parameters A and X2.
Initialize: Random basis Co E Ruixxxns, Ao = By 0.
for t = ...,, do
Access the 1-th sample ž,
3: Update {Ri, ;) by solving 100
4: Update the accumulation tensors:
A. A
B, = B.-1 + (2, - E7)
5: Update the basis L, (equivalently, L.) by optimizing the surrogate function:
L tns ( (T,,,AAA - tr(T.BB)) + A
L = arg min
2t
6: end for
Output: Optimal basis CN.
Equipped with Proposition we can rewrite the original problem 5 as the following, with each sample being separately processed:
N
min min R. 1=1
Σ
L, E
E
R.
R.
1)
2 | |2,000 S.L. Vi 1, I,...,,, k 1....,.... n13
R
12 < 1, (7)
where R. fft(RR, 1.3) and R, denotes the k-th frontal slice of R. This is indeed equivalent to optimixing the empirical loss function:
(k)
SN(C) def N +
A1
E(C, 2.)
L | 12,00
2N
where ((c,z) min min R (,,,,, 2 with -= R E Rexixxs Vk, 113 S 1}. We assume that each sample is drawn independently and identically distributed from some unknown distribution. In stochastic optimization, one is usually interested in the minimization of the expected loss function
f(C) E|e(C, E)
lim (C).
(9)
~0000
In this work, we first establish a surrogate function for this expected cost and then optimize the surrogate function for obtaining the basis in an online fashion.
4.2 Online Implementation of OMRTD
S The detailed algorithm is summarized in Algorithm 2 We start with an initial random dictionary Cy. The key idea is that at each
We now describe our online algorithm for minimizing the empirical loss function
iteration t, we first minimize the loss function with respect to (R., E., given the previous C,-1 by solving and then further refine the dictionary L, by minimizing the cumulative loss.
Optimize R. and E. Given C--1 in the previous iteration, obtain the optimal solution (R. Et by solving
[Ri ビ = arg min
1 2
2 L. R 11 2 11.
(10)
R
6

---

Published in Transactions on Machine Learning Research (06/2024)
We employ a block coordinate descent algorithm which alternatively updates variable at time with the other being fixed until some stopping criteria is satisfied. For the sake of exposition, we omit the subscript here. According to [Brtsekaas (1999), this alternating minimization procedure is guaranteed to converge when the objective function is strongly convex with respect to cach block variable. It can be observed from 10p that the strong convexity holds for & and it holds for R if and only if L is full tubal rank. For computational efficiency, we actually append a small jitter 2 | to the objective if necessary so as to guarantee the convergence (we set e 0.01 in our experiments).
We first compute an initial guess of R by
Reand = (CT C (I,) L (
(11)
If this initial guess Reand satisfies the constraint that Roand E P, we will use Reand as the new iterate for R. Otherwise, for each k; if R (8)
caadlll > 1, will introduce positive dual variable 19()) and solve
(k) 2
(k) 2
max min (2)
LR
22
1 - 1) s.t. (k) > 0, R 12 1.
(12)
R
The closed-form solution of 12 is given by
(k)
(I (IO) ((0+ (1, (Z
(k)
E
where I, denotes the r x r identity matrix. According to Proposition 2 of Shen et al. 2017). for each k, 3 (k)
R
la is strictly monotonically decreasing function with respect to 17 (8), This allows to search the as well as the dual variable 176 using bisection method. To be concrete, we denote
(b)
optimal R
R (1)) (10) (n) (k)* (0) L
(1)a (Z E
(k)
(k)
and maintain a lower bound ?h and an upper bound 722 such that R (A)
(n1)ll2 2 1 and || (k)
(12)ll2 S 1.
This cnsures that the optimal (B( lies within the interval 72] and we can find this value efficiently using
By comparing R (b)
bisection method outlined in Algorithm in Appendix A.2
(1)
17(2) (m + 72) (k)
with 1, we can either increase 7h or decrease 772 until R (x)) equals one. Note that || cand ll > 1,
which implics that the optimal value for (*)) is greater than e, thus we easily set m = 0. Once R is
found, we can update & using the soft-thresoolding operator (Donhho, 1995): E Sx Z L * R For
completeness, we list our method for updating the coefficient tensor and the noise tensor in Algorithm Appendix A.2
Optimize C: When (2,, Ri Eiji_ are available, we can update the basis C. by optimizing the following objective function
(C ; Σ E
R ED
A 21
1I
(13)
This is a surrogate function of the empirical cost function C(( defined in (9) in a sense that it provides an
upper bound for fe(C): gr (C) > f((C) (Mairal et al. 2010 Feng et al. 2013 Shen et al. 2017). It is easy
to verify that the minimizer of (13 is given by
C. = arg min
2, - L * RR; - E +
I 2
E
2t
2t
where& 3, = - E11 E R xtxn3
Ri = Ri...., Ri E Rxxxxx and E; = i,.,, E; E R xtxns,
Let L, bdiag( Li), Z, = bdiag( 2.),
R₁ = bdiag(R) R2,) and E; bdiag(E;). The above problem can be
7

---

Published in Transactions on Machine Learning Research (06/2024)
transformed into the Fourier domain as
1
X1 1
L arg min
1Zz
LR
- Eil1
21m3
arg min tng
1
(tr(L"LA,) - tr(( + 2ラ |2
1
(14)
2
Here, A. -
E R B, - trace operation. We again omit the subscript t in the rest of this paragraph. In order to derive the optimal solution, we first need to compute the subgradient of the squared 6,,0 norm, which can be done in a similar way as in Shen et al. (017)). To be speeific, let θ denote the set of row indices corresponding to the rows with maximum & row norm of L. Define Q E I xnins to be positive semi-definite diagonal matrix with Q * O if and only if E θ and all other entries are zeros such that Ei Q = 1. The subgradient QL. We then use block coordinate descent [Bertsckas,
R and tr(.) denotes the
of ! 1999) to update the columns of L soquentially; more details in Algorithm 6 Appendix A.2 Note that
2 I can be written as H 0 [(
H is diagonal matrix and off-diagonal blocks are zero matrices, we can write H as
H
def
H
H
In this manner, the subgradient of the squared 62 norm of L with respect to [ is Hç. By assuming that the objective function of [44] is strongly convex with respect to L, it is guaranteed that the solution of this block coordinate descent scheme always converges to the global optimum.
4.3 Complexity and Convergence Analysis
Here, we provide further analysis on complexity and convergence of our method.
Computational Complexity. In each iteration, the computational burden is dominated by the cost for solving (10). The computational complexity of 11 involves computing the inverse of na r x r matrices, matrix multiplications, and the (inverse) Fast Fourier Transform, totally O(nyráng + ning ng)... For the basis update, obtaining a subgradient of the squared f2 norm of L is O(nirna) and one-pass update for the columns in L in Algorithm 6 requires ((nr)2na).
Memory Cost. OMRTD requires O(nirna) to load L,-1 and 2, to obtain (R, E To store the accumulation tensor A,, we need O(r2ng) memory while that for B, is O(nrrg)) Finally, we find that only A, and B, are needed for the compulation of the new iterate L.. Hence, the memory cost of OMRTD is O(nrns)), i.., independent of N, making our algorithm appealing for large-scale streaming tensor data.
Convergence. In order to present the validity of the proposed algorithm, make the following assump- tions:
(A1) The observed samples are generated independent identically distributed from some distribution and there exist two positive constants ag, 01, such that the conditions on S 1 S aj holds almost surely for all t 1. This assumption is quite natural for the realistic data such as images and vidcos.
(A2) The surrogate function (C) in 13 is strongly convex. Particularly, we assume that the smallest singular value of the matrix AA, is not smaller than some positive constant B1.
(A3) The minimizer for E(C, 2) is unique. Notice that ? C, t is strongly convex with respect to and convex with respect to R. We can enforce this assumption by adding a term R function, where is a small positive constant.
| to the objective
Based on assumptions (A1), (A2) and (A3), we establish the main theoretical result of this work.
8

---

Published in Transactions on Machine Learning Research (06/2024)
Theorem 1. Assume (A1), (A2) and (A8). Let {Ci)121 be the solution produced by Algorithm Then the sequence converyes to stalionary point of the expected loss function [(C) when t lends to infinily..
The proof of Theorem 1 proceeds in the same following four steps in Shen al. 2017
(T) We first show that all the stochastic variables (R. E. Li are uniformly bounded. This property is important because it justifies that the problem we are solving is well-defined.
Proposition 2. Let (Rī, Colis be the sequence of optimal solutions produced by Algorithm
Then
1. The optimal solutions Ri and EÚ are uniformly bounded.
2. The tensors A,, and B, are uniformly bounded.
C. supported on some compact set L, there erists a positive constant 6₁, such that for all > 0, have || Ct.
Ci Corollary 1. Let (Ri, E, be the sequence of optimal solutions produced by Algorithm all t 2 1, we have
Then, for 1. ( Li, Rt) and E(L,, E.) are uniformly bounded from above.
2. The surrogate function, (e( defined in 13 is uniformly bounded.
Moreover, (c(C)) is undformly Lipschilz over the compact set L.
(II) Next, we show that the positive stochastic process (e(),) defined in 13 converges almost surely. First, we can easily show that (++1(C++1) ((() upper bounded by the set of measurable functions (((C,), C L} is P-Donsker (van der Vaart 1998), and the difference between the empirical loss and expected loss can be uniformly upper bounded by O(1/V)). Therefore, following the proof in Shen et al. (2017 Theorem 4), conclude that ge(C,) is quasi-martingale (iisk 1965) and converges almost surely.
le(.)) Then we show that [+1
(III) By establishing the mumerical convergence of the basis sequence { i.c., || Lelle (1/t)
(this step corresponds to Shen et al. 2017 Proposition 10)), we can show that the empirical loss function, fi(C,) defined in (8) converges almost surely to the same limit of its surrogate g. (C.)). According to the central limit theorem, (C.) also converges almost surely to the expected loss f(C,) defined (9). implying that (C())) and f(.)) converge to the same limit (this step corresponds to Shen al. (2017] Theorem 5)).
(IV) Finally, using the expression L R bvfold(bcira(E) bvec RR), we can derive that VS(C) is uniformly Lipschitz on C. Consequently, by taking a simple Taylor expansion, it justifies that the gradient of f(C) taking at C, vanishes as tends to infinity, which concludes Theorem
4.4 Extension to Tensor Completion
In this subsection, we study OMRTD for the case of data having missing entries. To be specific, let W [0, IR=.xNxns be tensor such that Waj,k 1 if Zijj j.j is observed and Wija 0 otherwise. The locations of the observed entries can be indexed by set Ω = j(i,j,k) Wij. 1}. We reformulate the problem for tensor completion by solving the following problem:
min _
MM
x El マタ
P + EzlEE11
s.t. Pa(M) Pn(2),
(15)
where P.t(:) is the orthogonal projector onto the span of tensors vanishing outside so that the (1.j. k entry of (s( is equal to Maj.k if (i,j, k) Ω and zero otherwise. We again minimize (15 by alternating

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 3 Updating tensor columns of M, R and E
Input: Partially observed data sample Po Po ( E RRuxxxx E R xxxxx and parameter X2-
Initialize: R E() (0) 0, 7- 1.9, (0) = 0.1, Mmax - 10 E 10-6, and Ç -= 0.
while not converged do M(c+1) P (+R(1
( + + + (
Pær (L R(() (
3: Update (R ((+1), E(stD) 1-1
using Algorithm F((+1) F(e) + (1()))(P (P&((M Pa 2)).
5: n((+1)- = min(yul(), ; )
6: Check the convergence conditions:
Pa (M((+)) - P& (2(2)) [))lF (((1)) -
1 ( <E.
8: 1=
9: end while
Output: Optimal M -M (5) R R ( and غ = {
minimization strategy. At the t-th iteration, when - given, the update for (Me, Rr, E.} corresponds to solving
(M: Rí Ei arg M.
1 IM f--1 - E12 + Ael s.t. Ps. (M) Pa. (Z.),
(16)
where S2 = {(i, t,), E 32. This problem can now be solved by using the Alternating Direction Method
of Multipliers (ADMM) [Boyd et al. 2011). Specifically, the augmented Lagrangian function of [6 is
M c. R E + A21 E
J Pa (M) - Pa (2.)) + -リ Pl Pa. (M) - Pa, (2.)),,
(17)
where I the Lagrange multiplier and p > 0 is a penalty parameter. The implementation of the ADMM algorithm is outlined in Algorithm 3 Finally, we define B, = (i=,M;; Et R, and the update of L, is exactly the same as in OMRTD. We dub this approach robust OMRTD (1OMRTD) in our experiments.
5 Experiments
In this section, we present several experimental results on both synthetic and real data. All experiments are conducted on PC with an AMD Ryzen 5950X 3.40GHz CPU and 64GB RAM with Matlab R2023b. We set A 22 = 1/ /n for
and we follow the default parameter settings for the baselines.
5.1 Synthetic Data Experiments
Data generation We generale the clean data tensor X 24 Do, where the entries 14 E Raxxxnng and VE Nxrxng are drawn i.dd. from (0, distribution. Here, we set ni 50 and n3 20. The observed data tensor Z is generated by Z X' E, where & is sparse tensor with fraction of p non-zero entries. The elements in E are from uniform distribution over the interval of [-10, 10).
Evaluation metric We evaluate the fitness of the recovered tensor subspace C (with each frontal slice being normalized) and the ground truth i based on the idea of Expressed Variance (EV) (Xu et al. 2010
1 CIL 1
tr((U +2 C C+T")(a;1) (r((Ut" +()(;;;1))
EV(U:
The value of EV ranges between 0 and 1 and higher value indicates better recovery. The Monte Carlo simulations are repeated 10 times and report the averaged EV of these 10 random trials.
10

---

Published in Transactions on Machine Learning Research (06/2024)
0.5
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
0.08 0.16 0.24 0.32 0.4
0.08 0.16 0.24 0.32 0.4 tubal rank /m
0.08 0.16 0.24 0.32 0.4 tubal rank /'m
tubal rank /'1
(a) OMRTD
(b) OTRPCA
(c) TRPCA
Figure 1: Performance of tensor subspace recovery using complete data under different intrinsic dimensions and corruptions. Brighter cells represent better performance.
Baselines For the complete data experiments, we compare the performance of OMRTD with OTRPCA (Zhang et al. 2016) and TRPCA (Lu et al. 2020). For the case of data having missing entries, we choose an approach that first performs tensor completion based on the tensor muclear norm (TNN) (Zhang & Aeron 2017 Lu et al. 2018) and then conducts TRPCA (Lu et al.) 2020) on the recovered data (TN++TRPCA) as the baseline.
0.5
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
0.08 0.16 0.24 0.32 0.4
0.08 0.16 0.24 0.32 0.4
0.08 0.16 0.24 0.32 0.4 tubal rank /n1
tubal rank /m
tubal rank /n1
(a) rOMRTD (r = 10%)
(b) rOMRTD (r = 30%)
(c) rOMRTD (7 = 50%)
0.5
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
0.08 0.16 0.24 0.32 0.4
0.08 0.16 0.24 0.32 0.4
0.08 0.16 0.24 0.32 0.4 tubal rank /ni
tubal rank /n1
tubal rank /n1
(d) TNN TRPCA (r (== 10%)
(c) TNN TRPCA (7 30%)
(f) TNN TRPCA (r (r= 50%)
Figure 2: Performance of tensor subspace recovery using missing data under different intrinsic dimensions and corruptions. Brighter cells represent better performance.
5.1.1 Robustness
We first study the robustness of OMRID in terms of EV value, and compare it to the tensor muclear norm basod OTRPCA and the batch algorithm TRPCA. In this set of experiments, the total number of samples N 2000. We vary the true tubal rank from 0.08n, 0.4n,, with a step size 0.04n,, and the corruption fraction P ranges from 0.05 to 0.5, with step size 0.05. The results are represented in Figure 1 Since
11

---

Published in Transactions on Machine Learning Research (06/2024)
0.98
0.99
0.95
0.9
0.90
0.9
0.0
0.98
0.7
0.96
C70024
0.96
0.88
0.75
0.5
500
3500
5000
500
5000
800
2000
3500
5000
500
2500
5000
number samples
number samples
number of samples
number samples
(a)
0.05
(b) 0.1
(c) p 0.3
(d) 0.5
Figure 3: EV value against the number of samples under different corruption fractions.
TRPCA accesses all the data in each iteration, it always achieves the best performance. We observe that both OMRTD and OTRPCA perform comparably in easy settings (i.e., few corruption and low tubal rank). However, in tough cases, OMRTD outperforms OTRPCA. For example, when the true tubal rank 12 and P p= 0.5, the EV values of OMRTD and OTRPCA are 0.8274 and 0.5840, respectively. In order to further investigate this phenomenon, we plot the EV curve against the fraction of corruption for some given tubal ranks in Figure 5 in Appendix A.3 Notably, when manipulating low tubal rank tensor, OTRPCA exhibits similar performance compared to OMRTD under low level of noise, e.g., the true tubal rank is no more than 8 and P is no more than 0.25. However, as the true tubal rank gets larger or the fraction of corruption increases, OTRPCA degrades faster than OMRTD, This is possibly because the proposed tensor max-norm is a tighter approximation to the tensor tubal rank.
Next, we study the effectiveness of rOMRTD the missing data scenario, where we set the percentage of missing entries 7 to be 10%, 30% and 50%. Figure indicates that TNN+TRPCA performs better than rOMRTD when t 10%. When the number of missing entries increases, the EV values of TNN+TRPCA drop rapidly, especially when the fraction of corruption becomes large. Finally, rOMRTD outperforms TNN+TRPCA for almost all different tubal ranks and p's when r 50%. The detailed plot of the EV curve against the fraction of corruption under some specific tubal ranks for t 30% is shown in Figure in Appendix A.3
5.1.2
Convergence Rate
We now examine the convergence of OMRTD in terms of the EV curve as a function of the number of samples. We first fix the true tubal rank to be 0.2m, 10. The results depicted in Figure B. As expected, TRPCA achieves the best performance since it is a batch method and it requires to access all the data during optimization. OMRTD is comparable to OTRPCA when the corruption level is low (see Figure 3a and Figure 3b) and the gap between the EV values for these two methods is below 0.04. When data are grossly corrupted, OMRTD converges faster than OTRPCA (sce Figure 3c and Figure 3d], which again suggests that lensor max-norm might be a better fit than the tensor nuclear norm when the signal to noise ratio is low.
We then compare the convergence rate of OMRTD and OTRPCA under different n1 's in Figure 4a. and Figure 4b The lubal rank of data is set to be 0.1n and the error corruption is fixed to be 0.3. We observe that when n1 = 50, OMRTD is generally slightly worse than OTRPCA and the gap between the EV values is below 0.004 for the same number of samples. However, when 100, OMRTD significantly outperforms OTRPCA. It attains the EV value of 0.95 only with accessing 1000 samples, whereas OTRPCA cannot obtain the same accuracy even using 20000 samples.
5.1.3 Computational Complexity
As we discussed, when we solve the dual problem to optimize R. the initial solution Reaud may violate the constraint. Thus, OMRTD inferior to OTRPCA in terms of computation. We plot the running time with respect to the number of samples for ni E (50, 100) in Figure 4c and Figure 4d which show that OTRPCA is about 2.4 times faster than OMRTD. When n, 50, OMRTD and OTRPCA take 76 seconds achieve
12

---

Published in Transactions on Machine Learning Research (06/2024)
1-
200
500
time seconds)
450
0.98
0.9
150
time (in E9501
400
0.8
100
250
0.84
200
150
0.92
0.7
50
100
0.6
0.05
0,4
0.8 1.2 1.6
0.05
04
0.8
1.2
1,8
0.05
0.4
0.8
1.2
1.8
0.05
0.4
0.8
1.2 1.8
number of samples..0*
number of samples x10*
number samples
number of samplesx10
(a) n1 = 50
(b) nl 100
(c) nl 50
(d) n1 100
Figure 4: (a)-(b) EV value function of the number of samples for nı 100). The intrinsic dimension is 0.1m, and the corruption fraction 0.3. (c)-(d) Running time as function of the number of samples for nı E {50, 1003.
Table 1: Background subtraction results and algorithm running time (in scconds) on CAMO-UOW dataset.
Methods
Metrics
Video
Video 2 Video 3
Video
Video 5
Video 6 Video
Video 8
Video 9
Video 10
Precision
0.7290
0.7873
0.6367
0.7698
0.6472
0.9883
0.9521
0.7343
0.7552
0.9646
Recall
0.2032
0.2237
0.2328
0.1903
0.1174
0.7209
0.1621
0.2334
0.1101
0.4262
RPCA
F- F-measure
0.3038
0.3311
0.3337
0.2982
0.1941
0.8288
0.2608
0.3476
0.1628
0.5557
Time
2641.1
130.1
255.5
258.9
265.5
247.3
207.9
359
265.3
382.2
Precision
0.5829
0.6281
0.5712
0.6632
0.6665
0.9541
0.7954
0.6021
0.7197
0.8734
Recall
178
0.1019
0.1045
0.0926
0.0861
0.3865
0.0826
0.1037
0.0530
0.1786
TRPCA
F-measure
0.2599
0.1489
0.1673
0.1613
0.1483
0.5411
0.1460
0.1635
0.09499
0.2761
Time
1086
518.4
1111
1102
1121
1103
933.8
1526
979.9
1490
Precision
0.0435
031636
0.1711
0.0602
0.0404
0.1339
0.083
0. 0.1226
0.0372
0,1528
Recall
0.1923
0.2859
0.4174
0.1990
1278
0.7105
0.2071
0.3010
0.1231
0, 0.4325
ORPCA
F-measure
0.0669
0.1715
0.2311
0.0910
0.0593
0.2160
0.1118
0.1657
0.0536
0.2165
Time
23.13
12.17
20.75
21.51
30.99
19.32
11.47
54.31
20.63
21.73
Precision
0.6806
0.7073
0.6510
0.6162
0.6306
0.9038
0.6285
0.7052
0.6573
0.7801
Recall
0.1777
0.0888
0.1016
0.1184
0.0921
0.3038
0.1149
0.1239
0.0876
0.2070
OMRMD
F-measure
0.2657
0.1489
0.1718
0.1965
0.1500
0.4492
0. 0.1798
0.1993
0.1437
0.3123
Time
8.74
4.28
8.73
8.73
8.90
8.88
6.91
11.76
7.49
11.56
Precision
0.3580
0.4024
0.4636
0.5077
0.4260
0.9-175
7.7607
0.5560
0.5543
0.8462
Recall
0.1595
0.0923
0.2526
0.1171
0.0693
0.5023
0.0575
0.1208
0.0561
0.2809
OTRPCA
F-measure
0.2095
0.1328
0.3209
0.1862
0.1007
0.6493
0. 0.1056
0.1853
0.0849
0.3991
Time 31.67
14.70
31.65
31.82
31.87
31.89
26.43
44.96
27.99
44.27
Precision
0.8663
0.8682
0.9638
0.7617
0.8200
0.9382
0.7992
0.8597
0.8221
0.8544
Recall
0.3769
0.3243
0.2573
0.2447
0.2446
0.4555
0.2823
0.3454
0.1925
0.3220
OMRTD
F-measure
0.5119
0.4657
0.3861
0.3624
0.3668
0.6103
0.4080
0.4830
0.2901
0.4552
Time
83.01
39.02
82.61
79.1
84.42
84.55
67.95
119.7
74.44
132.6
the EV values of 0.9963 (with 9500 samples) and 0.9995 (with 20000 samples), respectively. The caveat here is that when nı 100, OMRID and OTRPCA take 207 seconds to achieve the EV values of around 0.9945 (with a little bit more than 8000 samples) and 0.86 (with 20000 samples), respectively. We can even expect that the gap between the EV values of these two methods will get even larger as nı increases. Tt is reasonable to conclude that the advantage of OMRTD over OTRPCA in terms of convergence rate significantly outweighs the increase in computational complexity when nı moderately large.
5.2 Real Data Experiments
In this subsection, we compare the performance OMRTD with OTRPCA (Zhang et al. 2016). TRPCA (Lu et al. 2020), OMRMD (Shen et al. 2017), ORPCA (Feng al. 2013) and robust PCA (RPCA) Candès et al.) 2011)) on the CAMO-UOW dataset (Li et al.) 2017) for video background subtraction. The task is separate the moving foreground objects, which are usually sparsely distributed in the video frames, from
13

---

Published in Transactions on Machine Learning Research (06/2024)
static background, which can be characterized by low-rank matrix/tensor. The dataset contains 10 real video sequences and we use all these sequences for both qualitative and quantitative analysis. To evaluate the performance of OMRTD, the Precision, Recall, and F-measure, are used as basic evaluation metrics. The upper bound of the rank of the clean data in OMRMD/ OMRMD/ORPCA /ORPCA is set to be 5 and the upper bound of the lubal rank of the clean lensor in OMRTD/ OMRTD/OTRPCHT /OTRPCA is set be achieves the highest F-measure scores for videos. The visual comparison in Figure Appendix A.3 shows that our method competent to extract the foreground from these videos.
can be seen from Table ] OMRTD
6 Conclusion
In this paper, we have proposed a tensor max-norm for low-rank tensor modeling and developed an online algorithm for the max-norm regularized tensor docompasition (OMRTD) problem. The main idea of OM- RTD is to reformulate the objective function of max-norı regularized tensor decomposition as a const problem using the tensor factorization form of the max-norm, which can be solved by stochastic optimiza- tion. We further extended the proposed method to the missing data scenario. Comprehensive simulations demonstrate the effectiveness of OMRTD and we conjecture that the tensor max-norm might be tighter relaxation of the lensor average rank compared to the lensor nuclear norm.
References
Anima Anandkumar, Prateek Jain, Yang Shi, and N. Niranjan. Tensor vs. matrix methods: Robust tensor docomposition under block sparse perturbations. In International Conference on Artificial Intelligence and Slalislics, pp. 268-276, 276, 2016.
Andreas Argyriou, Rina Foygel, and Nathan Srebro. Sparse prediction with the k-support norm. In Advances in Neural Information Processing Systems, pp. 1457 1465, 2012.
Dimitri P. Bertsekas. Nonlinear programmiing. Athena Scientific, 1999.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1-122, 2011.
Emmanull J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM, 58(3):1 37, 2011.
David L. Donoho. De-noising by soft-thresholding JEEE Transactions on Information Theory, 41(3):613- 627, 1995.
Ethan X. Fang, Han Liu, Kim-Chuan Toh, and Wen Zhou. Max-norm optimization for robust matrix recovery. Mathematical Programming, 167:3-35, 2018.
Jiashi Feng, Huan Xu, and Shuicheng Yan. Online robust PCA via stochastic optimization. In Advonces in Newral Information Processing Systems, pp. 404-412, 2013.
Donald L. Fisk. Quasi-martingales. Transactions of the American Mathematical Society, 120(3):369-384 389. 1965.
Thomas Franz, Antje Schultz, Sergej Sizov, and Steffen Staab. TripleRank: Ranking semantic web data by tensor decomposition. In International Semantic Web Conference, pp. 113-228, 2009.
Quanxue Gao, Pu Zhang, Wei Xia, Deyan Xie, Xinbo Gao, and Dacheng Tao. Enhanced tensor RPCA and its application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(6):2133-2144) 2021.
Kyle Gilman, Davoud Atace Tarzanagh, and Laura Balzano. Grassmannian optimization for online tensor completion and tracking with the t-SVD. IEFE Transactions Signal Processing, 70:2152 2211222167, 2167, 2022.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Donald Goldfarb and Zhiwei Qin. Robust low-rank tensor recovery: Models and algorithms. SIAM Journal on Motriz Analysis and Applications, 35(1):225 253, 2014.
Wei He, Hongyan Zhang, Liangpei Zhang, and Huanfeng Shen. Yotal-variatioon-regnaaa low-rank matrix factorization for hyperspectral image restoration. TEEE Transactions on Geoscience and Remote Sensing, 54(1))178-188, 2016.
Christopher J. Hillar and Lek- Lek-Heng Lim. Most tensor problems are NP-hard. Journal of the ACM, 60(6): 1-39, 2013.
Bo Huang, Cun Mu, Donald Goldfarb, and John Wright. Provable low-rank tensor recovery. Optimization- Online, 4252:2, 2014.
Hiroyuki Kasai. Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations. Neurocompulingg 347:177-190, 2019.
Henk A. L. Kiers. Towards a standardized notation and terminology in multiway analysis. Journal of Chemometrics, 14(3):105 122, 2000.
Misha E. Kilmer and Carla D. Martin. Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):641166) 2011.
Misha E. Kilmer, Karen Braman, Ning Hao, and Randy C. Hoover. Third-order tensors operators matricos: A thcoretical and computational framework with applications in imaging. SIAM Journal on Matrir Analysis and Applications, 34(1):148-17) 2013.
Misha E. Kilmer, Lior Horesh, Haim Avron, and Elizabeth Newman. Tensor-tensor algebra for optimal representation and compression of multiway data. Proceedings of the National Academy of Sciences, 118
(28), 2021.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. STAM Review, (3): 455 500, 2009.
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. A multilinear singular value decomposition. SIAM Journal on Matriz Analysis and Applications, 21(4):1233-127) 2000.
Jason Lee, Benjamin Recht, Ruslan Salakhutdinov, Nathan Srebro, and Joel A. Tropp. Practical large-scale optimization for max-norm regularization. In Advances in Neural Information Processing Systems, pp. 1297-1305, 2010.
Ping Li, Jiashi Feng, Xiaojie Jin, Luming Zhang, Xianghua Xu, and Shuicheng Yan. Online robust low- rank tensor modeling for streaming data analysis. IEEE Transactions on Neural Networks and Learning Systems, 3064):0611 2019.
Shuai Li, Dinci Florencio, Yaqin Zhao, Chris Cook, and Wanqing Li. Foreground detection in camouflaged scenes. In IEEE International Conference on Image Processing, 2017.
Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):208-22) 2013.
Canyi Lu, Jiashi Feng, Zhouchen Lin, and Shuicheng Yan. Exact low tubal rank tensor recovery from Gaussian measurements. In International Joint Conference on Artificial Intelligence, pp. 2504 2510, 2018.
Canyi Lu, Xi Peng, and Yunchao Wei. Low-rank tensor completion with new tensor muclear norm induced by invertible linear transforms. Tn IEEE/CVF Conference on Computer Vision and Pattern. Recognition, pp. 5996 6004, 2019.
Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan. Tensor robust principal component analysis with a new tensor muclear norm. IEEE Transactions on Pottern Analysis and Machine Intelligence, 42(4):925 938, 2020.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 11(2):19 60, 2010.
Morteza Mardani, Gonzalo Maleos, and Georgios B. Giannakis. Subspace learning and imputation for streaming big data matrices and tensors. IEEE Transactions on Signal Processing, 63(10)::663-25)) 2015.
1. V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, (3(5)22295 2317, 2011.
Benjamin Rocht, Maryam Fazel, and Pablo Parrilo. Guarantcod minimum-rank solutions of lincar matrix equations via nuclear norm minimization. SIAM Review, 52(3):471 10011111,1- 2010.
Jasson D. M. Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In International Conference on Machine Learning, pp. 713 713-719, 2005.
Bernardino Romera-Paredes and Massimiliano Pontil.
convex relaxation for lensor completion. In Aduances in Newral Information Processing Systems, pp. 2967-2975, 2013.
Jie Shen, Huan Xu, and Ping Li. Online optimization for max-norm regularization. Machine Learning, 106: 419 457, 2017.
Nicholas D. Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E. Papalexakis, and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):3551-3388 2017.
Guangjing Song, Michael K. Ng, and Xiongjun Zhang. Robust tensor completion using transformed tensor singular value decomposition. Numerical Linear Algebro with Applications, 27(3):e2299, 2020.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In Annual Conference on Learning Theory, pp. 545 560, 2005.
Nathan Srebro, Jason D. M. Rennic, and Tommi Jaakkola. Maximum-margin matrix factorization. In Advances in Newral Information Processing Systems, pp. 1329 1336, 2004.
Ledyard R. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279 311, 1966.
A. W. van der Vaart. Asymptolic statistics. Cambridge University Press, 1998.
Andong Wang, Guoxu Zhou, Zhong Jin, and Qibin Zhao. Tensor recovery via *z-spectral k-support norm. IEFE Journal of Selected Topics in Signal Processing, 1533):522-534) 2021.
Tong Wu. Online tensor low-rank representation for streaming data clustering. IEEE Transactions on Circuits and Systems for Video Technology, 33(2):602-6)) 2023.
Huan Xu, Constantine Caramanis, and Shic Mannor. Principal component analysis with contaminated data:
The high dimensional case. In Annual Conference on Learning Theory, pp. 490-502, 2010.
Jing-Hua Yang, Xi-Le Zhao, Teng- Yu Ji, Tian-Hui Ma, and Ting- Zhu Huang. Low-rank tensor train for tensor robust principal component analysis. Applied Mathemalics and Compulation, 367:124783, 2020.
Rose Yu, Dehma Cheng, and Yan Liu. Accelerated online low-rank tensor learning for multivariate spatio- temporal streams. In International Conference on Machine Learning, pp. 238 238-247, 2015.
Zemin Zhang and Shuchin Aeron. Exact tensor completion using t-SVD. IEEE Transactions Signal Processing, 651))1111- 2017.
Zemin Zhang, Gregory Ely, Shuchin Acron, Ning Hao, and Misha Kilmer. Novel methods for multilincar data completion and de-noising based on tensor-SVD. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 3842 2249, 2014.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Zemin Zhang, Dehong Liu, Shuchin Acron, and Anthony Vetro. An online tensor robust PCA algorithm for sequential 2D data. In TEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 2434 2438, 2016.
Pan Zhou, Canyi Lu, Jiashi Feng, Zhouchen Lin, and Shuicheng Yan. Tensor low-rank representation for data recovery and clustering. 1EEE Transactions on Pattern Analysis and Machine Intelligence, 43(5): 1718-1732, 2021.
A Appendix
A.1 Some Proofs
We first present the proof of Proposition 1
Proof. Let us denote x = |R||2 2, which is positive as long as R. is not a zero tensor. Otherwise the recovered low tubal-rank component X = R is lensor. Now construct two variables C = kL and R R,, and replace L and R in
5 with 1/2 C and RR, respectively. Our problem can be written as
1 min b12 2 (= (kR)² E.R.E
i 1 + A211E111,
Eli
which is equivalent to solving
~ TT C R
A
min E,R.E 2
2
E
R1 A2/EE111
2
Since R = LR, we have RR|1,,00 = _ = 1. Therefore, we can reformulate our MRTD problem as a
constrained program:
A A
min E.R.E
2 E
1
+ A s.t. |R 1 1.
To see why the above problem is equivalent to 6
only need to show that any optimal solution (L', R., E*) to ( must satisfy | Again, suppose that x |R'l2,, < Let L' kL
and R' R It is clear that (C', E*) are still feasible. However, the objective value now becomes
A
Z L' R E11 +
L' >211E*111
2
À1
2 L' R
E +
L
12200 + AellE"111
2
À
1 L R² - +
L
1200 + +
2
which contradicts the assumption that (C*, R², Et) is optimal. Thus we complete the proof.
R²,E*)
Next, we prove Proposition 2
Proof. (Sketch) Let us consider the optimization problem R is uniformly bounded because of the
constraint that ||| 1. Plugging in the trivial solution R4/ E() (0,0), we have ((2,,
0,0) (,,,0,1-,0000
| 11112. Therefore the optimal solution should satisfy
2 _ C. マे - ビ + A
17

---

Published in Transactions on Machine Learning Research (06/2024)
|| 13.1.. Since E, is uniformly bounded (Assumption (A1)), E; is uniformly bounded. The uniform boundedness of {Ac and B follows immediately. Recall that L, is the optinal basis for [14 Thus, the subgradient of the objective function with respect to L, should contain zero, i.e. A,
which implies
, B, Anna H, 0, where H, the subgradient of / || Since all of the eigenvalues of A, are lower bounded by a positive constant (Assumption (A2)), A is invertible. Thus, L, = B, A H+)(; Following the proof of Shen et al. (2017 Proposition 7), L,, and equivalently, Ct, can be uniformly bounded.
We now prove Corollary as follows.
Proof. Since Z., C,, Rे and ē are all uniformly bounded, it is easy to show 7(Z,, L., R, E and E(C,, Z,) are uniformly bounded from above. Thus, 9o (C.) is also bounded. To show that 9r (C) uniformly A
Lipschitz, we first define He (L) gr (C) 2ins [ LR; E, 18 Ei dzll Ei 2 L then the subgradient of De with respect to L is
(LA, B,) + A H F I
V
(LA, B.)lIE + A |
tms
tng
where H. is the subgradient of L Since L, A. and B are all uniformly bounded, the subgradient of It uniformly bounded. Notice that each entry of Z (in other words, each entry on the main diagonal block of L) is a linear combination of the entries in the same mode-3 fiber of L, where the corresponding coefficients are the elements of the Discrete Fourier transform matrix. Thus the subgradient of (c( is also uniformly bounded for all L E L and (C( is Lipschitz.
A.2 Algorithm Details
Algorithm 4 Data Projection (Problem (10))
Input: Observed data sample 2 I x1xn3, R"1xxxa, and parameters Ag and Initialize: غ = 0.
while not converged do Compute the potential solution R Reand using
(k)
3: if Vk,
R Raaanlle < then
4: Set R Reand-
else
for = 1,,,, nig do
if R (k)
7:
cand
1l2 <
then
(b)
(k)
Set R
R Rand
clse
10:
Update by Algorithm
11:
end if
12:
end for end if
13:
R = ifft R ( (1.3)
14:
15:
8 =S 1 L R|.
16: end while
Output: Optimal R. and E.
Let (R', 3 and (Té", E be the two consecutive iterates. If max (
"Ill "Ile)/(nnnn) is
less than 6 the number of iterations exceeds 100, will terminate A Algorithm
18

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 5 Bisection Method for Solving Problem 12
Input: L C z E C²,, e e C
R (k)
Initialize: Set 7/2 0 and 7/2 to be large enough such that
(л2)llr S 1.
1: repeat
Compute the middle point: n/ [ + 72).
2:
(k)
if ||
[FF then
Update 7/2 (8) else
Update = (8).
7:
end if
until
R
||
3
Output: Optimal and 18)))
Algorithm The Update of C
Input: L m in the previous iteration, accumulation tensors A and B, and parameter A
1: Z= =fft((C, [],3), A = fft(A, [], and B = [f,
Compute the subgradient of ] || H 0(
3: for h: = 1,2....
2........ ..... nl do
4: A = A (k) B (k) H H
5: for j = 1,2...., do
k(:j,k) k(;j,k) Ass
L (k)
b,)) >1ı)))
nJ
end for end for
Output: L - C=ifft(C.[],3)
19

---

Published in Transactions on Machine Learning Research (06/2024)
For Algorithm G we find that one-pass update on the dictionary L is sufficient to guarantee desirable accuracy, 88 we shown in the experiments. This is also observed in Mairal et al. (2010).
A.3
Supplementary Experimental Results
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.6
OMERTO TU-TTU
0.6
QURRI TRPCA
0.6
QUATT TIPAA
0.5
0.5
0.5
0.05
0.2
0.35
0.5
0.05
0.2
0.35
0.5
0.05
0.2
0.35
0.5
(a) tubal rank
(b) tubal rank
8
(c) tubal rank
12
0.9
0.9
0.8
0.8
0.7
0.7
0.6
OMATO
0.6
OMPTO
-OT-POA
0.5
0.5
0.05
0.2
0.35
0.5
0.05
0.2
0.35
0.5
(d) tubal rank = 16
(e) tubal rank 20
Figure 5: EV value as a function of corruption fraction for different intrinsic dimensions of complete data.
0.9
0.9
0.9
0.8
0.8
0.7
0.7
0.6
.00PT1 T---TTN-TAPCA
.PIRID TINTTIPAA
(OMRI -
0.05
0.35
0.05
0.5
0.2
P
P
P
(a) tubal rank =
(b) tubal rank = 8
(c) tubal rank = 12
0.9
0.8
0.7
0.7
0.6
0.6
4- TMPCA
0.5
0.5
0.05
0.2
0.35
0.5
0.05
0.2
0.35
0.5
(d) tubal rank 16
(e) tubal rank
20
Figure 6: EV value function of corruption fraction for different intrinsic dimensions of missing data when 7 = 30%.
20

---

Published in Transactions on Machine Learning Research (06/2024)
Input
Ground Truth
RPCA
TRPCA
ORPCA
OMRMD
OTRPCA
OMRTD
Figure 7: Examples of background subtraction using the CAMO-UOW dataset Li al. 2017 From top
to bottom 10 sequences within the dataset.
21


Reviews:
[{"review_id": "P9SloT18W9", "reviewer": "Reviewer_cKGa", "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": "While the algorithm is no doubt interesting and appears to have good performance in practice, there are several weaknesses of this paper that need to be addressed. I detail these more specifically in Requested Changes, but at a high-level:\n\n1. The authors state \"we rigorously deduce a new tensor max-norm for tensor decomposition.\" While the authors define the new tensor-max norm, they do not rigorously prove it is indeed a norm over the space of tensors under the t-product (I suspect this wouldn't be too hard to do...perhaps it is not necessary for a TMLR paper, but to me, the claim of \"rigorously deduce\" would necessitate this). The authors seem to conjecture throughout the paper that the max-norm is a tighter approximation to tubal-rank, but also claim without proof on P4 \"hence it is tighter [sic] to the tubal-rank.\" I suggest the authors either rigorously provide the theory to their claims or modify their claims appropriately. They also add, \"since the tensor max-norm is a more complicated mathematical entity, the development of online methods for the max-norm regularization requires more attention.\" What do the authors precisely mean by \"is a more complicated mathematical entity?\" Can you be more specific about the technical challenge this paper addresses? \n \n2. This manuscript needs some reorganization and additional exposition to give more context for important details, particularly surrounding the mechanics of the t-product/t-SVD. Much of the writing in general should be improved to reduce wordiness, awkward phrasing, and passive voice. I suggest the authors include more thoughtful transitions between central ideas.\n\n3. There is often inconsistent, incorrect, or undefined mathematical notation that needs to be resolved. \n\n4. I suggest the theory be made more precise and formal. While I understand theory is optional for a TMLR paper, I think the presentation of Proposition 1 and the convergence guarantees should be cleaned up. The authors claim \"we derive several theoretical results\" but do not provide formal theorem statements or proofs.\n\n5. I have some concerns about the optimization problems in Equations (7) and (17).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 contributes a new online algorithm for low-rank tensor factorization under the tensor-tensor product using max-norm regularization of the factors. The authors also propose an extension of their algorithm to data with missing entries. The authors claim the algorithm converges almost surely to a stationary point as t tends to infinity. The method appears to be superior in subspace recovery to the competing OTRPCA method they compare against, lending credence to their claim the tensor max-norm is a tighter approximation to tubal rank, albeit at higher cost in computation time.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I list my requested changes below by their order as I read them in the paper. For those that are critical to securing my recommendation for acceptance, they are marked with [**CRITICAL**]. \n\n1. P3 and formatting throughout: Make sure you use \\mathrm{rank} and \\mathrm{F} for the Frobenius norm in your LaTeX editor.\n\nP3: Equation (1): I suggest you clarify that \\cdot here is ordinary matrix-matrix multiplication. I also suggest you add the dimensions of $\\pmb{\\mathcal{C}}$, and you that specify how the dimensions of $\\pmb{\\mathcal{A}}$ and $\\pmb{\\mathcal{B}}$ must match for the t-product to be valid.\n\n2. P3: Definition 5: The first equality needs to be $\\triangleq$.\n\n3. [**CRITICAL**] P4: Section 3: This section overall really could benefit from additional exposition and reorganization to give more intuition for the t-product and t-SVD, particularly for novice readers not familiar with it since t-SVD is still relatively new in the tensor literature. I strongly suggest you discuss how the Fourier domain counterparts of the t-product variables relate to the computation of the t-product in practice. This is a central idea to your work since the tensor max-norm uses this concept too.\n\n4. P4: Section 4: The introductory statement seems to be incomplete? It states \"This section first...\" but there is no second, third, etc. To my overall point, I think there could be more thoughtful transitions to make the paper flow more nicely. The first sentence of 4.1 reads awkwardly; I would rephrase, and be more precise what you mean by \"the basic problem.\"\n\n5. P4: Section 4.1: I would say \"...sparse corruptions, plus Gaussian noise\" since your noise model is actually Gaussian from the Frobenius norm in Equation (2), which is to be distinguished from the corruptions that are modeled as sparse.\n\n6. P4: Section 4.1: below Equation (2): I suggest explaining the behavior of $\\lambda_1$ and $\\lambda_2$.\n\n7. P4: Equation (3): I would make this a formal definition.\n\n8. [**CRITICAL**] P4: Sentence starting \"Since the t-product in the spatial domain corresponds...\" : To my earlier point, this is really out of context to a reader not already familiar with the t-product since there is no previous discussion about why the Fourier domain variables are important, or the equivalency between the t-product and the matrix-matrix products of the frontal slices in the Fourier domain. I think this needs more supporting exposition, and mention of the product equivalency should be formalized much earlier, such as in Section 3.\n\n9. [**CRITICAL**] P4: \"...and hence is tighter to the tubal rank.\" is what this sentence should read as. How? I don't understand the intuition from this sentence. Is there a proof of this claim?\n\n10. P4: \"...we have the following equivalent *optimization problem:* \"\n\n11. P4: Last sentence before Prop 1: This sentence is awkward. I would reword and use active voice.\n\n12. [**CRITICAL**] P4: Proposition 1: In what sense are these optimization problems equivalent? Equal objective function values? The same optimal solutions? I think from the proof you mean the former? Can you make this more precise? Just from Prop 1 and the sentence preceding it, it is not immediately clear yet how this allows for sequential optimization, so perhaps think about how this transition can be revised.\n\n13. P5: Algorithm 1: Clarify that $\\bar{\\mathbf{L}}$ and $\\pmb{\\mathcal{L}}_t$ are equivalent representations of the basis.\n\n14. P5: First equation: I think there are missing i subscripts on the Z, R, and E variables. This should be congruent with the notation in Equation (7).\n\n14a) [**CRITICAL**] P5: Equation (7): I'm not sure this is the correct optimization problem you are actually solving. I believe you are actually solving the problem (please excuse my own notation here, I will neglect the arrows above the oriented slices...) $$\\min_{\\pmb{\\mathcal{L}}} \\sum_{i=1}^N \\min_{\\pmb{\\mathcal{R}}_i, \\pmb{\\mathcal{E}}_i }\\tilde{\\ell}(\\pmb{\\mathcal{Z}}_i, \\pmb{\\mathcal{L}}, \\pmb{\\mathcal{R}}_i, \\pmb{\\mathcal{E}}_i) + ....$$ \n\n14b) [Suggestions] Additionally, can you simplify the notation for the frontal faces of the R_i's in the Fourier domain? There is a lot of decoration here that makes it hard to read. Minor suggestion: I would also suggest perhaps using the $\\ell_2$ norm on these constraints, since the variables are vectors not matrices. Use \\quad to space out the $\\forall i$ and $\\forall k$.\n\n15. P5: Below Equation (8): I think you are again missing i subscripts in this math. I think the set $\\mathcal{P}$ needs to have the dimensions of the variable to specify it is the set of $r \\times 1 \\times n_3$ slices, and not the full $\\pmb{\\mathcal{R}}$ tensor.\n\n16. P5: \"We assume that each sample is drawn independently and identically distributed from some unknown distribution.\" Is this true? You are assuming additive Gaussian noise through the Frobenius norm in your objective function.\n\n17. P5: Everything from \"This is indeed equivalent to optimizing.... Equation (9)\": The organization of this section is a bit odd. Usually in stochastic/online optimization, the exposition begins with introducing the minimization of the expected loss first, and then, as a surrogate, relaxes this to minimization of the empirical loss. This fits better within the context of the online optimization problem to be presented in Section 4.2. Here, this discussion is a bit out of context and does not quite flow well.\n\n18. P6. The tensor inverse under the t-product is undefined as currently in your paper. I recommend including this from the Kilmer & Martin paper and refer to it in the appendix perhaps.\n\n19. P6, Equation (12): One $\\eta$ $\\forall k$? Or $\\eta^{(k)}, \\quad k=1,2,3,...$?\n\n20 [**CRITICAL**] P7: Algorithm 3: There is quite a bit of inconsistent and undefined notation in this algorithm block. I will leave it to the authors to find all of the errors, but take care to define all column vectors, and make sure the all \\Lbar's are using consistent tensor/matrix notation. You currently index block diagonal matrices with three modes of indices. Also, please specify the convergence criterion.\n\nDoes the problem in $\\pmb{\\mathcal{L}}$ need to be solved exactly every time? If so, what is the convergence criterion? Does your algorithm still work if you solve it inexactly? Can you take just a single subgradient step in $\\pmb{\\mathcal{L}}$ with a new sample? I understand your convergence results may not hold, but it could significantly speed up your algorithm, since I suspect solving (14) is one of the most expensive steps. \n\n21. P7: First paragraph: $\\epsilon$ here is undefined. I think some of these arrow-R's should be indexed by t, as done in Equations (10) and (13).\n\n22. \"by optimizing the surrogate function.\" I know what you mean here, but this is written without any context or explanation why (13) is a surrogate function, i.e., a majorizer. This is a very similar problem to online dictionary learning and matrix factorization, so I *strongly suggest* the authors cite some of the works by Julien Mairal and others. \n\n23. P7: \"It is easy to verify that the minimizer of (14)...\" do you mean Equation (13)?\n\n24. [**CRITICAL**] P7: Be very careful on this page to define all notational equivalences between the tensor variables and their block-diagonal matrix counterparts in the Fourier domain; some of the equivalent representations for the R variables appear overloaded. Be careful to explain the connection/equivalency between the two optimization problems in Equation (14).\n\n25. P7: You need to include more thoughtful transitions, such as here where you jump to declaring how to compute the subgradient with respect to L without first explaining the optimization approach you will use to solve (14).\n\n25. P8: This should be $\\mathbf{U} \\triangleq ...$. This is perhaps my personal preference, but using $\\mathbf{U}$ to denote a subgradient seems a bit odd...especially since U is used earlier to denote the left singular tensor in the t-SVD. Also, shouldn't $\\mathbf{\\Theta}$, $\\mathbf{Q}$, and the subgradient be indexed by $t$? In the block diagonal representation of $\\mathbf{U}$, I suggest being clear that the off-diagonals are zero.\n\n26. P8: Again, make sure all variables denoting slices in time are indexed by $t$.\n\n27. [**CRITICAL**] P8: Convergence: I suggest writing the Convergence subsection more formally. E.g., Assumption 1), Assumption 2), ... Proposition 3), Theorem 4), etc. You say \"Following the proof techniques of Shen et al. (2017)...we derive theoretical results...\" but then don't provide the formal statements or proofs. It is very hard to verify these claims without explicit proofs.\n\n28. P9: Algorithm 4: specify convergence criterion. Also, why is $\\mu$ fixed in the ADMM iterations? Usually this penalty parameter is increased in a geometric progression, such as $\\mu^{(t+1)} = \\min${$\\rho \\mu^{(t)}, C$}, where here I use $t$ to denote the ADMM iteration, $\\rho > 1$, and $C >> \\rho$. This will likely speed up the convergence of your algorithm.\n\n29. [**CRITICAL**] P9: Usually an online algorithm includes a step size/learning rate that varies the tradeoff between newer and older samples, but I don't see this in your work. Can you please comment on why this is, or modify your existing work to account for this? I don't think it would be too hard of an extension to make; the only real changes will probably be in the way the A and B tensors are computed in Equation (14).\n\n30. P9: Right after (16): I think this set should read as $\\Omega_t = ${$(i,k) | (i,t,k) \\in \\Omega$}, since $t$ is fixed.\n\n31. [**CRITICAL**] P9: Equations (17) - (18): Why is the constraint over the entries $\\Omega_t$ in (17) dropped in the augmented Lagrangian in (18)? Also, I don't think variable splitting is necessary here. After variable splitting, you still have a least squares problem in D where before you had a similar least squares problem in M with a closed form solution. \n\n32. P10: I think the works OTRPCA (Zhang et al., 2016) and TRPCA (Lu et al., 2020) need to be discussed or at least mentioned in Related Works.\n\n33. P11: No real data experiments? I'm not certain what TMLR's policy is on having real data experiments, but it would certainly strengthen the paper to include real data. \n\n34. P12: \"a tensor max-norm based low-rank tensor model\" is a little wordy and hard to read.\n\n35. P12: \"suggest that the tensor max-norm might be a tighter relaxation\" Perhaps use active voice and say, \"we conjecture...\"", "broader_impact_concerns": "I have no broader impact concerns about this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ay8VkdGqJy", "reviewer": "Reviewer_9zJ8", "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\n- A new norm: The proposal of tensor max-norm within the t-SVD framework is new to the best of my knowledge. \n- Promising numerical experimental results: The experimental results in comparison with (O)TRPCA shows the effectiveness of the proposed algorithms. \n\nWeaknesses:\n\n- Influence: The proposed max-norm-based tensor recovery model seems of limited possible applications in machine learning society.\n- Insufficient analysis of the properties of max-norm: The properties of the proposed max-norm are not sufficiently analyzed to support the statement \"... and suggest that the tensor max-norm might be a tighter relaxation of the tensor average rank compared to the tensor nuclear norm.\"\n- Reproductivity: The proposed algorithms involve many details, and it may be not easy to implement for readers. The lack of code raises a concern about reproductivity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 proposes the tensor max-norm for online low-rank estimation for tensor data. The formulation of the new max-norm is based on the algebraic framework named tensor Singular Value Decomposition (t-SVD) which finds many applications in visual data modeling in recent years. An algorithm is designed for the proposed online model with analyzed complexity and convergence. Numerical experiments validate the effectiveness of the proposed algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It is suggested to provide a more detailed and clear analysis of the properties of the proposed max-norm to show its advantages, especially in \n- Why do we need to design a new max-norm within the t-SVD framework instead of the Tucker/CP/TT/TN sense? \n- What are the advantages of the new max-norm in comparison with other tensor low-rank regularizes like the $*_L$-Spectral $k$-Support norm rather than only the TNN?\n\n2. The proposed online tensor RPCA model seems of few possible applications in today's deep learning age. It is suggested to discuss:\n- Are there any possible applications of the proposed online tensor RPCA models to enhance deep learning models?\n- What are the possible benefits that t-SVD-based modeling can bring to deep learning? To the best of my knowledge, a typical model is the \"stable tensor neural networks\" for rapid deep learning which has recently been used for improving robust generalization (e.g., transformed low-rank parameterization can help robust generalization).\n\n3. It is interesting to see some discussions about the theoretical performance of the proposed tensor recovery model, i.e, the estimation error. Anyway, it is not mandatory.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oLHwsReA06", "reviewer": "Reviewer_sMav", "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- The numerical experiments showed the promise of OMRTD for tensor completion, particularly in the cases when there are a greater proportion of missing data.  The algorithm was also shown to be faster than a competing online approach.\n- The algorithms were described thoroughly.\n- The computationally complexity, particularly in terms of memory allocation, was clearly \n\nWeaknesses:\n- Results were only generated for synthetic data and only for tensor completion problems.\n- The motivation for the algorithm, the max-norm definition, and more was unclear.\n- The writing was hard to follow at times.  For instance, the Convergence paragraph in Section 4.3 explore all of the assumptions and analysis rapidly, making it difficult to verify the accuracy of the statements.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 authors propose an online max-norm regularized tensor decomposition (OMRTD).  The proposed method learns a low-rank tensor factorization under the t-product with max-norm regularization. The authors formulate an alternating optimization problem slice-wise and add practical constraints to their low-rank factorization to make online updating a feasible strategy.  The authors describe convergence and complexity behavior of their algorithm and show numerical experiments on synthetic data for a tensor completion problem with comparisons to related algorithms in the literature.\n\nContributions:\n- A new OMRTD algorithm that can handle larger-scale tensor completion problems by updating sample-by-sample.\n- Using max-norm regularization compared to the traditional nuclear norm approach for tensor completion.\n- Extensive numerical experiments on synthetic data to support the theory of the presented algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "All of the requested changes are critical to securing my recommendation for acceptance.\n\n- Numerical Experiments on Non-synthetic Data: \n    - All of the presented experiments were performed on synthetic datasets.  The paper needs results on real-world data, for instance video and hyper spectral data.\n    - Additionally, it would be compelling to see how the algorithm performs under different sparsity patterns. The authors only look at random sparsity, and other options like tubal sparsity or structured sparsity (e.g., like that seen in image inpainting) would make OMRTD a more convincing approach. \n\n- Motivation Clarification and Writing Improvement: There were many aspects of the paper that were not motivated clearly, and hence difficult to follow.  Below are a few examples of questions that arose.  There are more, so the reviewer requests a major revision.\n\n    - Why is max-norm regularization helpful? Why does Definition 2 of the tensor max norm require a factorization into $\\overline{\\mathbf{L}}$ and $\\overline{\\mathbf{R}}$?\n    - What is a sparse noise tensor?  Is it tubally sparse or is it a different notion of sparse noise?\n    - What does \"(5) can only optimized in a batched manner\" mean on Page 4?\n    - The convergence analysis in Section 4.3 needs to be fleshed out.  Why are the assumptions made and are they reasonable?  Why do you need to add the additional regularization on $\\vec{\\mathcal{R}}$ with an $\\epsilon$ regularization parameter? etc.\n    - The statement in the introduction \"Extensive experimental results on the tensor subspace recovery task illustrate that the proposed tensor max-norm **always performs better** than the tensor nuclear norm in terms of convergence rate and robustness.\" does not seem accurate based on the presented results.  Be sure that your claims are stated appropriately.\n    - The statement \"Intuitively, the tensor nuclear norm constrains the row norms of $\\overline{\\mathbf{L}}$ and $\\overline{\\mathbf{R}}$ on average, while the tensor max-norm constrains the largest $\\ell_2$ row norm, hence is **tighter**.\"  What does \"tighter\" mean?\n\n- Reproducibility: There is no code provided for reproducibility.  However, this reviewer acknowledges that code may not be able to be provided at this stage of the double blind review process.  This would need to be included in the final version to recommend acceptance.", "broader_impact_concerns": "There are no concerns about the ethical implications of this work that would require adding a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were unanimous in their opinion that this was a reasonable and publishable paper. The reviewers requested a lot of changes, and the author made these changes (some of them big, like adding real data to the experiments), and reviewers were happy with this.

I'd like the authors to make a few minor changes (these are either my requests or from the recommendations of the reviewers):
- Section 4, P5: they now say from the Srebro & Shraibman (2005) paper that the matrix max-norm regularizer "could outperform" matrix nuclear norm when the entries are uniformly bounded, but it's not clear what "outperform" here means. Does this mean a tighter approximation to the matrix rank? What other conditions are necessary for it to "outperform" nuclear norm, since "could" does not imply "always"? I think more precision is still needed here.
- Now that you can de-anonymize the manuscript, please include a link to code
- The proof of Theorem 1 is very high-level. For each of the 4 high-level steps, can you be more specific about why this is true, since it can't exactly follow Shen et al for all details. Perhaps justify each step in the appendix
Other little minor things to clean up:
- delete "we understand that" on P7.
- Last sentence of P7: run-on sentence; should read: "bdiag(E). The above..."
- Use a semicolon, not a comma, here on P8: "...sequentially; see details..."
Decision: Accept (poster)