Non-Convex Tensor Recovery from Tube-Wise Sensing
Authors: Tongle Wu
Ying Sun
Venue: NeurIPS 2025 poster ()
Keywords: Tensor compressive sensing
non-convex
sample complexity
Primary area: optimization
TL;DR: We introduce the a new local tensor compressive sensing model with computational and statistical guarantees.

Abstract: In this paper, we propose a novel tube-wise local tensor compressed sensing (CS) model, where sensing operators are independently applied to each tube of a third-order tensor. To recover the low-rank ground truth tensor, we minimize a non-convex objective via Burer–Monteiro factorization and solve it using gradient descent with spectral initialization. We prove that this approach achieves exact recovery with a linear convergence rate. Notably, our method attains provably lower sample complexity than existing TCS methods. Our proof leverages the leave-one-out technique to show that gradient descent generates iterates implicitly biased towards solutions with bounded incoherence, which ensures contraction of optimization error in consecutive iterates. Empirical results validate the effectiveness of GD in solving the proposed local TCS model.

Non-Convex Tensor Recovery from Tube-Wise Sensing
Tongle Wu The Pennsylvania State University tfw5381 @ps.1.ppuueeee edu
Ying Sun" The Pennsylvania State University ybs5190@psu.edd edu
Abstract
In this paper, propose novel tube-wise local tensor compressed sensing (CS) model under the tensor product framework, where sensing operators are indepen- dently applied to each tube of third-order tensor. To recover the low-rank ground truth tensor, we minimize a non-convex objective via Burer-Monteiro factorization and solve it using gradient descent (GD) with spectral initialization. We prove that this approach achieves exact recovery with a linear convergence rate. Notably, our method attains provably lower sample complexity than existing TCS methods if the low tubal rank ground truth tensor satisfies the defined incoherence condition. Our proof leverages the leave-one-out technique to show that gradient descent generates iterates implicitly biased towards solutions with bounded incoherence, which ensures contraction of optimization error in consecutive iterates. Empirical results validate the effectiveness of GD in solving the proposed local TCS model.
Introduction
Tensor compressed sensing (TCS) that recovers low-rank tensor from limited measurements is fundamental problem in signal processing and machine learning. Specifically, the classical TCS problem aims recover a ground truth X B x tensor from a few linear measurements generated as
[y
Mml A(x") X(), (Am, X²)
with A P xppixngxn + RD being linear sensing map. Without any structure assumption on X the problem ill-posed and it impossible to recover from measurements less than its dimension. In this paper, consider X" exhibiting structure that be well-approximated by low-rank model. However, unlike a matrix that has a unique notion of rank, a tensor has multiple definitions of rank 19 induced by different tensor decompositions such Canonical Polyadic (CP) [16), Tucker
(54) tensor singular value decomposition (1-SVD) [17), and others 33 65) 70). Algorithms and their
theoretical guarantees recover X under different notions of low-rankness have been studied in
series of existing works 3
18 26
28
30
36
43 44).
Despite the long-standing literature, works mentioned above share common limitation: the TCS model [ is global CS model where the sensing operator AA is applied to the entire tensor X In certain applications, however, fulfilling such requirement is impossible when dealing with massive tensor datasets that exceed available memory, one common strategy is split the data into smaller sub-tensors and allocate them across distributed network of storage nodes 499 (55) In this case, is more practical to take measurements the sub-tensors locally at each node out of implementation efficiency and privacy considerations. Another example is real-time applications such as video streaming, where the data is modeled as tensor whose dimension is increasing with time. For these applications, algorithms that can process incoming measurements
inefficient. For example,
*Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

incrementally and generate the tensor on the fly are favored over those that repeatedly measure and recover the full tensor whenever new data arrives [37 64
To address the above limitations in the global TCS model, recent work (64) firstly proposed a local TCS model where measurements are taken with respect to each lateral slice matrix of X Methods proposed therein provably recover the ground truth tensor X' of low tubal rank with a lower sample complexity than the global TCS model. Inspired by this result, this work takes a further step by proposing a more flexible local TCS model that senses each tube of X". Our proposed tube-wise TCS model only requires access to individual tubes (mode-3 fiber vectors) of the third-order tensor, whereas fiice-wise/ [64] and global sensing methods [20] 26 28 60] must measure the entire slice (full matrix) and the whole tensor, respectively. We refer to our framework as the tube-wise TCS model and define it precisely below:
Definition 1 (Tube-Wiss TCS). Given third-order tensor X" E R geu1XnxX1n tube-wise TCS measures X by the sensing map IR. X [R Xns
- Te xw2xm that consists on x n2 sensing matrices Zi E Rmxns i 1, ,..., To1, j = 1j.1.... ,2 and generates the measurement
y x(x), where Vi.j..) Z ij X' (5 (1. v(i.5) E [m1] x [n2]]-
(2)
Here, fi,, 72, and ni are respectively the height, width, and depth of X"; and n1 and m2 are collectively referred to as the spatial dimension. Each X (i;),,,; denotes (i. tube vector of X which is measured by Zi with an output vector (i.. E R", where m denotes the tube-wise sample size. We can observe that given samples and measurements obtained via the tube-wise TCS model, we can turn it into an equivalent slice-wise or global TCS model, but not the other way around. This reflects the flexibility of the proposed wuse TCS model.
This work considers recovering X with low tubal rank (cf. Definition from y under the tube-wise TCS model. The low tubal rank assumption is well-motivated in applications where multi-dimensional data exhibit strong correlations along the third mode 22 68 such as time or spectrum. Under the t-SVD framework, this assumption enables compact representation of the tensor and has shown empirical success in video, hyperspectral, and multichannel signal recovery tasks 22 41 57
58 62 The TCS model under the VDD framework has also been widely studied in t-SVD
existing works 15
66 67]. Although we consider the Fourier transform- framework, our results in this paper can be extended to general t-SV framework whose transform matrix satisfies L L L- LL
25 26
28
63
nzI, which is standard in the transformed t-SVD framework that includes the DFT matrix as special case.
27 29
Given the proposed tube-wise TCS model, central question is how to design method that can exactly recover the ground truth tensor X" that is both sample and computationally efficient. This paper addresses this question and our main contributions are summarized as follows:
Computational complexity. We formulate the tensor recovery problem by minimizing a quadratic loss and encode the low rank structure utilizing tensor Burer-Montedt (BM) factorization [5]. By reparameterizing the tensor to be learned as the product of two smaller factors based on low tubal rank assumption, the BM factorization enables more computationally and memory- efffciint numerical solutions than existing LSVD-based TCS methods [20 25 28 60, 67]. Specifically, we prove that despite being nonconvex, with a sufficient amount of measurements under the defined tensor incoherence condition (cf. Assumption 2 applying the GD with proper spectral initialization
finds the ground truth X a linear rate.
Tube-wise sample complexity. We provide tube-wise sample complexity to ensure the linear rate of GD and exactly recover the ground truth, given by (12). The expression decreases linearly with the spatial dimension n, implying that for fixed tubal rank and tube size, increasing spatial dimension can reduce the sample complexity significantly. Such a property is unique to our local TCS model and has not appeared in any previous results, revealing that the local TCS model is more sample-efficient than existing methods, as summarized in Table []] Simulation result shown in Fig. corroborstss our findings. Furthermore, our sample complexity is essentially tight since the total sample complexity of all tubes nearly matches the information- theoretical information-theorttiaal lower bound.
Technical analysis. To prove the linear rate of GD under the provided tube-wise sample complexity. our analysis hinges on two key ingredients. One is showing the existence of a benign landscape near the optimum of non-convex loss (6). and the other is that GD iterates stay in this region. To this end, we leverage the leave-one-out (1.00) technique and judiciously construct two auxiliary sequences to show that GD with spectral initialization is implicitly regularized with all iterates having bounded

---

Table 1: Comparison of existing works under different TCS models.
Normalized sample complexity
Method
TCS Model
Convexity
Convergence Rate
TNN 28
Global
Convex
X
Orr(2n- -r)ms)
IR-TTN 60
Global
Non-convex
Sub-linear
x
Schatten-p TNN 20
Global
Non-convex
X
x
FGD 26
Global
Non-convex
Linear
(())))))
Alt-PGD-Min
64
Slice-wise
Non-convex
Linear
Ö(r2na)
ò (max [r"ng
Ours
Tube-wise
Non-convex
Linear
Here assume for simplicity and without loss the generality that = = r denotes the low tubal rank of the ground truth tensor. Normalized sample complexity is defined as the total number of entries in the sensing map divided by the tensor size nu 12 na-
incoherence. Based on this implicit regularization phenomenon, new concentration results are established showing that the empirical Hessian of non-convex loss is close to its population counterpart under reduced sample complexity than state-of-the-art results.
Related works. Based on our proposed model and technique, we organize relevant works as follows.
T-SVD based global TCS. Recovering low-tubal-rank tensors under the 1-SVD framework has been considered in (28), wherein a convex tensor nuclear norm (TNN) minimization formulation is proposed with order-optimal sample complexity guarantees. The results were extended to the robust recovery settings in [67]. Under the TNN minimization framework, nonconvex surtogates for tubal rank have been explored in [20] and (58] to improve performance, yet no sample complexity has been provided. In addition to wow-rankness, the local smoothness structure has been incorporated in (25) for visual data improve sample complexity. Algorithmically. all these methods require performing multiple SVDs per iteration, which is computationally intense. More recently. nonconvex formulation based on the BM factorization for symmetric tensors was proposed in (26). wherein the factorized gradient descent (FGD) algorithm is developed to solve the problem with reduced computational costs and storage requirements. All these works focus on the global TCS model rather than the local sensing setting considered in this paper.
Local CS model. Compared to the global CS model, methods for local CS have remained relatively underexplored. Recent works 22 matrix recovery. yet much less work has been devoted to local CS for tensors. A lateral column- wise sketching method under the Tucker decomposition was proposed in [4), and gradient- basded algorithms were introduced, but without thcoretical analysis. Recent work [64] has studied slice- wise local TCS under the t-SVD framework, wherein both sample complexity and algorithmic convergence are provided. In contrast, this work considers a more fine- ane-grained tube-wise TCS model where the sensing map is applied to each tube independently. Our model achieves improved sample complexity compared to [64], as shown in [
38 48 49 (55 have studied local CS for low-rank
Implicit regularization in tensor learning. Under the BM factorization, one line of research has studied overparameterized tensor models and has shown that some optimization algorithms implic- itly promote low-rank structures CP [TO 12 45). Tucker 31 46). and t-SVD decompositions [15]. Another line of work has studied the exact parameterization setting and has proved that GD or its variants generate balanced factors [51] 52 or enforce incoherence conditions 2 6 7 59].
There are also works that have investigated other types of implicit regularization in tensor learning, such as
Our work reveals the implicit regularization effect of gradient descent in the proposed tube-wise local TCS model, which allows the tube-wise sample complexity required for exact recovery to be reduced linearly as the spatial dimension increases, as shown in (12). ) This leads to significant improvement in sample efficiency.
34
2 Preliminaries
Notations.
Scalars, vectors, matrices, and tensors are denoted by x, x, X, and X, respectively. For third-order tensor X E T Xmgxng denote its (i.j, k) entry X Kijk. The (-h tube, denoted as Xi, X .. is considered as tensor in 1R 1xl1x vector in R=s, depending
3

---

on the context. The i-th horizontal, lateral, and frontal slice of X are denoted as (2, or i; E I X (;,2, R xlxms, and X (:. ;, R xn2x1 respectively. We also refer to the frontal slice () as X E R (x Eijk VinkVijk iyk is the tensor inner product. X denotes the result of performing DFT on all the tubes of X, i.e., X fft(X, I:3); and the inverse DFT is X (f 11, max (X) mamin (X)) is the largest (smallest) nonzero singular value of X.
Basics of t-SVD algebra. T X are defined as
The three basic operations, unfold, fold and block circulant, for X
X
X (mn)
X (2)
Unfold (x) = x ; ;x(
X
x(1
X (3)
beiro(
(3)
Fold (Unfold (2)) = X;
:
X (
X (ms-1)
X (1)
With the above operations, we introduce the following tensor algebraic basics 17 Definition 2. The tensor product of
28
X' E R RR xaaxs and y E IRaaxaaxa is defined as:
X x F.ooo(iiircc (2))nfold()))
XRaxaa
(4)
Definition 3.
The conjugate transpose of a tensor X E RR xn2xna is defined as the tensor x E Reaxmixn, obtained by taking the conjugate transpose each frontal slice of X, then reversing the order of transposed frontal slices through n3.
Definition 4. (f = I, and [(., 1) O, for SiS neg, then I Buxaxss is defined as the identity tensor.
Definition 5. Q nuxxxaa is orthogonal if and only if satisfies Q - 2= 2 II.
Definition 6. A tensor is f-diagonal if each of its frontal slices is diagonal.
Definition 7. X E Rnxxnxs has an inverse y if II and y * X use X to denote its inverse.
I. If X is invertible,
Definition 8. The tubal and average ranks are respectively defined as ranke(X) = X
and (x) (1/nz) E rank [X (x))).
[mxi rank
Theorem 1 (t-SVD (17). X
can be decomposed as X u S V with U In X X Xng, V E R being orthogonal and S E l.n XwaXna f-diagonal.
Definition 9. The spectral norm of X E [Rnixng [ defined as | == max (bcire (X)).
Given the sensing map Z in (2) its adjoint map is defined follows:
Definition 10. The adjoint map of Z R xngxns + R Km. denoted as 2 RR Xn2Xm R XRxxXx is defined such that for vy Reixnaxm it outputs X ()) Ruixnanns with
X(i.j:) (i.)i, (i.j) E [n1] x [mz].
(5)
3 Local TCS via Burer-Monteiro factorization
We employ the Burer-Monteiro factorization S to parameterize the low rank tensor to be leamned as X= A B, where A R Xrxns E X Recovering X' under the tube-wise local TCS
model (2) can then be formulated minimizing the following non-convex loss function:
12
C C(A
Σ
12 s
A * A
B
(6)
where the first term fits the model to the measurements and yıj E RThh is the measurement vector for (V, jith tube. Since the BM factorization not unique, factors A and B cannot be identified. To address this ambiguity, we generalize a technique widely used in asymmetric matrix recovery problems [8 53 7 to tensors and introduce (6) the second term balances the size of A and B. If there is such term, the loss has an identifiability issue since for any invertible R E xxxxxs

---

factors (AA, B) and , has the same loss value. Such ambiguity may result in the norms of the two factors being highly unbalanced, leading even divergence of the algorithm.
To minimize f. we substitute the expression of measurement y generated in Eq. loss function and then apply the GD method with step size 1/ taking the form: (2) into the above
A 4+1 A' 1 A' (B') -x*) B²
m
A'
((A))
A'
(B') T B²)
(7)
B++ =
- 17 2 A' (B') T -xx)) A'
mL B'
(BB)
* BB' (A4) T * A²)
(8)
where the adjoint map z is introduced in Definition 10 The estimated recovery result at each iteration is therefore given by X² :- A' (B*)
To overcome the challenge getting stuck at local solutions due to the nonconvexity of (6) and
enabling exact recovery of X", we further provide spectral initialization scheme that starts GD at point sufficiently close to the ground truth. The complete algorithm is given by Algorithm | and
Algorithm Gradient descent with spectral initialization for minimizing (6)
Input: Operator and measurements y E R XmggX rank r, step size 17, total iteration T maxx- b Spectral Initialization:
1: x
(²)))
2: [A..B") L T-SVD-Spaar Sppo-pee
m
Gradient Descent:
do 4: Update A A' V ACA' B, BB - BB) based on
3: for =0 O..... T Tipax
5: end for
Output: Recover tensor X A Timax B T.
Algorithm 2 Truncated t-SVD based spectral initialization:
[A, B -T-SVD-Spe((X,,
Input: X E Th Knn,
1:
fft(X, (].3)
2: for i
1,
113 do
(T()) ( V = ())
3:
7 = (1, (s) (1:r,1:7)) B = T (.1r)) (1:1,1r))
4:
5: A= ifft A (1.3), B iBft(B
6: end for
Output: Tensor factors A,B. B.
To establish the theoretical results, we first impose the following low-rank structure on X",
Assumption 1. Each front slice of X" has rank r & min 722, ns).
Assumption 1 is the same the low multi-rant assumption in 69 and implies rank;(X*)) Thus,
Theorem implies that X' has exact skinny I-SVD (68) given by
X = U S" (V*),,
(9)
where 4i E R XrXn3, S* E B and V e R Based on 9 we introduce the two balanced factors A R2ixrxn, B p xrx defined
A"
A
(1,3), = ifft(B (],
In addition to Assumption I assume X satisfies the following tensor incoherence condition, which ensures information is spread out across all tubes of the tensor, and no small subset of tubes carries dominant information.
Assumption 2 (Tensor incoherence condition). Let 2 satisfy Assumption I with skinny t-SVD given by p There exists constant μs that
max
22 (i, (.:1
V n
PT
and
max jE(nal
|1 (].;;:) S
(10)
(E(m)
1273
5

---

where || is the tensor spectral norm (cf. Definition actually degenerated third-orde tensor.
9.. Each horizontal slice matrix in the above is
Remark 1. Assumption 2 imposes uniform bounds the tensor spectral norm of horizontal slices of lensor factors. This assumption is equivalent to the matrix weak incoherence condition 168 Eq. (31)), which is assumed in the lensor completion problem under random tubal sampling. This condition is slightly stronger than the existing tensor incoherence condition that uses the Frobenius norm 24 28 68), due to the fact that our measurements of X' are taken tube-wise rather than globally.
For simplicity and without loss of generality, we assume R1 = 72 = for the spatial dimension of X². We denote max max (X²), min minn (2**) and the tensor condition number Since the factors are identifiable up to orthogonal transformations, we introduce the
= Tuin
following alignment tensor R' remove the ambiguity:
AA B'
A" B"
RA.
arg min REO,
R
(11)
where the set O, includes all orthogonal tensors with size r x x Recall that m is the number of measurements taken for each tube (cf. Definition [ With Assumption [ we are now ready to state the main result.
Theorem 2. Let X satisfy Assumption 1 and and the entries of local sensing matrices {Z be generated from i.i.d Gaussian distribution N 1). If the tube-wise measurements satisfy
na log" m (3000C) n
V ne) V1.
(12)
n
Then under the step size condition generated by Algorithm
Omin 100mo
with probability at least 1 [Dvng] the iterates
satisfy
AA"
AA*
S (1 0.1 0.1mmomin's - (ur)4 log (n V na)
R'
(13)
B'
B*
([47
AA" B*
(pr) -2641)
log" V na na)omax mn²
max 1e(2n
R²
S (1 0.Lmmpmmnn) 2964CC
B
(14)
where C is a universal constant.
Theorem 2 further implies the following fine-grained uniform bound the recovery accuracy for all
tubes of X"; new result in the t-SVD based tensor recovery literature.
Corollary 1 (Tube-wise bound). Under the same setting as Theorem by GD achieve
Ve
> 0, the iterates generated
max (A'' * (B3) -x= Se
(15)
in al most Ox² log )) iterations with high probability.
Next, we discuss the implications of Theorem 2 and Corollary in detail.
Computational complexity. The above results show that even for the non-convex loss (6) GD with spectral initialization converges to X at linear rate with iteration complexity O(k² log 2). The com- plexity scales quadratically with k, showing that GD converges faster if the ground truth tensor is well- conditioned. The computation cost per iteration mainly lies in performing FFT, SVD, inverse FFT, and matrix multiplication. The complexity of initialization is O (magn² + n n log ny + n n2n)) and that of per GD iteration is O (mngn? + n22ng log + rnng log na + n²r + nr?). Thus, the total computational cost of Algorithm is Ö (x²² (mnggn 2 + n²2ng log n3 + n²rr + n²²)a).
Sample complexity: Based on the local TCS model recover each tube independently, which requires measurements m on the order of ((n3). In contrast, Eq. (12) shows that collectively recovering all the tubes exploiting the low-rankness structure can
naive approach to reconstruct X is to

---

significantly reduce the sample complexity. Specifically, since the right hand side of (12) decreases linearly with n. we have that for a fixed tubal rank and tube length n23, larger spatial dimension leads to fewer samples needed per tube to achieve exact recovery. A direct consequence is that the sample complexity of our model outperforms state-of-the-art results as illustrated by Table [ The total number of samples taken over all tubes is Ô (r9) which is nearly order-optimal when compared to the degrees of freedom (rrns)) for tensors with tubal rank r [28].
Remark 2. The dependence of the sample complexity on the tubal rank of X" is T due to analysis technicalities. Similar high-order polynomial dependencies on the rank can also be found in the
literature of non-convex matrix and tensor recovery 18 32 47 50 159.
The implicit regularization of GD. Eq. iterates generated by GD remain incoherent throughout the optimization process. This implicit bias is crucial since the non-convex loss (6) is strongly convex and smooth when restricted the incoherent directions, thereby enabling the linear convergence of GD. Eq. (14) also leads to the new tube-wise convergence rate (T5), showing that the recovery error is spread out across all tubes. The main technique to prove this property is the LOO analysis, which will be discussed in detail in Sec.
reveals that even without explicit regularization, the
4 Theoretical analysis
This section outlines the analysis by providing intermediate results paving the way towards Theorem 2 whose complete proof is provided in Appendix A The starting point is proving the sensing map Z in (2) satisfies the tensor Restricted Isometry Property (T-RIP).
Proposition 1. If the sensing map Z and ground truth X
satisfy the conditions in Theorem and
the tabe-wise sample size has
2n r)m3k2 n22
m 2
(16)
n²8?
then tensor RIP holds with parameter 5, E (0,1) given as
m(1 - 6,)) |X 1/ - 2 (x |1 S m(1 + 5,) 1x
(17)
with probability at least 1 - exp (-cr(n r)n3}.
For the global TCS model, existing proofs used Bernstein incquality that is uniformly applicable to all rank-r tensors to prove the RIP condition. If we use the same incquality, the sample size required to establish the RIP condition given in Proposition I would be much larger than our current result due to ignoring the structures of the tube-wise sensing model.
Thus, compared to RIP result in Lemma 5 of [26]. Proposition 1 shows that under the local TCS model, a smaller sample size m suffices to guarantee | 1 (x* 1 concentrates on its expected value m ||x*1] F. The key property that leads to this result is that X satisfies the tensor incoherent condition (TO). Motivated by this observation, we prove next that the GD iterates also satisfy the incoherence condition, which will allow us to use similar arguments to show the empirical Hessian of the non-convex loss (6) concentrates on the population Hessian under the same order of sample complexity. The linear rate of GD then follows from the fact that the population Hessian is restricted strongly convex and smooth.
To prove that GD iterates satisfy the incoherence condition implicitly, we leverage the LOO technique and define the LOO map for the tube-wise sensing map Z, which is motivated by the matrix completion setting [8 32).
Definition 11. Given a tube-wise TCS map Z, the LOO map Z Z_i, : RxXXX p is identical to Z but excludes the measurements of all tubes belonging to the i-th horizontal slice of X Correspondingly, the projection map Pt.. B n for X* sets its i-th horizontal slice to zero. That is,
ZZz Kijo 0m-
1: k
(x (Kjjs Ongs
k i
1z 1z_ (20)2yg
[P,, (2))
(18)
k
k
In analogy to Definition 11 we additionally introduce the map Z.-, that leaves out measuring the j-th horizontal slice and projection map P.
7

---

Next, we construct the auxiliary sequences as the GD iterates generated by minimizing loss func- tions defined based on the LOO maps. Specifically, for I / I n. we define the loss function corresponding to leaving out measuring the i-th horizontal slice
c (A, B) = 3-1, (A+B*
xx + +lp... (A+B*
xx)
x
m A 8
A
B
B
(19)
with variables A E R2ixxxas B R The LOO sequence is given by
A 4 A VAC (A B²1); B = B VBC (1) (A B².d).
(20)
Similarly, for n. + < < 2n, we can also define the loss based on leaving out (1 n) lateral slice map Z (1-( and corresponding generated GD iterates as 119 and (20), respectively.
Furthermore, we define the following two orthogonal alignment tensors
A
AA
AA B
R
R
arg min REO.
R
:T
arg min TEO,
T
(21)
B
B
Theorem 3. In the same setting as Theorem
the LOO sequences satisfy
(
A L
AA'
(ur)5 log"(n V na)omax
max re [2m
R
S1
0.1mmrominn
2496C
B**
mn2
I::
(22)
A B
AA' Bt
(ur)4x2n log (n V na ma)x mn?
max 1e(2n
T
R'
S (1
0. 0.1mmjmmin 52C
(23)
with probability at least (IVV
Assumption 2 and (22) together show that the LOO sequences satisfy the bounded incoherence
condition, w While (23) shows that the GD iterates are sufficiently close to the LOO sequences. Eq.
(22 and thereby ensure that the incoherence condition (14) holds along the GD iterates.
The rest of the proof for Theorem iis is devoted to establishing that the non-convex loss (6) under sample complexity (12) is strongly convex and smooth along the incoherent directions satisfying [14] in local region sufficiently close to X' (cf. Lemma 7 in Appendix A).
Our last result shows that Algorithm generates initial points sufficiently close to X and also satisfies the tensor incoherence condition. Similar to the GD stage, 2n auxiliary LOO variables are introduced as follows. For 1 < S n, we define the [-th LOO variables A 0. as
0
Ed_, (2) (2)
(x*))
BOd1 = T-SVD SpeeSSee .r). O.
(24)
m
For n 1S1S 2n, generate (I -1 LOO pair of variables in analogous 24 by leaving 1-th lateral slice out.
Theorem 4. In the same setting as Theorem 2 if the tube-wise measurements satisfy
(100C)2 ((r))r/ 'n²" na log? (n na) 1,
(25)
then the initialization generated by Algorithm 7 and 24 satisfy
AA* B*
(pr) 5 ng log2 (n V ny n
R
S 988C
(26)
1
((
[A" |B
[A*
)
(ur) log (n V na n mn?
max 1E(2n]
R
B'
$ 5
(27)
(
- 0
A
(ur)5 log" mn?
( (n V 1
max te [e|2m]
5 126C1
(28)
D*
l:
8

---

max [m
A
[B001
T.
[A0T
1
R
S 52C
(ur)* 2n log V
n n²m
ne 7
(29)
with probability at least
(DVng)
The idea of the proof for initialization is similar to that in 32 and is provided in Appendix
5 Experimental results
We validate our theoretical findings on synthetic tensors (real-data results appear in Appendix C First, we verify the linear convergence of Algorithm Then we study its recovery performance under varying tube-wise sample complexity. Finally, we compare our method with existing works in terms of sample complexity and running time.
To validate convergence, we set (M1, R2, na) = (100, 100, 50), tubal rank r = 5, and condition number
1 for ground-trutt tensor X' that is generated from i.i.d.N(O.. 1) entries, per- forming an FFT along tube mode, truncating each frontal slice to rank r via SVD (setting the top singular values to and the rest 0), and then applying the inverse FFT. We set the = 0.2 and tube-wise sample complexity m = 10. Fig. plots the recovery errors vs. iter- ation number in 20 Monte Carlo trials under different initializations. The recovery errors plotted in three metrics: (1) the relative Frobenius norm error || - X || / /||x"" (1) the rel- ative tube-wise error maxij
(x
x²) "y:: p /mxx;
x Gj
(3) the relative incoherence error
((
A B' R
AA'
{[
maxie[[2)
B'
maxxe(am)
B
8::
C::
Fig. I(a) shows the linear convergence of our Algorithm in all three relative error metrics, Fig. ((b)
and Fig. (c) show the results of the GD under random initialization AA, 5 ~ NO a a n with I, 0.001, respectively. For convergence. Fig. I(b) shows large initialization cannot achieve exact recovery. For a 0.001, the " 0.2 is the same as the Fig. setting. Fig. [ shows that GD achieve exact recovery under small initialization with the nearly same computational cost as Algorithm I1 Fig. Fig. [[c]sshr show that our spectral initialization is not necessary to achieve exact recovery, and GD with random initialization can also attain this in global convergence, but the small initialization is necessary condition even under exact parameterization.
1, we select the largest " 0.0002 to guarantee
I(b) and
10"
Tobe
Frchmitte
Relative Eeror
10
102
10
10
10
100
200
400
2000
4000
6007
300
500
Iteration Number
Iscration Number
Iteration Number
(a)
(b)
Figure 1: Relative recovery
iteration number. (a) Algorithm with spectral initialization
in Algorithm 2 (b) Random initialization with a 1. (c) Random initialization with a = 0.001.
To illustrate the sample efficiency the method, we plot phase transition diagrams examine the recovery phenomenon with varying spatial dimension n and varying tube-wise sample complexity
m. We fix the tube dimension as ni- = 50 and consider the two settings: (1) r = 5; (2) r 10. We generate ground truth X through the abovementioned ways. We choose in [20 5 200) and for both r 5 and r and assess a trial to be successful if the recovered X satisfies || - X x1]]=/|| x' || S
m 1,2,
cases. For each (n, m) pair, we simulate 10 test trials
0.001.
Fig. 2 plots the fraction of successful recovery for each (n, m)) pair, and white denotes perfect recovery (100%), while black denotes failure (0%). Fig. [(a) and Fig. 2 plot r = 5 and r 10 cases, respectively. In both cases, the white successful region large, but is noticcably larger for

---

Table 2:
Comparison of runtime and required measurements m (TCS), m: sample size in tensor unit; ng: tube size; n. spatial dimension; r: tubal rank.
FGD
TNN (m time (s))
Schatten-2/3
Alt-PGD-Min
Ours
na
time (8))
TNN time (s))
(m / time (s))
(m time (s))
10 (r=2)
20
840/7.1
1450/1.6
1020/5.1
43/13.8
3/1.1
10 (r=2)
50
2200/ 175.7
4600/109.4
3100/181.7
45/15.6
2/3.7
20 (r=3)
20
2400/86.99
3950/7.7
2750/20.7
130/13.8
7/4.5
20 (r=3)
50
6800
/44044
13000/717.5
8500/988.2
135/80.4
3/11.6
30 (r=4)
20
4900/1812
7100/20.9
5250/90.0
250/47.3
12/16.1
30
(r=4)
50
13500/ 1626.
2/000/239556
16500/2344.9
268/ 155.9
6/18.9
r = than for = 10, reflecting the greater difficulty for higher rank settings. Morcover, as the spatial dimension increases, the required tube-wise sample size m for exact recovery decreases substantially, which corroborates our sample-efficient theoretical result.
200
180
dimcosion
160
Spattal diouneton
160
140-
140
120
120
100-
100
80-
60-
6 16
41 46
11 16 26
36
50
Tabe-wiso sample complexity m
Tube-wise sample complixity
(a) r
(b) r
Figure 2: Phase transitions for tube-wise local TCS model.
To validate the sample efficiency of the proposed tube-wise model and method as given in Table 1 we compare with existing t-SVD-based TCS methods, which include global TCS methods: FGD 26]
TNN (28), Schatten-2/3 TNN [20]. and the latest slice-wise local TCS model Alt- [64]. We
report results for n = 20, 50 only, as Schatten-2// TNN and TNN encounter out-of-memory issues for larger due to the huge sample size. For each method, we find the smallest number of random tensor samples m (each tensor has the same size as X and all entries generated from i.i.d. standard
x x--x11 1l
Gaussian distribution that can achieve exact recovery in the sense of
< 10-3, For the
X
computational cost, we choose the largest step size for each method that can converge under each parameter setting.
The comparison results are summarized in the Table 2 We can observe that tube-wise model and solving method can use both the smallest tensor samples and computing time to achieve exact recovery. This validates that our proposed model and method achieve both sample and computation efficiency. In addition, we can also find that for the fixed tube size ni and tubal rank with increasing size of spatial dimension n, all other methods need more samples to achieve the recovery. On the contrary. our model can use fewer samples to recover, which means that increasing the spatial dimension can reduce the tube-wise sample complexity. This result also validates our theoretical sample complexity in (2)..
6 Conclusion and future work
In this paper, we proposed a tube-wise TCS model under the t-SVD framework. We prove that GD with spectral initialization achieves exact recovery at linear rate. Our analysis reveals that the tube-wise sample complexity decreases linearly with respect to the spatial dimension. But several important questions remain open. The current linear-rate constant scales quadratically with the tensor condition number, motivating preconditioned or curvature-aware gradient methods to mitigate slow convergence on ill-conditioned instances. We also assume a known tubal rank and focus on third-order tensors; extending the theory to over-parameterized factorizations and arbitrary orders under modern high-order tensor algebra is an important next direction.
10

---

References
[1] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics, 48(3):1452, 2020.
[2] Joshua Agterberg and Anru R Zhang. Estimating higher-order mixed memberships via the 22,0c tensor perturbation bound. Journal of the American Statistical Association, pages 1-11, 2024.
[3] Talal Ahmed, Haroon Raja, and Waheed U Bajwa. Tensor regression using low-rank and sparse tucker decompositions. SIAM Journal on Mathematics of Data Science, 2(4):944-966, 2020.
[4] Silpa Babu, Selin Aviyente, and Namrata Vaswani. Tensor low rank column-wise compressive sensing for dynamic imaging. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5, IEEE, 2023.
[5] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical programming, 95(2):329-357, 2003.
[6] Changxiao Cai, Gen Li, H Vincent Poor, and Yuxin Chen. Nonconvex low-rank tensor comple- tion from noisy data. Advances in neural information processing systems, 32, 2019.
[7] Changxiao Cai, H Vincent Poor, and Yuxin Chen. Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality. In International Conference Machine Learning, pages 1271-1283 PMLR, 2020.
[8] Ji Chen, Dekai Liu, and Xiaodong Li. Nonconvex rectangular matrix completion via gradient descent without 8, regularization. IEEE Transactions on Information Theory, 66(9):5806- 5841, 2020.
[9] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[10] Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou. Understanding deflation process in parametrized tensor decomposition. Advances in Neural Information Processing Systems, 34:1299-1311, 2021. 2021.
[11] Rungang Han, Rebecca Willett, and Anru Zhang. An optimal statistical and computational framework for generalized tensor estimation. The Anmals of Statistics, 50(1):1-29 2022.
[12] Kais Hariz, Hachem Kadri, Stéphane Ayache, Maher Moakher, and Thienry Artieres. Implicit regularization with polynomial growth in deep tensor factorization. International Conference on Machine Learning, pages 8484-8501. PMLR, 2022.
[13] Kais Hariz, Hachem Kadri, Stéphane Ayache, Maher Moakher, and Thierry Artières. Im- plicit regularization in deep tucker factorization: Low-rankness via structured sparsity. In International Conference on Artificial Intelligence and Statistics, pages 2359-22412 2367. PMLR, 2024.
[14] Nick Higham and Pythagoras Papadimitriou. Matrix procrustes problems. Rapport technique, University of Manchester, 1995.
[15] Santhosh Karnik, Anna Veselovska, Mark Iwen, and Felix Krahmer. Implicit regularization for tubal tensor factorizations via gradient descent. arXiv preprint arXiv:2410.16247, 2024.
[16] Henk AL Kiers. Towards standardized notation and terminology in multiway analysis. Journal of Chemometrics: A Journal of the Chemometrics Society, 14 2000.
[17] Misha E Kilmer and Carla D Martin. Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):641-658, 2011.
[18] Eren C Kizildag. Information-theonedl guarantees for recovering low-rank tensors from symmetric rank-one measurements. In 36th International Conference on Algorithmic Learning Theory.
11

---

[19] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):55--00, 2009.
[20] Hao Kong, Xingyu Xie, and Zhouchen Lin. t-schatten-p norm for low-rank tensor recovery. IEEE Journal of Selected Topics in Signal Processing, ((6)):405-1419) 2018.
[21] Kiryung Lee, Rakshith Srinivasa Sharma, Marius Junge, and Justin Romberg. Approximately low-rank recovery from noisy and local measurements by convex program. Information and Inference: A Journal of the IMA, 12(3):1612-16) 1654, 2023.
[22] Jing Li, Quanxue Gao, Qianqian Wang, Ming Yang, and Wei Xia. Orthogonal non-negative tensor factorization based multi-view clustering. Advances in neural information processing systems, 36: 16:181862 1081866182000 2023.
[23] Chunyan Liu, Sui Li, Dianlin Hu, Jianjun Wang. Wenjin Qin, Chen Liu, and Peng Zhang. Nonlocal tensor decomposition with joint low rankness and smoothness for spectral et image reconstruction. IEEE Transactions on Computational Imaging, 10:613-627, 2024.
[24] Xiao- Yang Liu, Shuchin Aeron, Vaneet Aggarwal, and Xiaodong Wang. Low-tubal-rande tensor completion using alternating minimization. IEEE Transactions on Information Theory, 1633):7714-1737, 2019.
[25] Xinling Liu, Jingyao Hou, Jiangjun Peng, Hailin Wang. Deyu Meng, and Jianjun Wang. Tensor compressive sensing fused low-rankness and local-smoothness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8879-8887, 2023.
[26] Zhiyu Liu, Zhi Han, Yandong Tang, Xi-Le Zhao, and Yao Wang. Low-tubal-rank tensor recovery via factorized gradient descent. IEEE Transactions Signal Processing, 2024.
[27] Canyi Lu. Transforms based tensor robust pea: Corrupted low-rank tensors recovery via convex optimization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11 115--1522 2021.
[28] 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 (IJCAI), 2018.
[29] Canyi Lu, Peng Xi, and Wei Yunchao. Low-rank tensor completion with a new tensor nuclear norm induced by invertible linear transforms. In IEEE International Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
[30] Yuetian Luo and Anru R Zhang. Low-rank tensor estimation via riemannian gauss-newton: Statistical optimality and second-order convergence. Journal of Machine Learning Research, 24(381):1-44 2023.
[31] Yuetian Luo and Anru R Zhang. Tensor-on-tensor regression: Riemannian optimization, over- parameterizaaton, conpuaaillc gap and their interplay. The Annals of Statistics, 52(6))2583-2611 2024.
[32] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in noncon- vex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345-3354. PMLR, 2018.
[33] Ziye Ma, Javad Lavaci, and Somayeh Sojoudi. Algorithmic regularization in tensor optimization: Towards a lifted approach in matrix sensing. Advances in Neural Information Processing Systems, 36:39994-40005, 2023.
[34] Ziye Ma, Igor Molybog, Javad Lavaei, and Somayeh Sojoudi. aver-parametrization via lifting for low-rank matrix sensing: Conversion of spurious solutions to strict saddle points. In International Conference on Machine Learning, pages 23373-23387 PMLR, 2023.
[35] Roy Mathias. Perturbation bounds for the polar decomposition. SIAM Journal on Matrix Analysis and Applications, 14(2):588-597, 1993.
12

---

[36] Cun Mu, Bo Huang, John Wright, and Donald Goldfarb. Square deal: Lower bounds and improved relaxations for tensor recovery. In International conference on machine learning. pages 73-81. PMLR, 2014.
[37] Seyedehsara Nayer, Praneeth Narayanamurthy, and Namrata Vaswani. Phaseless pea: Low-rank matrix recovery from column-wise phaseless measurements. In International Conference on Machine Learning, pages 4762-4770. PMLR, 2019.
[38] Seyedehsara Nayer and Namrata Vaswani. Fast and sample-efficient federated low rank matrix recovery from column-wise linear and quadratic projections. IEEE Transactions on Information Theory, 69(2): 177-1102. 2022.
[39] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing. 3365):2295-2317,200 2011.
[40] Vern Paulsen. Completely bounded maps and operator algebras, volume 78. Cambridge University Press, 2002.
[41] Liangzu Peng, Juan Elenter, Joshua Agterberg, Alejandro Ribeiro, and Rene Vidal. TSVD: Bridging theory and practice in continual learning with pre-trained models. In The Thirteenth International Conference on Learning Representations, 2025.
[42] Wei Pu, Junjie Wu, Yulin Huang, and Jianyu Yang. Ortp: A video sar imaging algorithm based low-tubal-rank tensor recovery. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 15:1 15:1293-1308, 2021.
[43] Zhen Qin, Michael B Wakin, and Zhihui Zhu. Guaranteed nonconvex factorization approach for tensor train recovery. Journal of Machine Learning Research, 25(383):1 48, 2024.
[44] Holger Rauhut, Reinhold Schneider, and Željka Stojanac. Low rank tensor recovery via iterative hard thresholding. Linear Algebra and its Applications, 023:220-262. 2017.
[45] Noam Razin, Asaf Maman, and Nadav Cohen, Implicit regularization in tensor factorization. In International Conference on Machine Learning, pages -9244. PMLR, 2021.
[46] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks. In International Conference on Machine Learning, pages 18422-18462. PMLR, 2022.
[47] Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie. Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing. In The Thirty Sixth Annual Conference on Learning Theoory pages 5140-5142. PMLR, 2023.
[48] Rakshith S Srinivasa, Seonho Kim, and Kiryung Lee, Sketching low-rank matrices with a shared column space by convex programming, IEEE Journal on Selected Areas in Information Theory, 4:54-60 0054-60.22 2023.
[49] Rakshith Sharma Srinivasa, Kiryung Lee, Marius Junge, and Justin Romberg. Decentralized sketching of low rank matrices. Advances in Neural Information Processing Systems, 32, 2019.
[50] Dominik Stöger and Yizhe Zhu. Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity. arXiv preprint arXiv: 13276, 2024.
[51] Tian Tong, Cong Ma, Ashley Prater-Benneter Erin Tripp, and Yuejie Chi. Scaling and scalability: Provable nonconvex low-rank tensor completion. In International Conference on Artificial Intelligence and Statistics, pages 2607-2617. PMLR, 2022.
[52] Tian Tong, Cong Ma, Ashley Bennette, Erin Tripp, and Yuejie Chi. Scaling and scalability: Provable nonconvex low-rank tensor estimation from incomplete measurements. Journal of Machine Learning Research, 23(163): 2022.
[53] Stephen Tu, Ross Boczar, Max Simehowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. In International conference on machine learning, pages 964-973. PMLR, 2016.
13

---

[54] Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika. 31(3):779-11, 1966.
[55] Namrata Vaswani. Efficient federated low rank matrix recovery via alternating gd and mini- mization: A simple proof. IEEE Transactions on Information Theory, 2024.
[56] Roman Vershynin. High-dimmensioall probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[57] Andong Wang. Chao Li, Mingyuan Bai, Zhong Jin, Guoxu Zhou, and Qibin Zhao. Transformed low-rank parameterization can help robust generalization for tensor neural networks. Advances in Neural Information Processing Systems, 36:3032-3082, 2023.
[58] Andong Wang, Yuning Qiu, Mingyuan Bai, Zhong Jin, Guoxu Zhou, and Qibin Zhao. General- ized tensor decomposition for understanding multi-output regression under combinatorial shifts. Advances in Neural Information Processing Systems, 01147759947333 2024.
[59] Haifeng Wang, Jinchi Chen, and Ke Wei. Implicit regularization and entrywise convergence of riemannian optimization for low tucker-rank tensor completion. Journal of Machine Learning Research, 24(37)) (114)):--8844 1-84, 2023.
[60] Hailin Wang, Feng Zhang, Jianjun Wang, Tingwen Huang, Jianwen Huang, and Xinling Liu. Generalized nonconvex approach for low-tubal-raakk tensor recovery. IEEE Transactions on Neural Networks and Learning Systems, 3305):330533319, 2021.
[61] Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differen- tialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)) Mathematische Annalen, 71 71(4):441-47) 1912.
[62] Tongle Wu and Jicong Fan. Smooth tensor product for tensor completion. IEEE Transactions on Image Processing, 2024.
[63] Tongle Wu, Bin Gao, Jicong Fan, Jize Xue, and Wai Lok Woo. Low-rank tensor completion based on self-adaptive learnable transforms. IEEE Transactions on Neural Networks and Learning Systems, 35(7):8826 188888888888888- 2022.
[64] Tongle Wu, Ying Sun, and Jicong Fan. Non-convex tensor recovery from local measurements. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 21590-21598 2025.
[65] Zhong-Cheng Wu, Ting-Zhu Huang, Liang- -jin Deng, Hong-Xia Dou, and Deyu Meng. Tensor wheel decomposition and its tensor completion application. Advances in Neural Information Processing Systems, 15:27008-27024 2022.
[66] Jize Xue, Yong-Qiang Zhao, Tongle Wu, and Jonathan Cheung-Wai Chan. Tensor convolution- like low-rank dictionary for high-dimensional image representation. IEEE Transactions on Circuits and Systems for Video Technology, 34(12):13257-1322 2024.
[67] Feng Zhang, Wendong Wang, Jianwen Huang, Jianjun Wang, and Yao Wang. Rip-hased performance guarantee for low-tubal-rank tensor recovery. Journal of Computational and Applied Mathematics, 374: 12767, 2020.
[68] Zemin Zhang and Shuchin Aeron. Exact tensor completion using t-svd. IEEE Transactions Signal Processing, 65(6):151111526 2016.
[69] Zemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, and Misha Kilmer. Novel methods for multilinear data completion and de-noising based tensor-svd. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3842-3849, 2014.
[70] Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring decomposition. arXiv preprint 16Xiv:1606.05533 2016.
[71] Xi-Le Zhao, Hao Zhang, Tai-Xiang Jiang, Michael K Ng, and Xiong-Jun Zhang. Fast algorithm with theoretical guarantees for constrained low-tubal-rank tensor recovery hyperspectral images denoising. Neurocomputing, 413:397-409, 2020.
14

---

[72] Meng-Meng Zheng, Zheng-Hat Hai Huang, and Yong Wang. T-positive semidefiniteness of third- order symmetric tensors and t-semidefinite programming. Computational Optimization and Applications, 78:239-272, 2021.
[73] Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. The global optimization geometry of low-rank matrix optimization. IEEE Transactions on Information Theory, 67(22)1308-133 1331, 2021.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract/Intro state the tube-wise TCS model and our guarantees; Thm. (linear rate) and Eq. (12) (sample complexity) establish the claims; Alg. 1-2 specify the method; Table compares sample complexity; Sec. 5 validates on synthetic data.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Sec. 6 (Conclusion) lists limits: quadratic dependence on condition number, known-rank assumption, and focus on third-order tensors; it also outlines preconditioning. rank-agnostic analysis, and higher-order extensions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
16

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assump. 1-2 are stated; main results are Thm. 2 and Cor. 1; supporting tools include Prop. 1, Def. 11, and LOO sequences; full proofs in App. A-B with intermediate lemmas.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
17

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer:
[Yes]
Justification:
We include anonymized code and run scripts with instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttpp/s/mouris...cpppptt/t/t/ie
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer:[NA)
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
22

---

Appendices
A Proof for GD Stage
We first prove the tensor RIP result of Proposition T in Section A. Section A.2
A.3
A.
and A.5
23 and (14) in Theorem and Theorem 3 respectively. The final section A.6] presents the technical lemmas used throughout the main analysis. The core idea of the proof is an induction argument: assuming that equations (3)) 222 (23). and (14) hold at the t-th iteration,
proves the 13
we show they continue to hold at iteration + 1. Therefore, establishing that they are satisfied at initialization (L = 0) via spectral methods completes the proof.
A.1 Proof of Proposition
We prove this proposition by expressing 2 (X**) ||.- m | as a sum of independent, mean- zero, sub-exponential random variables. We then apply an e-net argument together with the sub- exponential Bernstein inequality to derive the desired concentration bound. Crucially, independence of the sensing matrices our tube-wise model and the tensor incoherence condition allow us to obtain a tight bound under the efficient sample size with high probability.
Proof.
2 (2e) 11 m 2
m [(
1=1
j=1
n
Σ>
(xi):
T D Zi m (Xix.) Xijs)
7
n
m
2 Zija Xi;: (Xi (xir.)
T
X
(30)
Tye
is apparent that ( are independent sub-exponential random variables with zero mean and bounded sub-exponential norm ||K I
1l. Thus, we can use sub-exponential Bernstein inequality with e-net argument to bound such deviation. Firstly, > 0 we have
CC||
e
82
Σ ii=1
Σ m= Σド=
Tijally
ija
mC
X X
12
mC maxij
11
E)=1
X
f2
(31)
mC² maxij
||
||
Secondly, there is
t C maxi;
(32)
maxifk
Ris 1
|
Setting & = mC'6, ||
then there is
t2
mo
X 1
m8,
x
min
min
2 maxij
|| |
11
||
1
C C'max ||
max4y
|
max.j
|| 11
| ||
m55
||
m5 |
m
X ||
(584)
m62
maxiş
x 11
max; [
|
max,
(ur
x
(ur)
|
23

---

mo. Mara min )2")
n
11g
(33)
n²rx2"
where (i) is based the tensor inequalities 93 995 and the tensor incoherence condition in 10p. Based on sub-exponential Bernstein inequality for fixed At"", we have
m
PP ( 2 (X*) || | > mC5, X |1:))
S exp
(34)
12
Thus, for all the incoherence X with tubal rank r, the covering number is O (r(2n r)n3), then based on the c-net argument in [56], there is uniform bound as
11²) S exp {
m u²rR22 r(nn r)ns
P ((1Z
| m x | 2 mC'6
(35)
Combining the tube-wise sample complexity in (16). we obtain the 17 with high probability.
L
A.2 Proof of
Following the proof of g we construct the auxiliary sequence as follows:
A
I+1
A' * R'
1 z (Ax) + B
mi
A" (R¹)² T (14') T A' - (B²)² * *B²) R²
2
(36)
B ++1
B² * R - n (z (A 1 A
mi B" (R')" (1B)) - (A4t² *A RR
2
(37)
where we define the quantity A == A' (B') T - A (B*)²
Next, we show that the expected auxiliary sequence contracts toward the global optimum in one gradient step. By controlling the deviation between the auxiliary sequence and its expectation via concentration bounds, we ensure the actual auxiliary iterates also exhibit this local contraction. Finally, we prove that the true GD iterates remain sufficiently close the auxiliary sequence, and hence inherit its local contraction toward the ground-truth factors.
It is apparent that the above defined quantities expectations have
A' R
' * B
mi
A (R')² T' ((A') A' - (B²)² * B3)) RR',
2
(38)
B +1
Bsd
R'
7pm
A x
T
A*
my
B * (R')" T ((B')" BB' - -(A0) * A²
R².
2
(39)
Based on triangle inequality and decomposition, there is
A4 AA*
E ++1
++1
A
++1
A
* R 1+1
B
B'
E
B
1+1
B
i+1
B
1+1
1
11
A4
A ++1
+
B
R
1+1
(40)
1Ts
Next, we need to bound II, 12, Il respectively.
A.2.1 Bound for II;
We first give the concentration inequality for auxiliary sequence as follows.
(z (Aix)
m 1
I1 =
(3 (A'x m x
T
A'
24

---

S " (1 (A'x m)x) B=1 + (2 (Axx) m * 1211
2gCmr
log(n V na) max | ( 15:
(1 (|A1))
(9)
4m/mm
max
log(n V 1z) max (A # R² - -Ai..) * (Bjx)² + AAi. (B) *R' -:::)
Bj:)) "11
(A
R
B ju
R
(18)
4m/mr
max
log(n V n1a)
max || RR' AA max
|
m
)
max
| max
(B's R B3)
"B*)
+ max
(1 R² A*) max
( R² B²) 3::) (m.ll)
(iv)
mmr
max max2 Rug3
log(n nz))
11880'1
(ur) log" (n V 123)0max
pro
m
12m
71
(ur))nnng log2(n (n V m n2m
504p'y
(v)
ma max 12
log(n n3) 0.3 pr
4nCmr
max
m
(ur)3x2 log (n V n3) n nm
0.012xmmmmin
98Cp'
(41)
where (i) is based Lemma
2 and (īi) is because
(A )s:lll A R *BB) j:: R RRT A (B (B)))²1
(A R²
A:..) BB
) A (B).
B TT + (A R'
A..)) (B).
B )²1
(42)
(iii) is due the tensor norm inequality 95 (iv) is based tensor incoherence condition (T0) and condition in 14). The (v) is due to the tube-wise sample complexity in (12)
A.2.2 Bound for ll2
To bound the distance between expectation of auxiliary sequence and optimum factors, we firstly defined the following eτror terms
A : A' R¹
A"
A = R'
-B"
A 1
A =
A
A B
E = A'A
(A)s)
BB"
1
A
(A')²
T
A' + A (AA))
1
A (43)
2
E A f
(A'))
A
- B* (A
2 B (A'A)T
A'A
(44)
2
The Il, can be bounded as follows.
A
Il
E
B
B'
A
* B
1992 A' * (R)T ((A7)T A' -(B'TT B') * R
A
17m
AA/ x
A"
mp B² (R)² ((A')= * A' -T B' R
25

---

A Tim (13)² 13'
A' (AA)) A'A (B")² 4 (Ab)² 2 =B* - (A4)) " *A*) + +im
A/
77m (At)² * A')
+ 2 B'= (-(3") 4 + (A')² A'A (AAA² T *A' (A r *B") + 7mm
A
mm * *B²)²
* =B" - -mmAA * (A*)
* * A + n
A
A B (At)*
T
A -mmBB * (B*)²' * A + TME
B
I, 21mmAA (Ar)²
A
* (I, - 21mm (A7)* AA))
+ 1
A
3
+ mpm
2
A B
[nn -2nmB' (B')²)
A B
I, 2pm (A+)** * A | + 2 Izm 27m
[A' (Aa)T
O
11
||'
2
0
B +B*)
+ ypm
(6)
(1 minm || I| + 4mm || |ATI
(6))
+ 4mn /mn//max /max 9 (ur)) log2 (n V naa
mmn
A
nm
(ur)) ny log2(r (n V n
(1 min)
||
4mmomin 980p' /
|لا||
nmm
$ (1 0.9
||اا|||
(45)
T A + (AB)² BB" is the symmetric tensor. (ii) is due where (i) is based on Lemma that (A'A)²
to || || + E S 4 |||
|. (iii) based on (13). and the last inequality is because of the lower bound of tube-wise sample complexity in (12).
A.2.3 Bounding for IIg
To bound the distance between auxiliary sequence and true GD iterates, the proof follows the proof of claim 10 in [8] Since we want to use Lemma bound the II as. For invoking Lemma 6 we can assign
AA' B'
A ++1 1 ++
A
X =
X1
and X2 =
1 * R
(46)
The alignment tensor between Xo and X2 is actually R2 (R)) T
R2+ Now we prove the alignment tensor between X, and X, is actually R2 = I,.. Based on tensor orthogonal Procrustes
in Lemma 4 this is equivalent proving that (A+*) AA 4+1 (B+)T T
B" *+1 is the symmetric
positive semi-definite tensor. Based on definition in (38). there is
x X1 (A+)*
A's R + (B*
13' RD
17 (At)"
Z A'' (B') A (B*))) 1*
17 (B*' Z z AA' (B')
A' (B)))) A'.
(47)
Based on definition of R' and Lemma and semi-definite positive. Thus, (A')² * *A"
4 the (Ar)T A' R RR' +B*) B RR is symmetric ++1
+ \B") T =B"
++1
is symmetric. In addition,
++1 (A+)T + (B+*T * B
(A77)T * A" + (B+) TT * 13*
2//mx (11 + 1l2)
(8) /omax
(3r))32223 log2 (n V n3)amax
0.01 0.012rm0 98CP'1
+ (1 0.9rpmomiu)
|
nm
(dis) < 2
(ur)3x22 log 2 (n V na 13)0max
0.012mmo P'CC''
26

---

(ur)) ny log"(n V nz)o
(1 0.9))mmmin 98Cp' /
nm
-98Cp' (ur)4n ng log (n V na) mm
S min (1 0.8881/m0miin)
S 0.50minn
(48)
where (i) is based on definition of 11, II in (40) and (ii) is substituting results in (41) and (45)
(iii) is due to condition (I3), and the last incquality is due to the step size condition and tube-wise complexity in (12). Moreover, we know
[A- [
AA B"
miin (AA'T A' + (B*)*x 13) min
20 min
(49)
Thus, based on Wely's inequality for tensor, which applies matrix Wely's 's inequality for the block diagonal matrix in the Fourier domain, there is
Fmin (AA7) T * A² ++1
+ +B²*
Th * B(t)) N 1.50 mins
(50)
which means that (At)* * A H+
+ (B*)
* B
1+1
is positive definite tensor.
To use Lemma 6 we should verify the conditions in Lemma
We have proved
A (+1
A 1
A 1
min (Xx)
(51)
B
1+1
2
The last thing is to verify that
A
+17
A+
- (A*)
* R
(52)
B
1+1
B++1
B"
4
as follows. Based updating of
and
8
there is
A 1 R' A'' 1/ 2
13
R
(A' R') (RR')' T ((4)) T *A' "(-("")" * +B¹) RR²
2
11+ * R² = B3 * R' - (3
A' * R
B R') (R')" " * ((B)) * BB* (A') * AA + R².
2
(53)
Thus,
A4+
Ä ++1
X X21l= =
* R
B3+1
B
2 (A
A + N34 AAA * (R')² T
((44) T * A' - -(B²) BB) * R²
(2')(4x)) T
+ マ 4/3 (R')² T * ((B)) T * BB' - -AA)²
T * A * R
11 | (4x) A + | (3' (Ax)) r * 2/2 1) + mm ||| (A')T * A' - -(8")" BB' A
5 (1(222 - -I) (Ax) * A/3 + m A A
+ ((8 mI)
(Ax)) -//l)
+
+ mm (2||471) | + 2 |1
| /1
+ |
+ +||ا I²) |اه||
$ n (1(2 mI) (A
Abll
( mI) (Ax))² T
الله + 2m | | II)
+ mm (4114~11 || + 2 11)
|
② 1 (1( - - (A الله +
- mI) (Ax))² -اàl))
27

---

+ Amn
||
| + +
I¹) ||ا|||
(1))
4Cro
mig
log(n na) max (axx A3:
||مو|| + 12mm ||A4* ||
<4Cmnr
nin
log(n V nz)
|ل|ه max
|| (A))))
max
|
+ max ||
( max ||
+ max |I
max (| (
+ 12mm
||
A
$ 120mm
nn3
log(n n V n2) max |
max A 1 + 12mm
|| ||
m
nng log (n V ns)
(ur))58ng log (n V n
12Cmmr
594Cp'
m2m
(jur) log"(n V nz) muxx
+ 12 maxxityy 98Cp'
||
mm
$ 0.08 min
mn A
(54)
where (i) is because
x
A' (B')² 2' A (B*)*
S |A' R² A' || B +|+ B * RR' -B* || + ||
R' A B R² B+1
2 A A + A
(55)
(ii) is based on Lemma sample complexity 122
2 and last two inequalities are due to the condition
(3) (4) and wise
Now the condition
1
X21l
AA* B*
I 0.08
Umin
mi7
|
mmax
2-2 min (A*)
(56)
4
is satisfied. The last inequality is due to the step size condition in Theorem condition (3 and tube-wise sample complexity 12) Finally, based on Lemma 6 there is
1++
A 1
113
R
++1
< 9k X
X21l
< 0.720 717
A
(57)
Combining the bound in
45
and
57
there is
A+
R 2+1
II, Il II,
B
1
0.01 0.012mmomin 98Cp'' (pr)3n2ng log2(n V n2 13)omax
num
+ (1 0.9mmaamin)
|| + 0.72mmo
A
(nr)2k²ng log" (n 12) max
0. 1.18mmmmmi) -9805mpm))))99C(p) 9
177
28

---

(40)
p / (ur)) log (n V mg)omax
(58)
nm
The inequality (i) uses
13 and (ii) is due to p= (1 - 0.1rmommin)
A.3 Proof of
The leave-one-out sequence with respect to the I-th horizontal slice is generated by the gradient descent method for solving (19) as
A 1, (At = (B8.)= xx) * BB - -PP,, (ath * (B8.)² -xx- * B3d
A t
mm
1 * ((4::)) T.
* *A' -(Bi)) T
1B'
2
T (Ath (BB1.) T X" ))
Pt. Aat (B 7 - x xxx1)² 7
(Bth)-
Bt+ = =B
3" 1
* A P
A
mil
Btd
((Bt.)) T * Bzt - (Aa1)) T
* A
(59)
2
For n + 1515 2n, the modified loss function is
min AER"XTX"3
(A,
3 - (A* [A*B* BTT x²)
+ -x*="*+''' 1|
(P -x:)
BERaKrXng
A A B", BB
(60)
8
The leave-one-out sequence generated with respect to the lateral slice the gradient sequence as
A 1411 = Al n -(((n)) 3 Ar * (BI.)² T - X
Bz.
:1(P.-(l-n)) -((xx) A (BL)² T
- -x" B'
mn 4. * ((4.1) * A'l
(B3..)
T
* *B'
2
B Bid
zc -1--(-n)
((-(nn))
A4 (B(.) T
- xx:)
T
* A4
P. (((-n)) Aah (BU.)² T. xx*) T
A
my
1ddd
(BBL) BL - (44)) T
* A
(61)
Without loss of generality, we consider the case where E [n], then the formula has
( B++1.
[44111 AA'
= A x R AT.-- - mmm AAi (BB.) T A.. * (B='))
* ++
* BB'. * RR
13
E,
+
A * RR'
Al..- 17m AA (B'))²
-Ai. (B²'T)
BBd * * * ((Rii)
* R *R(+111 I,
Ea
7Mm At. * ((a:))) * A'd - (Bt))² +BB
R 1+11
(62)
2
E3
29

---

For bounding the spectral norm of E1, with defining the notation A = A * *R A D :
B R B then there is
|| || (I,- -.mmm (B B3) (A%)
mm ((44)
A (A
BB RR.
1::
-mym (AW) 1::
(B*)²
A 4.
|I, mn (B') ) B
( 1::
+ 1pm |
-ل [1 (B*1)
+ mil ||...
A
|
B
I myy (B*) )" * BB|
||
||
+ mp
||ll|
|| |
-لهه
+ +2
1::
| |I
A t.i
(
A
+ |I ||)
(63)
Now comes to bound the
f./
as follows
A
[A* B
t.
A
R
B
TA
A 13a
AA"
VA
13
* RR
R
+
* R
B
AA
A"
A
[A"
9K
B
T
B'
R
B'
RR
B
(68)
(ur)* ( log" (n V o
(ur)+ ng log" (n V nz)o
S 9K 520p'1
+ 9
n²m
(ur)* ng log" (n V ng)o nm
< 12k p20p11
(64)
reuses the Lemma
to bound the first term of RHS of the above inequality as X
AA"
X1
and 2
T. It is apparent that ||=; Xull || X S
B
B'
B
(A') and | X
X
mmax (A") based on [3]
23
and tube- wise sample complexity
(ii) is due to 13) and
23
Substituting above inequality into (63) would have
(ur) log (n V ng) nmm
|| il S (1 mmn
)| (A 1::
+ mm ( t::
12x 52Cp'
(ur))n9ms log2(n na) nm
2 mmax
+ 12x 5
(ur) ng log" (n V 13) nm
am
pro
12k 52Cp'1
n
(ur)4k9gg log" (n V n3 maxx nm
mmax + 12k 52cp't
(ur)4 log" (n na)) [(~
(1 mmmmmi))
+ 11770
l::
nmn
1::
(ur)+)5ng log? (n V na)o
pr
1248C'pp1
mm max
n
30

---

(6]
0.83mmommnn
(A
.11
+ 0.5mmmmmin 24960pp
V
((r))5 log V ns)
n
(ur)5nena log2(n na)omax
m.6mmmmiin)
2496Cpp
n²m
max
(65)
where the (i) and (ii) are due to 112 (iii) is due to (22
and step size condition in Theorem
For the E,, we have the similar bound as (48) in
g as
| S | + (A4))..ll
(R..)
-1
R 1+11
I,
(8)
2 2
mrox
(R R
1+1,1 I,
(v/
2
< 2
pro
2 x 1250 mm p2
(ur) log2(n V ny o
(66)
nm
where the (i) is due to (65 and the last inequality is due to Lemma
For the 33 there is
|E
1ym
(44
2 الهه
||4|||
+2
A
B3*
A
| 1')
t::
1ym
(I((A)) (d)
+ [14i..1)
(4|/4*)
||41
2
r./
(ur)5 log ( V o
m
2496C|
LTO max
/ max
A
n2
n
prr
e.l
6axx
m
(ur) 2n9 ng log2(1 V 13)
1872C
(67)
nmm
where (i) uses the result in (22 and tensor incoherence condition in 10 (ii) and last inequality use the tube-wise sample complexity and (64). respectively.
Finally, combing the
665
66 and 667 would induce
1((
A 1+11 B 1
A+
(ur)3 log (n V na mmax n²m
R
2+1
(1 0.6 2496Cp'
B'
(2500C) (ur)* log V vz)
mm
( log (n V na)omax n2² n²m
(pr) log" (n V na o
+ 18720minomini
n²m m
< 24 (ur) 5 log 2 (n nz) 13)
(68)
n² m
31

---

The last inequality is due to the tube-wise sample complexity in 12
A.4 Proof of 23
Based on definition of T. in
21p.
there is
AA' B
R 2+1
A 1
+-1
* R²
[ B
T
(69)
B
B++
B B++1
Without loss of generality, we can consider the leave-one-out sequence under E [n]]. Based on {8 and (59). there is decomposition
A B
11
A B
[2 T = E1 +
R
(70)
E3
where the ε E2 and & are redefined as
E
A
"IVL(AA
*R² 15-((1
(1B0.)
- 1//VC .B.1) T
(71)
B
E2 =
mP,,
(Atit, (Bn..) T - A' * (B:)7)
-i Z1.
(At' Z1:
* (B)
* - -A"
(B1)7)
* *B''. TT
(72)
Eg mPP, [A (Bt))- T - A * -A* (B1)²)
AA * (B81)² A' (B*)² B1.
A T
(73)
where Z E [n1] denotes the tube-wise sensing operator that only tubes in i-th horizontal slice are sensed based on 2 and all other tubes are not sensed, i.c., for given E [n2]. there is
= { ZZ
k Vj
E [n]
B (2))
(74)
Om,:
i Vj E [n]]
Now we bound each of the error terms || ||E2|| and ||Eي|| in turn. For [& we apply Lemma 7 which provides restricted strong convexity and smoothness of the non-convex loss, establish a local contraction of the distance between the auxiliary sequence and the true GD iterates. The terms [E and ||E|]] are then controlled by our concentration bounds, ensuring they remain sufficiently small.
For 1,, there exists T E [0, 1] such that
||E1| || = [I V2 (TrA * The ti + (1 - -)'A'' * RR, 7B"
+ (1 +
(1- R¹))
AA T A' * R 1 T 13' R
A * T. A'a R Bt * T
$ (1 5
min
(75)
B
The inequality is based on Lemma follows. Based on 79 14 and tube-wise sample complexity we can conclude that
T T (1-T)A' R' u*1 B
A T U
max
T (1-T)B² R'
< max
1ddd * TTa V*
1::
1::
AA' x R 22" 13' R! V
+ (1 7) max
V o max
500 2n
A'' x RD U*1
A'' * R' - U²
B x R' - V
B R' V'
32

---

max
(76)
500k
where the third inequality is due norm inequality 92 Lemma 7
The above two conditions satisfied in
For E3, we have
72
||
Σ
ZijZy,
ml)
(Ax)
lg:
J::
Zhi ml)
A %/l
11:
Z122212 ml)
A
%.
||E3||
12:
1
7 Lm ml)
41
x
Inc-
77 ml
A !.
11:
1Z ml)
A 1.
12:
(77)
T Ztn ml ( ( 4.1
Inc-
where A == A (B'.) T
A" ) and we would bound the || separately. Before
that, we focus on uniform tuse-wise bound for A x. Vj E [m].
A
1.1
(B)))
T
B
L::
1::1
+ A (B) T Bi..) T
1
The
Ali))
(B)r)) T
(All The
A
(B T B3.z)
* 1. Ati
|| || + ||
| T Bj+
+
A Thd
ATT
133/ T
B
(1)
< 129
(ar)5 log² (ns V 1))omx n2m
uro
(ur)) log² (ns n) n2m
(por)5n0ngg log" (ng n)) n²m
puro
13000
(78)
(i) is based on 95 and the last inequality is due the tube- wise sample complexity in 122. (ii) is based on the tensor incoherence condition (10) and the following inequality.
((
(44
AA" B'
AA"
max
B4.
T
max
* T
B²
*
R
1::
(
AA"
AA"
max
* RR.
B'
1"
1::
33

---

(in)
AA
[A"
([T7) B3'
AA' B
13'
TT.
13
* R²
+ max
* R
(v)
(1r))422 ny log" (nz V n))omax n2m
52C
(ur)s ng log (nz V n.Jmax n2m (ur) na log (nz V n
594Cp'
< 6460
(79)
nmm
where (iv) we use inequality in (92 and (v) are due to 23 and on Lemma as
13
Now we bound the ||E2|| based
|22l| & 2Cmr
n13 log(n V na) max
(
|3
15
is:
F
(es)
2Cmr
Th3 V
log(n V /na) 1300C/
(ur)) log" (ng m))omax
pvo
m
n.m.
n
T
Bz + [18*
pyy / (ur))n> (ar)snono ng log" (nz V n) m)xmax
(wsi)
(ur)3 log (n V na 1 max nm
2600C²m
m
nm
(ur) log (n3 V mmaomxx nm
646C
+ 0 max
(nr)) 1 (n V na)na
p (ur)5 log"(ns V O
< 5200C mommin'
n²m
(ur)) log (n V 0max
20
(80)
mm
where (vi) and (vii) are due sample complexity (12).
78
respectively. The last two inequalities due to tube-wise
Now comes to bound the ||El]. To obtain a tight bound, we also bound the spectral norm of each tube,
Zig ml)
A
Vj
E [n]. there is
ij
12
f2
f²
Σ
1=
K2
Σ
A
1.
m max
(A
|T
mng max,,;
( 15:
1j:
15:
t
t
t
(81)
max,
Ks
maxi.j
f.
||
Th maxi,j
(A
ij:
15:
Based on the sub-exponential Bernstein inequality and e-net argument,
( ZZifzi - ml
(A
S / mmn max 1.
( x
Vlog(V + /na max 1.3
(A
log(n V na)
x
1j:
1j: 1j:1F
(82)
holds with at least 1 - exp(-clogíf) v nz)) probability. Finally using the union bound and inequality (2). we can obtain the bound for Eg as
|الل] S CVn. (Vrms
max bg
A 1.
v Tog(n na) + Vng max 1.5
tdl (Ax)
log(n v ms))
|
15:
15:
34

---

ang
(A 1s: 1
$ =22m/
log(n ny) max 1s
m
12
2 /
may log 2 (n V nea)
130000
(ur))nong log (ng V o n²m
pro
* T Ai + (|
(40 260002mpp
prng log (n V ney 1 of
(pr) (ur)skone ng log (ns V n)omax
m
n²m
646C''
(ur) ny log (nz V n)Jmax nmm
uro
(pr) mw? ny log" V ns), p'
(ur)) my log (ng V n)o
<5200C moo00Cmmommnn mimin
n2m
(ur)2n2n nz log? (n V na)0
20mominm
(83)
mm
where (i) is due to 77) and triangle inequality. (ii) is because 779 and tensor incoherence condition 10).
The last two inequalities are due tube-wise sample complexity in (22
Finally, combining the bounds in
75
80 and with 70) would have
A ++1
+
R r+1
A 1+11
B
B
I
min
5
A T A' R
B T B R
(ur)3 log (n V na)omaa
20mo
nºm
(ur)2 log (n V na na)omax n2m
2Cmo
mijmin
520p''
(pr) ng log" (n ng)o
5
n²m
(ur)3 nı log" (n V n na)x
+ 0.08 520p'
n2m
(ur) log 2 na n
< 520 2tt
(84)
m2m
where the last inequality is due the p 0.01mmpmmin..
A.5
Proof of 144
This proof is combining
23
and
22
by triangle inequality. Thus. there decomposition as
(((
A B
AA" B*
A
AA"
R²
<
B
*
+
B
R. 1.1
B"
1::
(1
[A*
* *R
* R f.!
* RR.
B
B
B
13*
(85)
35

---

where
the last inequality
is due to tensor norm inequality
(92
For bound the
A
AA' Bddd
* R
R t.
we apply the Lemma 6 again as
B
AA' B
AA' B²
[4 13
X =
X =
RR, X₂ =
* *T
(86)
Based on tube-wiss wise sample complexity, there is
(ur) log (n V n3)ommxx
| Xoll
98Cp21
V
nm
2 (n V na) (ur)ak3 ny log
98Comin
min
(87)
2
where is due (3) and the last is due to tube-wist wise sample complexity. addition,
(ur)) ny log (n V n3 0 n2m
|| X2 | S
52Cp'
Vmax
(ur))nnng ng log 2 (n V nz) n2m
52Cominp
Omin
(88)
4
where (i) the first inequality is due to
(23
and the last is due to lube-wise sample complexity. Thus,
[((
[[[A7
A B
[A'
AA
A
A
[A"
R'
B
<
9x
1
R
B
T
B
R
B
1::
(ur) *x log" (n V ni m n m
< 468Cp'
(ur) ng log (n na ng)omax nmm
+ 2496C
(ur)5 log (n nz) na)o n2m
< 2964Cpp
(89)
A.6 Technical Lemmas
This section presents the technical lemmas used in proofs of Section A The first lemma is some important tensor norm inequalities under the t-SVD framework, which will be repeatedly used throughout the proof.
Lemma 1. For v E Rai XmgXna, y E X2x there are tensor norm inequalities as
|| X
n Dig X pm;
(90)
(i.;;,;;) < (1,;;)))
Vi E [m]]
(91)
max
| :::1l < | -
Σ
X (1,;,));
(92)
:E(n]]
| y01 < <|||| | 1| - vaall |
||
(93)
X )/ < ||||| ||||
(94)
(i,;,,) P(...)))
Wi [n]]. Vj [ri].
(95)
36

---

Remark 3. The relationship between the spectral norm and the Frobenius norm in the 1-SVD tensor algebra differs from the matrix case. For matrix X, one has
X|| S |
whereas in the tensor setting an extra factor of /na appears in (90). Similarly, the matrix inequality
|| S l
also acquires a factor of /na in 93 This vna factor is unavoidable in the general third-order tensor context. Interestingly, for horizontal slice tensor X :i.;.:) E IR 2g1xxxXns, the Frobenius norm bounded by its spectral norm, reversing the usual matrix inequality.
Proof. For the 90 we have
(6) | (x) S |[biirc (2))
x
VT3 |
(96)
where we use the definition of tensor spectral norm in (a), matrix norm inequality in (b). (c) due to the definition of the beire operator in (3) and equality (I02).
For 91
2
Σ
ng
X8 (1.::)))
max k((ns)
X
(k)
(x,
(97)
123
For (92
| | = |[bdiag
X
X (())
max
ke [ma]
22
(k)
max ke [ns]
X
n1
11:
max kE|mal
X (A))
max E kEins]
n1
S
Σ
X| (i, :))
(98)
where (d) uses matrix norm incquality that ||||| with only row, its spectral norm is equal to its Frobenius norm. (f) is due to the definition of the tensor spectral norm.
< X Ix. (c) is based on the fact that for matrix
For 93
1
X Vl1
XY
113
F
V Σ 1/3
X
(1)
(1)
k=1
F
Vn3
(k)
(k)
Y
X
(g)
k=
F
37

---

Σk=
n3
Y
k=
max ke[mal
X
Vng
|||||
II
||
(99)
(g) is based matrix norm inequality that
|| X
||
S
Y
|X||
(k) y (8) X
(8)
For 94)
|
3
max
maXke[mal
e
X
|
For 995
19 1 [D)(; & (t,;;) :::)).
it is directly result from
and
93
(1(;), (1:.;::))
(i,
The following lemma is the key lemma in our proof, which measures the concentration of the tube-wise sensing map Z Ruxnxns + Raxxxm of Definition [ the tensor spectral norm metric.
Lemma 2. For the defined tube-wise sensing operator 2. all entries in {Zij} obey i.i.d standard Gaussian distribution, then't 4 tensor A E RuxXxX3 F E IRaxxxna, the
[I - -- Fl < 2Cmr
log(n na) max | |
(100)
holds with high probability at least 1 [nVig] To
Proof. Due to the independence of each horizontal slice from Z, the core idea to bound each horizontal slice separately and utilize the union bound control concentration. Denote C :=
(mI- 2 3) ( F, then C.:: = Σÿ= Z Zi Aij mI) F(i;;;) E Ilxxx Based on
the variational formula of the matrix spectral norm, there
||C...I|
max (Ca:; wx?
wE .
(88)
((F ng
2 I1) (eire(C...) (FT) & ,,),
wE .26
Σ
Z Zis A -Ai.)) *F(ii;;)), beire* ((F & 11) wx (F Ir))
max we w
TERlxrxng
Zij A 19:1 Zij (Tx (F(FF:))))) m Aij T (F(j.::)))
max
WEe! .see j=1
m
T (FU)))))*) (iij T (F(),;;)))²)
max WEBL..EG
j=1
K₁a
(101)
(i) is due to the definition of the tensor spectral norm. (ii) is because the block circulant matrix in 3
can be block diagonalized, i.e.,
F na I (x)
Ing) X,
(102)
where F, is the Fourier matrix and X is the block diagonal of X
X
X
X
(103)
(na)
38

---

The set @ is defined as @ == 1² ns* The set B" denote the block sparse vectors, specially,
B = a R x = [=] ... . x J. where æ, B and there exists j such that J # 0 and m, for all # j. The s defined as S = f RR |||||| = 13.
Due to independence of { Vi E [n]] the Kjs are independent sub- exponential scalars with zero means and have bounded sub-exponential norm [| I Aillle T (F () > 0, there are
t2
t2
j==
2j=1
T (F(j,
F
max;j
FF Σソ=
|| T
(F()...:))7
ma
kj: |
1|
T F
IV
(2
m. maxaj A
Ajs 11
|T 1
|F 2
t2
(104)
mng max,;
||
11:
||
t
maxja
||
maxi;
A 13: max,
T * (F(J,;;:))
(120)
max.j
| F max, |F j::
(s0)
(105)
Mi maxij
A A || max, F j::ll
(i) and (iii) due to norm inequality in 93 (ii) and (iv) because ||
/ng. Thus, based
on the sub-exponential Bernstein's 's inequality and e-net argument, Vi E [n] there is
|F }):
P CI.C.: 2 1) < exp r Flognn emin
mns max., |
|
my maxij A max, (106)
The exp (r nt) is due to the covering number of for union set O x @ is O (exp ((r + 1) log na)).
Based the independence among Ca., Vi E [n] due to tube-wise sensing operator Z, there union bound
Σ ca:ll 2 ntt
P C[|C
2 t)
i=1
t2
I n exp (r log nz) exp
-cmin
ming maxig
A
ijz
F
2'
/na maxis
A Aig
max, (107)
|
Thus.
||l|| <
Σ 11.
< CVV. (Vmmer log(n n3) max A. ||F|| + vagr log(n V nz) max || Aii l max ||F F:all
39

---

nn3 log(n ny) max ||
222mr m
A 15:11 |F
|F
(108)
holds with probability least (nVng)io The first and last inequalities are due the tensor norm inequality (92).
Besides the above concentration inequality in the tensor spectral norm metric, we also need the following concentration inequality in the inner product metric, which would be used proving the
restricted strong convexity and smooth property of the non-convex loss landscape in (6)
Lemma 3. For the tube-wise sensing map Z Ruxxxns - RaxXXM in Definition
A.B,CC,DE
Baxrxns and the defined concentration distance
D ( (A* = - (A*ce) 3 (
(B+
m (A*C*, B++"""
(109)
there is
D (A**C", , BB D") s Vmllog(n V na),
Σ Σ Asi (c,z)) ||
B * (D)..)) )
1=1
I Vmng lon(n V ns) (11A41 max ||Cx:l) ^ (I[lIl max [[Cx:ll) || F | F
(110)
with probability at least 1 (DVng)10.
Proof.
D A BB=
Zis (Ai: * (()==)) Zi (B:: (D (D):)")
j=1
m (A:: * (Cz::² TT. .B::: * (D)=)²)
n
m
Ain * (Czz)²)
T Zijs
Bi. * (Dz:)²) (A * (Cj.." B.. * (D ju
Lijs
(111)
It is apparent that Pijs are independent sub-exponential variables with zero means and bounded sub-e sub-exponential norm 119c,elle I
A * (C,:))
B (D):)
Thus, there is
t
n1
A (C,.)"' 2
B (D (D,z)* (
2
-= j=1
m 1=1 Σラ=1
(112)
maXijs 1ggjollyy
maxi A (C,..)"
B (D):)
Based on the sub-cxponential Bernstein inequality, there is
|D (A* c², B * B'D")
m log(n V na)
A (C,x))
| B (D)
<
2
log(n V mz))
A * (C)
BB.. (D,t.)/
max
1F
2
$ V Vm lo V nz),
ΣΣ
A * (C,:))
Br: * (D):)² 71
(113)
40

---

holds with probability at least
Further, we have
(nvma)io
A.:: * (cx=) Ber. * (D):.) S max As: * (Czz)"
B (Djz) )
1=1 1=1
((Al) ||||| F max (C=:ll) a (I[C) max
max |Atilll)
1B:l 1111 j: p:
713
i=1 j=1
= =vng ((1A1), max (c:ll) (IeIl max A.:
max
| F
|
(114)
where the inequality due to norn inequalities
(93
The following lemma gives the property of alignment tensor R in which shares similar result in the matrix alignment setting 332
Lemma 4, For the minimization problem 11 the
(A'
RR) A" + (B" R²)) B
(115)
the symmetric positive semidefinite tensor and (A' R' - AA'²² A'' RR' R *B* Brxrxss is also symmetric tensor.
Proof. Solving
is equivalent to solving the following problem in the frequency domain as
A (1)
A
R
((
B+ (1)
Rd arg min REO,
A (na)) (mg)
A (na)
(ns)
R.
B (ns)
B
(116)
Due to the block diagonal structure, to find the orthogonal alignment tensor. We just need to find each orthogonal alignment matrix for each frontal slice in the Fourier domain
A (k)
(k)
(K) = arg min R
A
R
vk E [ma]]-
(117)
B (k)
(k)
REO.
B
Vk E [ngg]. the (17) is the matrix orthogonal Procrustes problem optimal alignment matrix
14
which concludes that the each
(p!tt)²
T
R
A'
(K)
T
A
(k)
B
T B
(k)
L
(k)
S.
(k)
P
)1)) T
(118)
where the second equation denotes the SVD decomposition of LHS. Also there is
(A (k)) T
A
R (k)
+
+B
B
(k)
7
B
R
A
R
(k)
+
B
(k)
R
(b) T
P.
S
(K)
T
(119)
Translating the above equation into the original domain, we obtain
(At)² (A' R²) (B*)² (B' RR) (A' R¹) A' + (B' R²) BB*
41

---

= P S
(120)
which is the symmetric positive semidefinite tensor.
(A' AA'R''AA1) A' + B' R
-B)
T B =B= (A' + R²) T A' (B' R²)
B
- -(AA')² A + (B')² B3"
(121)
where the RHS of the above equation the symmetric tensor due to 120
T The general result for
tensor is similar matrix that R' is the minimizer of (TT) iff that (A' R B is symmetric and positive semidefinite.
A IB' R
The next lemma gives the perturbation bound in the tensor spectral norm under the t-SVD algebra.
Lemma 5. Ler C E g be a nonsingular tensor, i.e., o, (C > O, Vi E [ma]] Then for any tensor& & [rrxxxa with ||E| S mmin (C), there is
ssgn(C + E) sgg((C)l S |
(122)
min (C) |
where sgn(X) == X * (X" x)
Proof.
[|sgn(C + + -sgn(C)] C (C') - -C E) ((C+ E) (C+
E
log
Mmin C)
F
Quin (C)
E
1
amin (C)
|1
(123)
0 min (C)
||
where (i) is based on Theorem 3.2 in [35 which is perturbation bound for the complex matrices. (ii) is based on logarithm inequality log(1 + z) 2 __ Vr > -1
To bound the distance between two tensors after transformation based on the corresponding orthogonal alignment tensor, we need the following lemma, which a generalized version of the matrix setting in (32 and based on Lemma 5
Lemma 6. Assume the tensors Xu. X1 E Raxrxns satisfying
oiin (X))
Piin (X))
|X - Xoll Xooll S
| X2 1121
(124)
4
Denote the alignment tensors as
R1 = arg min REO,
X * R X
R2 = arg min
12 * R - X'olF
(125)
REO,
Then there is
Tmax (2x)) 2
| * R1 X₂ R2ll <
|2' - X211
(126)
Tmiu (2'o)
This can be proved based the proof for the matrix setting in 32
Xx R, X2 R2
|| X2) R2 X (R1 RR))
42

---

11 - - + | ||
R1 R21
| 211 2oll R1 R2ll;
(127)
where the last inequality is due to the second condition in (24). Now we come to bound the distance between two alignment tensors. Based (25). vk E [13)]. there is
R arg min
k)
R X (k) X
(128)
REO,
R2 k)
arg min REO,
R Xo n
(129)
F
Denote the C = X N and C + E = X2 * Xo there is
0 (X
- X0 = | X
X S
(130)
- (x 2
which means that all T are
Based on Wely's ' incquality, we can know mii invertible. Thus, C is an invertible tensor. In addition,
E
T X2
S
X2
X1
X
= X1
X211||
min (X))
4
(131)
(k)
Thus, C + E is invertible and R
R2 have closed formulation
R (k) = ( ((at))
T
-
R₂ (M) = (c (c()+
+ +E")) ((t"h++"))
+ +E(h+ T
(T
+ {
-
(132)
Therefore, there is
R R2ll=
R R2
C T
(C''c)
- CC E) (CC E)" (C+E))
|IE|
m (C)
E
X X211 1
(133)
2in (x))
oini (2o)
where (i) is based on Lemma the last inequality with T31p. Substituting above inequality into
and EE|
omin (Xx)
Mmin (Xa)
amin (C), which also induce would have
2
127
2 xol
1 R₁ X2 Rell S 1|
X211+
|| X21l
e (Xa)
nu (Xx)
8
|2 - X22l
o² min (2(
9 max (X
2
|
X21l.
(134)
min (xx)
The following lemma provides the benign landscape of the non-convex problem (6) which has restricted strong convexity and smoothness properties in incoherent regions near the global optimum X The sample complexity in (12p is sufficient to guarantee the existence of this benign landscape, which can obtain the linear rate.
Lemma 7. With the same setting as Theorem
2 if the tube-wise sample complexity satisfies (2 then
Vec
A D
)
T
Mat (V²)(A,B)) Vec
D DB
2
Tmin
DA D
2
and [[A S 50
5
(135)
43

---

hold with probability at least 1- (nvmg)1 for V.A, B E Ruxxx that satisfy
1
( ( -B-V" v2
A 21
o max
max LE [m
5
(136)
500kv 2n
1::
and VD A. DB E R stay in set
A B
A2
A2 B2
42*
0 max
A [
Aa 1
R-
R
arg min REO.
R
2
1"
500k
FF
(137)
Proof. Based on ( there is definition A = A-4", AB = B - V and population level has expression as
[ D3]
[D DD )
(IDA*>>I*
E
Vec
Mat (V²)(A,B)) Vec
DTA + 4r D'S
_/2
D = D'g
vnll
A² DA+B. *DB| 1 + +W + W/
+
(138)
where the W1 + W2 has following bound
M + W/l < 9 [112 A2ll + || - B2ll) (1] + [[B21] + (1/21- - A2ll + | - -B211)2
(1) + || (112 + (| + (||Aاا - -| -(DDal/ + | (2))
(139)
Due to spectral norm inequality
92 there
A 40 B
2n
(
A U
B - V. ))
V"
B (( u 4.
v. ),
max 2n [m/2m]
max
(140)
500
[A B2
24"
Thus, based on
Jamax and above inequality, there 500
V*
Wi Wol < Omin
A
(141)
5
D
Next, we need to bound the difference between the population level and the empirical level by the following decomposition
[DA]] [DB
T
[D DD
T
)
Vec
Mat (V²S(A,B) Vec
E
Vec
Mat (V²](A,B)) Vec
DD
DD
= -2
2Z' =2(2"2
(A+BT -2 * (V.)7)
DA DT
2
(A
A BT
U2- (V*)T DA DT))
+ +| (DA+B* + D _
2
DA BT
A
D
2
II,
(142)
where II has decomposition as
I= 2D A (V*)², DA+ +2D (u'
A A D')))) +2D (A^
A DA D/b)
44

---

+2D (D** A DDB
+2D DA* B. D3B) +2D D A A D'B)
+D (DA* (V-) (VI(
+ 42' D. D
+2D D (V')² 14' * DiB)
+D D D A/3)
+D
A D A D3)) +2D DA * (V*('")* DA * A
+ 2D (4' DB
(143)
The concentration distance D (A c², B D") is defined in Lemma
Based on the Lemma 3
we can bound the conccentration level II as follows
I S log(n V ns) (2 [ max ( (A.) D [D + 124 11 max [1 k:: |
Th3
D F + ||l| max || B k: D [D + 2 m
max V
A F |
(144)
+ + max )::
+ 2
max [| k: A |
+ A max
V
|
FF
|D F + max U DD [4' || |D F
+2 | max
Vi.1
[24
||
DD |F + D max ||
[A :::ll |D F A
+ max
[I
H::ll
[D
P
|
|D F + |P max
| |P
AB|
+2 max
| T.
|| ||
| [DBllF)
(
S m/
n13 log(n V viaa
3 (3 1| max Aual + 3 maxx [1 || + ||
max
+2 max | | [1))
(IDDAl + PBB
(26)
m
13
log(n V nz)
3/v
promax
max
+3,
pro
Omax
+
v max
m
n
2m
71
500k
500k
Vmxx
+ 2
uromax
Vuv
urommxx
(IDAIl 11BBI
500kv2n
momia
(IDAI
(145)
5
where (i) is due to inequality 2 D D S
|D
1- (ii) is due to the tensor
[40) and tensor norm inequality ||*||| v Σー X 1
incoherence condition 10)..
136
2 s: < /n max; X 1= The last inequality is due to the tube-wise sample complexity
1
Lemma claims that the distance between two consecutive alignment tensors can be well bounded, which would be useful in proving (2). Lemma 8. With the same setting as the main Theorem then
2
2 2 m2 20 (V (wr) log?(e (n V na)o
(R!!) * I,
(146)
nm
holds with probability al least
3[nVng)
Proof. This proof follows the proof of Claim 11 in [8] and the proof of Lemma 12 in 32) which makes us use the proof idea for (3) and then utilize the tensor perturbation bound in Lemma Defining the auxiliary iterations (38
+11
A ++1
RL.
Z 1 B-1, (A B -ip,. (Ax)) B
45

---

A" ) ((44)) T A (B.1)² * *B" :R
mn
2
++,
RR -1 2--,,--1, (A%) A" A
-n (PL. (4%) )
B
B
A'
((Br.) (B
B'
(R!!)
B (Ath)) A' *R
(147)
2
Based on definition of R fi
in 21 we can conclude
(R..)
-1
* R 2l
arg min REO,
A 1 R B R
* RR
AA'
B'
(C E) ((C E)" (C + 8))
sgn(C + E)
(148)
where the (i) is due to (134) in
32
in frequency domain and 117) and
C = (At)² t+1,1
[B
(149)
a = 4411 R td A
1
A' + (BitLi * RRd
B B T
* B
(150)
To use the Lemma
5 we need to prove
A 1
A'
I, arg min REO,
* R
(151)
B ++1
B'
which is equivalent to sgn(C)
= I,.. Then we can use the Lemma as
( * R t I,
= =IssgnCC + + sgn(()]]
1+1,7 T
A * R -
A-"
B * R.
B ++,11
1"
A 1 T
++,1 T
[A- B
A
R
AA
mii
13 11
BT * R
B
B'
A 1
Ri
[+1,7
A'
13 +111
R
B ++1
B"
A 2 T
A
+1
* RRd
(+1,77
T
AA"
Omin
B 111
*
1
B * R
B
(+1.
B
(152)
To prove the (151
should prove that C is the symmetric positive definite tensor and bound
At111 R 1.
11,17
B +I
R
B
+111
Attli Rt. - - 1+177
We first bound the
Bt+1,1
* R 1i - B 1+1
as
4 * td
A 1+1,11
(- + 2i Zt. mPP.)
(A
A
B++ R
B 1+11
=
((-2'2 3 - -PPL.) (A
T
1.
B
11 * (R"1) * (A41)) A
* A4 - (B T
* BB'
* R t.
+ 7
2
I B
(R!1) T * (B²)) T
* BB - (At1)²
* A
* R
46

---

5 -- 2 2
21. mP,.)) (
A
m 2
| tul
2 أ
||41 2
1
A
+
|
Vuuryiinn log V na) na)o
< 2 x 1250 1250'mn p² Vonax
(153)
where the last two incqualities are due to the bounds for aı and d2 as follows.
For the d1, there is
13-2-m2 A + +
A (BulyT- - A (B
a1 S
21. ( |l)
|
(
2Cmr
11313
log (n V nz3)
max 8j
+ 2Cmr
n1 log(n na) max
(Ax)
+m
||ll||
[118*] + | +
A t./ ())
n1g3
(Hr)) ng log" (ng V n max
pr
4Cmr
log(n V na) 1300Cp"
(ur) log V na)o
+-3m 12k - 5520p0
max
(ur))nnn log?(1 (n V na m
-2k 112x-22C's
52Cp')
(v
(umn (uur))"nn ny nglog (n n nm
$ (1248C)²mpp Vo
(154)
where the (i) is due to concentration Lemma and (ii) are because (64) and 79). The last inequality due to the tube-wise sample complexity
For ag, there is
a2 5 /
4
| + A
(3) <
(ur))x² log (n V na ma)amax
( log (n 123)0max
p248Cp'1
//
2496C'p1
Vomax
7m
11772
(g log" (n ns) n maax nm
624C0'
+
1248 x 2500C2 2t Vomax (VL (ur)) log2 V ny) nz) 7 maax
(155)
nm
47

---

Next, we prove that C is symmetric positive definite tensor. The proof idea is similar to that of Section A.2.3 Based on the definition of (47). there is
C= (A*)*
A
t. * R (B²')
*B" r. * R 17 (AA) * +Zi (Ax) * *B'
yy (B²
3 L1
* A' - (At) * Pi. (A * BB' - 11 (B²)² * Pt. (A x * A
(156)
Based on definition of R. 1. in 21 and Lemma 4 the (A²)² A symmetric positive definite. Thus, C is also symmetric. In addition,
R. + +(B)²² BB R is
A B
A
A'
A'
A4
B
14
B
*
B*
<
B
1111
B
B*
E
A
1+1,1
A*
E
A
++117
AA
1
AA"
11111
11,1
1+
B'
E
B
B²
E
B
min,
(157)
where the last inequality uses the results in 158 and (160) as follows.
E
A
1+1
Bounding the
is similar to proof in Section A.2.1 as
11,11
++1
E 13
B
E A [+1,0
A
4+1,7
8-, 2-, A
B - -mP -1, (Ax) * B
*
E
B
14111
-
B
1+,
11
- 2 -1, (A
AA' m (P_L, A 1.! )
T
B
(6)
- 2n A'll (3 - In)
1.1 x
(1)
5 20
0maxlluijy
1113
log(n V n1a) max 6)
x
A.d وز:
F
(10)
$ 2C VCCVoman 10mxxmmn
n2333
log(n V ni))
mmax
<
1.1 ):::
max
|
m
+ max
|
(A
)::
max + max
1. k::
max
1.1
I1)
i::
(40)
nng
pro
< 2C / maaas
log(n V nz)
m
n
(ur)) log 2 (n V na ma)x
1938p'1
nmm
< 0.25 Vinaax
(158)
where the leave-one-out projection operator P P-i, is defined
KKiss kjts le k E [n]. A ==i,Vj [m]]
PP-i. i. (2))).g
(159)
Oms
(i) is because the spectral norm of the sub-tensor not larger than the original tensor. (ii) and (iii ) are due to the Lemma and tensor norm inequality (95), respectively. The (iv) is based on the tensor incoherence condition 110,, (64). and tube-wise complexity in 12p
48

---

IR
A
A
For the term
we can follow the (45 in Section A.2.2
(+1
I
B
B
E
1+1,0
A*
1+11
B
13*
In 2mmA' (At)²)
1
* A
II 27m (At)* AA'
+ mpm
2
B
2
I
21mmB" (B*)))
E2
AA' * (AA'T O
2
I. 21ym (At)²
A*
1.1
+
Inn
21pmm
B 1 7
A
(1
minomin)
a 1.1
4mpm
2
||41||
(1
0.9
A 1.1
0.25 max
(160)
where the last two inequalities are due tube-wise sample complexity.
Thus, based 157 and Wely's inequality, also conclude that min (C) 2 1.50 min which means that is positive definite tensor. Moreover, based on (153), we can bound the spectral norm of as
2
(ur)) ny log2 (n V na 03))
|E < 22 mmax 2 men 2² Vonax
nm
< 0.50mmin
(161)
where the last inequality is due to the tube-wise sample complexity and step size in Theorem 2 Thus, C,E satisfy the condition in Lemma 5 applying Lemma
(152) would have
2 1250 n² Va
( ns log (nVing Joass
(R::1) -1 RR I,
7112
v
maxx
1.50min 0.50min
(V [(ur) log (n V ns d
2 x 1250 12502mmn0 2
nmn
(162)
B Proof for Spectral Initialization
To use the same symmetric dilation technique for the matrix auxiliary tensor
1 8
40 in our setting, we construct the
0 Onxnnn
X
X
IR 2n 2
(163)
(X**)
O Onxny ns.
which is the symmetric tensor. This is because
x1)
X x. (1)
Onxn (x-11))
T
(164)
Onxn
49

---

is symmetric. wk = 2, ... ,...,, n3, n3, there is
x x2 (k) = [
Xx
x
Onxa
and X (ma
Onxn
(x-100st2-))))
T
(x-
O Onxn
nxn
(165)
Thus, there is
xx((1) T
x
(2)+2-k)
(166)
which obeys the definition of the symmetric tensor Definition the symmetric matrix and has tensor eigenvalue decomposition
3
Thus, each frontal slice of x²* is
U V
u
S
Onxuxna S
1
U
u
T
(167)
V2
-
O Onxnxns
V2
v
V2
Similarly, also define
O Onxxxxs
x
0 Oxxxxn (x001)
x
x² =
(20)²
and
x0, =
(168)
0 Onxxxns
0 Xxxxna
Then we have
| 221
Onxuxns
m 2 -- 2 -1, (X") + (x,
( = 3 -,, (X') +P,, x2))
Onxnxns
(169)
which is actually the sub-part of the 20 X In addition, based on the definition of 20 there is
x x
0 Onxnxns
2z x"
1 m
z'z(((")) x2.)"
0 OnxnXas
1 2 2x2((X) - x*
m
< x20r\
nn3
log (n V (3)) max
X
ij:
if
(
nng
uro
2Cr
log(n na)
m
(ur)*ng log2 (n V ng)n²
20
Omin
mn
1
40x2
mmin
Omia
(170)
4
where (i) is due the tensor norm inequality (95) and the tensor incoherence condition in 100
The
last inequality is due to the tube-wise sample complexity in (25). Thus, we also have
x - X
< 2 x-
Omin
<
(171)
4
Because v. 20 are symmetric tensor, if the top-r skinny of t-SVDs are
uº S (y")²² x"
td 50. (Vo1)² x
(172)
50

---

Then, the top-r T-eigenvalue decompositions [72 for x x0, are
v2
1
v
*
V2
1
4
and
v2 y
000 *
v2 you :
1 u T
(173)
respectively. Eq. 170)
means that the block diagonal formula, there is
X
miin
and
x
mmin
(174)
Based on Wely's inequality 61 and the above inequalities, there are
0 min S Trns ( S mmax (5
(175)
max
5
min S Orng (5 max (S
o max.
(176)
Recall the definition of A 2t (5")² 1 BB 200 (5 Vod, * (sa))
b A 2101 (80.1)
,
Define the tensor corresponding
1
4
AA'
g
(177)
V2
V*
V2
B
and H. 0
2 [o
1
A
H 0.1
1
70.1
1
A.
(178)
V2
V2
13
V2
Vod
V2
Further, the alignment tensors between these eigen- spaces are defined as
arg min
H R 9
(179)
REO,
0.1
arg min REO,
A R - 9
(180)
B.1
Proof of (66
[A00
AA* B*
* R
= V2 H R gll
= 22 H² (8 (R - 2²) + *H ((59) * - -" 20-2((('))
* (S*)
+ ( - - 9 * (S*)
<21|s"1
| R 0 + //
(8 3 o - - (**()))
1 | -"-
+
(1)
15v2
-
X
+ 15v2 2
K :
120-2"" x²-1
Omin
min
3v 20
x
X²
Jmin
(10
(ur) log2(n (n V 12 n2) max
201
Vonin
mn
22 m
Jmax
22
5
Omin
a min
anin
(ur) x ny log" (n ny mg)omax
< 98C
(181)
mn
where we use Lemma 10 and 12 in (i) and 170 in (ii.
51

---

B.2 Proof of (8
[401 1(
* RR 011
AA"
= v2 =v2
(7 * *R 01 -9),.. 1:1
B
2/
7
Qu 9)
v2 H// (R 01 -
- 1
//
0,5
(8
- Qu. X 9 (
+ V2
01
x 1:: *
H 0.1
((StM)
2 odh (8*)-
H 0,1
Qui
9 (5*) # )|
+ v2 2 R e41
v/
(sa)
- 2 (( $ -o ed (8)))) *(5)
H 0.1
ºº1 أ||
+
+ 22
max
| + (71 * Qo. - 9) r))..11) 01 Q
v Tmin
(1)
2 /2 max ||A
maxx
x0011 x 1
v Vmax
('V
15
30
Vo
min
+
3
x10 - x2-1
+ V2
IuTomax (1
+
(7 Q01 - 9) 11
2n
15
maax
20011
x.
T min
(6) 33x
201
(ur) log (n V na)n²
Omin + V2
(
uuromax
mn?
2n
+ (
a +0"- (0)
1)) (ur)nng log? (n V ng))5"
15
o
max
201
(n log" (n V ny)K?
min
mn
o
min
(1r) log" (n V ng ng)n55 mn?
< 66C
+
66C// 22
mn?
(ur)ng log" V ng)n²
pro
15
max B
20
2n
σ
min
mn
(6))
(n log 2 (n na ma) omax
(ur)5n3 log 2 (n V na) mmax
x 66C
+ 600
mn?
mn2
ng log 2 (n V na o maax mn=
< 126C
(182)
where (i) uses the Lemma 12 (ii) is due to 171 and (iii) due to the sample complexity bound in
25
52

---

B.3
Proof of (29)
Without loss of generality, we consider the case I [ni], the denote the alignment tensor
J 0,1 arg min
H 0,1
R H
(183)
REO.
Then based on definition of T there
1 * 7.
* R
= 2
7 0.1 T.t. - -71- * R
B
$ 22
H J - 77 R
(( (SOO)) 1 *Jol -J (5
$ //
H
+ V2
H 0.1
T
- -i(") * (5 H
(1)
15
max
x0. x00
v2.
50 max
H
0.1 gJo! -H²
min
(40) max
15v2
x011 x
+
50 max
2V2
[ xe4)
2
m
min
K
20,1 2001
< 26
V min
(11)
26
(L.
1 Bi, Zt, (X**
V 7inin
(v))
2C
n3 m
rlog(n V ns)) max ij
X|
Jmin
ngr log (n V ng)it
Jur n
52C
momin
(ur)a log 2 (n na na)omax
< 52C
(184)
n2m
where (i) is due to Lemma 12 and (175). (ii) is based on matrix version of Davis-Kahar SinO theorem
[9] and (iii) is based on definition of o 2 in (168). (iv) and (v) are due to our Lemma 2 and tensor incoherence condition in (10), respectively.
B.4 Proof of (27
Proof. Its proof is the same as proving
14 that VT E [2m], there is
A
AA"
0.17
A 0.17 1
[A"
R
R
0.1
R.
B
B
13*
l:
1::
AA"T
+[((
0
0.1
[A-]
9K
R
1
7
+
00.1
RR 0.1
1
(11)
(ur) na log" (n 12))mmxx
9x
520
n2m
(ur) logo(n (n na)x max mn2
+ 126C
(ur)3 log (n V ns maxx mn?
< /
(185)
53

---

We apply the Lemma in (i) as
A^' B
A 1
A B
11
* R
X2
T
(186)
The conditions || |
X ||
v Amin and |
X2
|
I Tmm can be satisfied based on
29
26) and tube-wise sample complexity in 25).
(ii) is due the result in (88 and 29
L
B.5
Technical lemmas
This section provides the necessary lemmas used in proving that spectral initialization satisfied the results in Theorem 4
These can obtained based on results of matrix setting in [3.
Lemma 9, (T-eigenvalue decomposition (72)) Any symmetric tensor X E IRxxxxnn (i.e., x X)
could decomposed into X = U * S * u", where E R=xXx" is orthogonal tensor and S E Ruxnxns is a I-diagonal tensor that diagonal entries of are T-eigenvalues X.
symmetric tensor with top-r T-eigenvalue decomposition as u Ut and ||X 11 S Amin and denote
Lemma 10. Let the X' E BRaxnxng
arg min REO,
11 R -
(187)
where X has T-eigenvalue decomposition as U2
S* (T
Then there is
u * é -u-1
2 X'1
(188)
m
Proof. The proof applies the result under the matrix case for each frontal slice of the tensor in the frequency domain. Based on (177) Yk [ma]
(b)
arg min
(
R-U
R
(189)
REC.
F²'
where ((h) U (k)
x(() X (1
Ce orthogonal matrices.
Since
Omin x-(11
based on Lemma 32 in 32. there Ak E [ma]
3
x-
(190)
o min X
which induces
(K)
U (1)
3
X (())
x-
max kE[ngl
minke[ngl mmin
X
(M)
kE[ngl
(191)
which is the conclusion of the lemma.
Lemma 11. Lel X' X' Raxaxns be symmetric tensors with top-r T-eigenvalue decomposi-
tion U S tt U2 S2 Uyy correspondingly. Assume for each frontal slice X X1 (x(1)) -xn
(8)
(k) > 0, A (X 0 and
1 min
(
Xx X2
5
(192)
40
Amax (X
Denote A₁ =1 S A2
S = =2 * S and define
i = arg min
11 + R 11ll
(193)
REO
Q = arg min
|1 * R Arllp
(194)
REO,
Then there is
Ô - o < Amax (Xx))
|| X211
(195)
min (x
54

---

Proof. The proof is similar to the proof in Lemma 10
Based on condition in 192 Ak E [mz]], there
x (k)
X2
(1)
min
(1)
min
(196)
40
Amax (x)
40
Amax
X
Combined with result in Lemma 34 in 32 we have
X
h)
Q
(k)
I
15
Amax
1
x
x
(8)
(197)
X
min
which induce
max EE [ms]
Q
(1)
Q
(k)
< 15
(2
max kE(ns]
X [c]
X (k)
(198)
min (x
which is exactly the result of the lemma.
Lemma 12. Lel X X2, X' E Baxuxns be symmetric tensors with top-r T-eigenvalue decom-
position U1 * S1 U U2 * S2 * Uh and U3 S3 * u2 correspondingly: Assume for each
frontal slice A1 (x
(1))
An(A (X) (X
An
(k)
0, 0 (8))
and 1| - xxll S
Aman (x) || X31 <
Amtn (X1) ( Denote
2 =
arg min REO.
U22 * R - Uzllr
(199)
Then
Amnax (2'2)
S 2 Q
S
S
|| X3
(200)
min 2
Proof.
The proof follows the idea in Lemma 10 and Lemma 11 and applies the Lemma 33 in to each frontal slice of Q 52 and S kk)
32
to obtain the final result based on definition of
Amaxx (X2), (min((1)) for third-ordee tensor.
55

---

C
Experiments on real world data
All experiments were conducted using MATLAB R2022a on Windows system equipped with
I 12th Gen Intel(R) Core(TM) 17-12700 CPU at 2.10 GHz and 16.0 GB of RAM.
30
35
20
30
PSNR
30
BANN
20
15
2000
4000
6000
8000
20
120
140
Iteration mimber
Frame
(a) PSNR vs. iteration
(b) PSNR for cach frame
Figure 3: Convergence and PSNR values for video sequence recovery.
(a) Ground truth
(b) m 20, r
(c) m 30, r =
Figure 4: Visual comparison 17th frame
We test the proposed local TCS model on the "highway" video sequence, which is reshaped into third-order tensor with size 144 x 150 x 176. 144, 150 denote the spatial dimension, and 176 denotes the tube size. When we compare with FGD (26) and Alt-PGD-Min [64] methods, both methods require large sample sizes that exceed our machine's ' memory capacity, making them infeasible to run in our setting. Because the video has full tubal rank and only approximately has a low tubal rank, we have no prior setting of the parameter in our model. Thus, we set 3 in our algorithm. For this r, we select the two tube- wuse-wise sample sizes as m 20, 30, which are much smaller than the tube size 176. For setting the step size 17. the video tensor has a large condition number which means the ground truth an ill-conditioned tensor. We have to select small step sizes (0.00005) to guarantee the convergence, which leads to slow convergence rates. We use the PSNR metric to evaluate the recovery performance and plot the PSNR vs. iteration number in Fig. 3(a) We also plot
1.1408 10%,
the PSNR values across video frames in Fig. 3(b)
The visual recovery results are shown in Fig. 4
We can observe that although our recovered tensor only has r 3, it has very small reconstruction error for the ground -tuth video sequence. This means that the original video sequence approximately has low tubal rank. Besides the video sequence, MRI medical images and hyperspectral images often exhibit a low tubal rank structure because spectral (wavelength), temporal (frame), or slice axes are highly redundant. Low tubal rank-based tensor methods are often effective for these tasks, as shown in existing works in 23 data, our low tubal rank Assumption
42
57
71 Thus, based on these experimental results on real-world realistic in practical applications.
We can observe that the GD converges slowly due to the very large condition number of the video tensor. This motivates on k to accelerate the convergence rate. Despite the slow convergence and the fact that the ground truth video tensor is not strictly low-tubal-rank, GD still achieves satisfactory recovery performance with small sample sizes. Moreover, as the sample size increases, the recovery quality improves accordingly.
use the preconditioning technique [22 64 to get rid of dependence
56


Reviews:
[{"review_id": "PU75bvMSzC", "reviewer": "Reviewer_58Bp", "summary": "This paper studies spectral-initialized factorized GD for tensor sensing problem under the so-called local measurement model, where each one-dimensional slice along the third axis $\\\\mathcal{X}(i, j, :)$ is measured by i.i.d. Gaussian matrices. Under a somewhat stronger coherence condition than the usual one, it is proved that factorized GD converges linearly when the number of measurements $\\\\gtrsim r^5  n_3 n$, where it is assumed $n=n_1=n_2$.", "questions": "Please refer to the Weaknesses part.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\nThe local measurement model is relatively new (built upon the idea of [58]). The overall approach appears rigorous, though I have not checked all the details in the proof.\n\n## Weaknesses\n- It is not clear whether the local measurement model is of significant practical relevance. It would be beneficial to discuss potential real-world applications. \n- It is not adequately addressed in the paper whether the local measurement model is simpler or harder to deal with than the more common models. Given the similarities of the proof to well-known proofs in the literature, the main technical contribution of the paper should be highlighted better.", "was_revised": true, "final_justification": "The author has addressed my concerns, and I will keep my positive recommendation.", "rebuttal": "Thank you for your detailed review and comments. We have addressed your concerns and respond to your questions below point by point.\n# Weakness 1:\n*It is not clear whether the local measurement model is of significant practical relevance. It would be beneficial to discuss potential real-world applications.*\n# Response:\nThe local measurement model is useful when each sensing operator can only  be applied to a small slice/tube/fiber of the ground truth tensor (e.g., one spatial line, one spectral vector, or one 2‑D slice). This is exactly how many real-world  systems are engineered, either because of hardware constraints (e.g., detectors read row by row, line by line, or slice by slice) or because the scene/object is physically scanned  piece by piece. For example, local sensing can be potentially used in the following two applications:\\\n**(1) Hyperspectral remote-sensing cameras (pushbroom / line-scan).** Pushbroom sensors on aircraft and satellites acquire one spatial line at a time while recording the full spectrum for that line, producing exactly tube-wise (line × wavelength) measurements. Industrial line-scan cameras similarly read a single row each clock cycle for high-speed inspection on conveyor belts.\\\n**(2)  Medical and biological volumetric imaging (slice/plane scanning).**  MRI / fMRI: 3‑D volumes are routinely built from multiple 2‑D slices acquired sequentially (multi-slice EPI, etc.), so each acquisition operator is confined to a slice. Practical CS-MRI implementations often undersample $k$-space slice by slice or frame by frame, exploiting local sampling patterns rather than a single global operator—exactly the scenario our theory targets.\n\nIn summary, due to hardware designs, many sensors cannot implement dense, global random projections; they naturally produce localized measurements (lines, slices, small patches). Additionally, for throughput and memory considerations, local readout enables devices to stream data with small buffers and parallel electronics, which are critical for high-resolution or high-speed systems.\n\n# Weakness 2:\n*It is not adequately addressed in the paper whether the local measurement model is simpler or harder to deal with than the more common models. Given the similarities of the proof to well-known proofs in the literature, the main technical contribution of the paper should be highlighted better.*\n# Response: \nThe local (tube‑wise) model is harder than standard global models, because we must show that with lower sample complexity it still admits exact recovery at a linear convergence rate—something we validate empirically in Figure 1 of main paper and Table 2 of Appendix.\n\nWe are agree with you that there are several well-known proofs in common TCS models such as convex nuclear norm, projected GD, alternating minimization, and nonconvex factor GD (FGD). Our method falls under the last category. However, \nstraightforwardly generalizing their techniques without exploiting the local tube-wise sensing model structure will not lead to the sample complexity provided in our paper. Detailed elaborations are given as follows:\\\n**(1)** For the global TCS model, existing proofs used a Bernstein inequality that is uniformly applicable to all rank $r$ matrices or tensors to prove the   Restricted Isometry Property (RIP) condition. If we use the same inequality, the sample size required to establish the RIP condition given in Proposition 1 would be much larger than our current result due to ignoring the structures of the tube-wise sensing model.\\\n**(2)** Prior works leverage global RIP (please refer to our response to Question 5 in second Reviewer UaeD ) to show the loss function satisfies the restricted strong convexity (RSC) and smoothness (RSM) property on a neighborhood of optimum and then prove linear convergence of GD using a spectral initializer. Our RIP, on the other hand, only holds for incoherent rank‑$r$ tensors, but not uniformly over all rank‑$r$ tensors. As such, to prove GD recovers $\\mathcal X^\\star$, we need to show all the iterates stay in a region that is smaller than existing works. To establish this result, we derived new tubal/t‑product norm inequalities (Appendix, Lemma 1), tube‑wise concentration bounds in Lemmas 2, 3, 7, and a proof for Eq. (23) in the Appendix; and combined them with a leave‑one‑out argument that decouples iterate–measurement dependence along tubes. To our knowledge, all these are new in TCS literature."}, {"review_id": "SZP0zpxHZ3", "reviewer": "Reviewer_UaeD", "summary": "The paper consider a tensor compressive sensing problem, with tube-wise linear measurements as defined in Definition 1, and under a low tubal rank assumption. They show that using gradient descent with a Burer-Monteiro factorization of the matrix is able to recover the original tensor and provide several theoretical guarantees.", "questions": "- Line 48: Tubal rank is yet to be defined. Here the authors should point to the definition of tubal rank (Definition 8).\n- Line 129: The definition of $\\mathcal{I}$ is inconsistent. The authors alternate between using $\\mathcal{I}$ and $\\mathcal{I}_n$. I think dropping the index and using $\\mathcal{I}$ is fine as it is clear its definition in the context.\n- Line 146: It should be made more clear at this time what the second term does in the loss does. In particular I believe it should be mentioned that the minima are the balanced factors defined in 162, up to an orthogonal transformation (which is referred in equation (11)).\n- The norm in (10) is for a matrix, yet the authors refer to a tensor norm.\n- In section 4, let us suppose that another random model for $\\mathcal{Z}$ also possesses an RIP condition. Would that imply the results obtained also hold for that random model?\n- The authors consider the $t$-rank of a tensor, which is the $M$-rank of a tensor when $M$ is the DFT matrix. Would the results obtained hold for other $M$-products?", "limitations": "The authors address the limitations adequately.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The topic of the paper is quite interesting. Although the applications of the paper are limited, as the model considered by the authors seldom arises in applications, the mathematical analysis behind the results makes up for that.  They provide a very complete analysis of the algorithm, under random settings, and obtain results in line with other lines of work. Moreover, they obtain an interesting dependence between sample complexity and the dimensions of the tensor $(O(r^5 n_3/\\min(n_1, n_2))$, where the tensor is $n_1\\times n_2 \\times n_3$.", "was_revised": true, "final_justification": "The authors addressed all my questions and concerns. I recommend acceptance.", "rebuttal": "Thank you for your detailed review and comments. We have addressed your concerns and respond to your questions below point by point.\n# Question 1:\n*Line 48: Tubal rank is yet to be defined. Here the authors should point to the definition of tubal rank (Definition 8).*\n# Response:\nThank you for pointing this out. We will revise accordingly.\n# Question 2:\n*Line 129: The definition of $\\mathcal I$ is inconsistent. The authors alternate between using $\\mathcal I$ \n and $\\mathcal I_n$. I think dropping the index and using \n it is fine as it is clear its definition in the context.*\n# Response:\nThank you for pointing out this notational inconsistency. We will drop the index and unify the notation by using $\\mathcal I$ throughout the paper.\n# Question 3:\n*Line 146: It should be made more clear at this time what the second term does in the loss does. In particular I believe it should be mentioned that the minima are the balanced factors defined in 162, up to an orthogonal transformation (which is referred in equation (11)).*\n# Response:\nThank you for your professional comment. The second term in line 146 is to balance the norms of factor $\\mathcal A$ and factor $\\mathcal B$. To see this, if there is no second term, then the loss in line 146 becomes $\\mathcal L\\left( \\mathcal A, \\mathcal B \\right):= \\sum_{i=1}^{n_1}\\sum_{j=1}^{n_2}  ||  Z_{ij} \\left(\\mathcal A(i,:,:) * \\left(  \\mathcal B(j,:,:) \\right)^T \\right) -  y_{ij} ||^2_F$, which has identifiability issue since for any invertible $\\mathcal R \\in \\mathbb R^{r\\times r \\times n_3}$, factors $(\\mathcal A,\\mathcal B)$ and  $(\\mathcal A*\\mathcal R^{-1},\\mathcal B*\\mathcal R^T)$ has the same loss value. Such ambiguity may result in the norms of the two factors being highly unbalanced, leading to divergence in  the algorithm. The second term is added to penalize such an imbalance.\n\nIndeed, we agree with your comment and will add this discussion in the revision.\n# Question 4:\n*The norm in (10) is for a matrix, yet the authors refer to a tensor norm.*\n# Response: \nThank you for pointing this out. In Eq. (10), $\\mathcal U^\\star(i,:,:) \\in \\mathbb R^{1\\times r \\times n_3}$ is a degenerate third‐order tensor. Although it can be viewed as an $r \\times n_3$  matrix, the norm here indeed stands for the tensor spectral norm. We will clarify this in the revision.\n# Question 5:\n*In section 4, let us suppose that another random model also possesses an RIP condition. Would that imply the results obtained also hold for that random model?*\n# Response: \nThank you for the insightful question. If an alternative random model also satisfies the RIP condition in Eq. (17), we anticipate that our analysis can be generalized. However, we would like to note that the major technical challenge actually lies in proving the  RIP condition. One of the difficulties is to find the structural assumption on $\\mathcal{X}$ so as to obtain a tight sample complexity.   For tube-wise TCS, our RIP is proved to hold over the set of all low rank tensors satisfying an incoherence condition as stated in Assumption 2. Such a set often depends on the sensing model and needs a case-by-case study.\nFor example, if one  aims to prove the  RIP that is used in global TCS analysis: the sensing map $\\boldsymbol{\\mathcal A}: \\mathbb R^{n\\times n\\times n_3} \\rightarrow \\mathbb R^m$ in global TCS model satisfies T-RIP condition with parameter $\\delta$, if it has $ (1-\\delta)||\\mathcal X ||_F^2 \\leq ||\\boldsymbol{\\mathcal A}({\\mathcal X})||_F^2\\leq (1+\\delta) ||{\\mathcal X} ||_F^2$ for $\\forall {\\mathcal X} \\in \\mathbb R^{n\\times n\\times n_3}$ with tubal-rank of at\nmost $r$ (cf. Definition 2.12 in [22] ), then higher sample complexity would be needed with samples taken by our local TCS model. \n Moreover, our main  result presented in Theorem 2 shows that the GD algorithm provably recovers $\\mathcal{X}^\\star$. To this end, we must prove that all the iterates satisfy the incoherence condition, and thus RIP holds along the trajectory of the algorithm. This is another main technical challenge and cannot be assumed a priori. \n\nIn summary, RIP alone is insufficient. To inherit our results, a new model must (a) achieve the same‑order sample complexity for the desired RIP and (b) provide a mechanism  ensuring the iterates stay within the region where that RIP holds. Our high-level of proof may be generalized, but verifying these two ingredients requires a dedicated analysis for specific sensing model.\n# Question 6:\n*The authors consider the t-rank of a tensor, which is the M-rank of a tensor when M is the DFT matrix. Would the results obtained hold for other M-products?*\n# Response:\nThank you for the question. Our analysis extends to any transform matrix satisfying $M^TM = MM^T = n_3I$, a property enjoyed by the DFT matrix. This condition is standard in the transformed t‑SVD framework [1-3]. Thus, our results still hold for such $M$-products.\n\n# Reference\n[1] Lin Chen, Li Ge, Xue Jiang, Hongbin Li, and Martin Haardt. Slim is better: Transform-based tensor robust principal component analysis. **IEEE Transactions on Signal Processing**, 2025.\\\n[2] Canyi Lu. Transforms based tensor robust pca: Corrupted low-rank tensors recovery via convex optimization. In Proceedings of the **IEEE/CVF International Conference on Computer Vision**,270 pages 1145–1152, 2021.\\\n[3] Canyi Lu, Peng Xi, and Wei Yunchao. Low-rank tensor completion with a new tensor nuclear norm induced by invertible linear transforms. In **IEEE International Conference on Computer Vision and Pattern Recognition (CVPR)**, 2019."}, {"review_id": "m5tNpvYQSa", "reviewer": "Reviewer_sxUs", "summary": "This manuscript propose a new tensor compressed sensing (TCS) model with local tube-wise strategy. The method works by minimizing a nonconvex objective via Burer-Monteiro factorization. Besides, the authors prove that this method achieves exact recovery with a linear convergence rate.", "questions": "1. The slice-wise method, i.e., Alt-PGD-Min, and the proposed method are both local TCS models. What are the advantages of the tube-wise method compared with the slice-wise approach?\n\n2. This paper provides tube-wise sample complexity. However, the experiments do not involve a comparison of the sample complexity with other methods. How can the effectiveness of the proposed tube-wise sample complexity be sufficiently verified?\n\n3. There was no comparison with other benchmark methods in the experiments. Moreover, the effectiveness of the proposed method in practical application scenarios remains to be verified.\n\n4. The author claims that tube-wise is more flexible. How is this flexibility demonstrated and supported in the paper?\n\n5. Some typos exist, e.g., “GD” in abstract and several definitions lack references.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This paper introduces a local tube-wise method under the tensor product framework. The corresponding detailed definitions and theory are provided. Additionally, experiments analyze about convergence, initialization, and sample complexity.\n\nHowever, this paper lacks sufficient experiments to demonstrate the contributions of this work. More comparative methods need to be added. Furthermore, the motivation from slice-wise to tube-wise requires further description.", "was_revised": true, "final_justification": "After reading the rebuttal, I am satisfied with the new experiments, so I decide to raise my score.", "rebuttal": "Thank you for your professional comments. We appreciate the opportunity to address your concerns here point by point.\n# Weakness 1:\n*However, this paper lacks sufficient experiments to demonstrate the contributions of this work. More comparative methods need to be added.*\n# Response:\nDue to page limits, we have placed a part of  experimental results in Appendix C (please refer to **pp. 54–55 in Appendix.pdf**), which may be easy to miss. Comparison  with the global TCS method FGD [23] and the latest slice\nwise TCS method Alt-PGD-Min [52] on both synthetic and real-world data have been provided therein. \n\nIn addition, during the rebuttal period, we ran additional experiments that include new comparisons with two global TCS methods: the non‑convex **Schatten‑$2/3$ TNN** [17] and the convex **TNN** [23]. We report results for $n=20$ and $n=50$ only, as both  of them encounter out-of-memory issues for larger $n$ due to the large sample size. The comparison results are summarized in the following table.\n\n# Table 3: \n Comparison of runtime and the required number of measurements $m$ to achieve the same level of relative recovery error in tensor compressive sensing (TCS). (**m** is the sample size in tensor unit, **n₃**  is the tube size, **n** is the spatial dimension, **r** is the tubal rank ).\n\n| **n₃(r)**  | **n** | **FGD  (m / time)** | **TNN (m / time)** | **Schatten-2/3 TNN (m / time)** | **Alt-PGD-Min  (m / time)** | **Ours (m / time)** |\n|:---------------:|:-----:|:------------------:|:------------------:|:-------------------------------:|:--------------------------:|:-------------------:|\n| **10 (r=2)**    | 20    | 840 / 7.1          | 1450 / 1.6        | 1020 / 5.1                    | 43 / 13.8                  | 3 / 1.1             |\n| **10 (r=2)**    | 50    | 2200 / 175.7       | 4600 / 109.4       | 3100 / 181.7                    | 45 / 15.6                  | 2 / 3.7             |\n| **20 (r=3)**    | 20    | 2400 / 86.9        | 3950 / 7.7         | 2750 / 20.7                    | 130 / 13.8                 | 7 / 4.5             |\n| **20 (r=3)**    | 50    | 6800 / 442.4       | 13000 / 717.5      | 8500 / 988.2                    | 135 / 80.4                 | 3 / 11.6            |\n| **30 (r=4)**    | 20    | 4900 / 181.2       | 7100 / 20.9       | 5250 / 90.0                     | 250 / 47.3                 | 12 / 16.1           |\n| **30 (r=4)**    | 50    | 13500 / 1626.1     | 24000 / 2395.6     | 16500 / 2344.9                  | 268 / 155.9                | 6 / 18.9            |\n\nIt can be observed that our method attains the same relative recovery error $\\frac{|| \\hat{\\boldsymbol{\\mathcal X}^\\star}- \\boldsymbol{\\mathcal X}^\\star||_F}{|| \\boldsymbol{\\mathcal X}^\\star ||_F}$ with the **minimum** sample complexity  and runtime.\n\n# Weakness 2:\n*Furthermore, the motivation from slice-wise to tube-wise requires further description.*\n# Response:\nThanks for your helpful suggestions. In line 25-51 of the main paper, we have provided a short paragraph motivating why local sensing is of interest.  For a more detailed motivation of using local measurement model from an application perspective, please see our response to first Reviewer 58Bp's first question. In what follows, we provide a detailed elaboration why we move from slice-wise to tube-wise sensing within the local TCS framework:\\\n**(1) Practical Applications.** There are applications where tube‑wise access is natural or mandatory. This is because some real‑world systems provide access to one tube of the tensor at a time, rather than an entire slice. For example, pushbroom (line scan) hyperspectral imagers used on aircraft, satellites or in conveyor belt inspections acquire one spatial line per exposure but capture the full spectrum of that line. Until the scan completes, one never have a full spectral slice (all pixels at a single wavelength) in memory; however, each pixel’s spectrum (a tube) is instantly available. Any algorithm requiring complete slices cannot run online, whereas a tube-wise method can. Similarly, rolling‑readout video sensors (e.g. CMOS cameras) stream raster lines one after another. In low‑latency or high‑speed settings, you see each pixel’s temporal tube well before you have a clean, full frame. A tube wise approach lets one process data as it arrives, supporting true streaming recovery with only small buffers.\\\n**(2) Motivated from Existing Work in [52].** Latest work [52] proposed slice-wise local TCS model that provably recover the ground truth tensor  of low tubal rank with a lower sample complexity than the global TCS model. We are interested in whether an even finer‑grained local TCS model—tube‑wise sensing—can further reduce the sample complexity. This  motivates our shift from slice‑wise to tube‑wise setting.\\\n**(3) Sample and Computational Efficiency.**  Theoretically, we show that tube‑wise sensing achieves  lower sample complexity than existing tensor compressed sensing (TCS) models, including slice‑wise sensing. Specifically, in Table 1 of the main paper, to exactly recover an $n\\times n\\times n_{3}$ tensor of low tubal rank $r$, the slice‑wise model of [52] requires $\\mathcal O(r^2n_3)$ samples, whereas our tube‑wise model needs only $\\mathcal O(r^5n_3/n)$.\nEmpirically, the results in the above **Table 3** in our response to your Weakness 1 validate that the tube‑wise model outperforms the slice‑wise approach in both sample complexity and runtime.\n\n# Question 1:\n*The slice-wise method, i.e., Alt-PGD-Min, and the proposed method are both local TCS models. What are the advantages of the tube-wise method compared with the slice-wise approach?*\n# Response:\nThank you for the question. As stated in point (3) of our reply to your Weakness 2 , tube-wise is more efficient than slice-wise sensing in both sample complexity and computational cost, which is validated by both theory and experiments in **Table 3** above. We also note that the two approaches address different scenarios, with the tube-wise and slice-wise sensing applying, respectively, to applications where measurements are taken with respect to a tube and a slice of the ground truth tensor. \n# Question 2:\n*This paper provides tube-wise sample complexity. However, the experiments do not involve a comparison of the sample complexity with other methods. How can the effectiveness of the proposed tube-wise sample complexity be sufficiently verified?*\n# Response:\nThank you for insight comments. The  theoretical comparison of sample complexities has been provided in **Table 1 of main paper**. Experimental validation of our method’s sample efficiency has been provided in **Table 2 (Appendix C.pdf)** and the **Table 3** in our reply to your Weakness 1. In all settings, our tube‑wise model achieves exact recovery with the **minimum** sample complexity and runtime.\n# Question 3:\n*There was no comparison with other benchmark methods in the experiments. Moreover, the effectiveness of the proposed method in practical application scenarios remains to be verified.*\n# Response:\nSome of our experimental results are provided in the **Appendix.pdf** due to the page limit. Specifically,\\\n(1) Comparison with FGD and Alt‑PGD‑Min has been provided in **Appendix C.1**. To make the evaluation more comprehensive,  we have added  two extra benchmarks: nonconvex Schatten‑$2/3$ TNN [2] and convex TNN [7]. The result is shown in the above **Table 3**.\\\n(2) To show its effectiveness on practical applications, we have tested it on a video‑recovery problem in **Appendix C.2**. Here, we have not compared with the benchmark methods because they require a large number of measurements for recovery, which leads to memory and computational costs exceeding our computational resources at hand.\n# Question 4: \n*The author claims that tube-wise is more flexible. How is this flexibility demonstrated and supported in the paper?*\n# Response:\nThank you for your insightful question. For applications where one can design the sensing tensor, tube‑wise method is more flexible because:\\\n**(1)** Tube‑wise sensing only requires access to individual tubes (mode‑3 fiber vectors) of the tensor, whereas slice‑wise and global sensing methods must measure the entire frontal slices (full matrices) and the whole tensor, respectively. \\\n**(2)** Given samples obtained via the tube-wise TCS model in Definition 1, we can  turn it into an equivalent slice-wise or global TCS model, but not the other way around. We take the slice-wise model as an example to elaborate. Let $\\mathcal X \\in \\mathbb R^{n\\times n \\times n_3}$ be the tensor to be measured and $\\mathcal X(:,j,:)$ be its $j$-th lateral slice composed of $n$ tubes, namely, $\\mathcal X(i,j,:)$ for $i=1,\\cdots,n$. In tube-wise TCS, the $m$-th measurement of tube $\\mathcal X(i,j,:)$ is $\\mathcal Y(i,j,m)=\\mathcal Z^{ij}(m,:)\\mathcal X (i,j,:)$, where $\\mathcal Z^{ij}(m,:)$ is the $m$-th sensing vector for tube $\\mathcal X(i,j,:)$. \nSumming up these measurements over $i$ (all the tubes belonging to the $j$-th slice)  as $ \\hat{\\mathcal Y}(j,m): = \\sum_{i=1}^n \\mathcal Y(i,j,m)$ gives the $m$-th measurement for $j$-th slice in the slice-wise TCS model: $\\hat{\\mathcal Y}(j,m) = \\langle\\hat {\\mathcal Z}^{j,m},\\mathcal X(:,j,:)\\rangle$, where the sensing matrix $\\hat{\\mathcal{Z}}^{j,m}$ is formed by taking each $\\mathcal{Z}^{ij}(m,:)$ as its $i$‑th column. On the other hand, a slice‑wise model cannot be converted into a tube‑wise one because its measurements mix information across the tubes. \\\n**(3)** In terms of implementation cost, tube‑wise TCS needs fewer measurements and incurs less memory cost than slice‑wise methods. Therefore, the method can be more flexibly applied to real-world applications under resource constrains such as computing power.\n# Question 5:\n*Some typos exist, e.g., “GD” in abstract and several definitions lack references.*\n# Response: \nThank you for catching these. \"GD\" is short for \"gradient descent\" and we will fixed these typos in the revision."}, {"review_id": "2LGJwAQRtr", "reviewer": "Reviewer_TA7y", "summary": "In conventional Tensor Compressed Sensing (TCS), the sensing operator $A_k$ acts on the entire tensor $X$, which has several drawbacks: (1) it is not scalable for large-scale data, (2) it is not suitable when the data size is variable, and (3) block-wise $Ak$ is preferable for privacy-preserving applications. To address these issues, slice-wise TCS approaches have been proposed. Inspired by existing slice-wise methods, the authors develop a tube-wise TCS method.", "questions": "### Suggestions:\n\nI hope the following suggestions help improve the clarity and readability of the paper:\n\n- [**S1**] Please explicitly state the dimension of the vector y in Equation (6). While I understood that y_ij corresponds to y(i,j,:) as defined in Definition 1, it took time for me to understand it.\n\n- [**S2**] Consider describing the tensor size of R in Equation (11). Where is the set O_R defined?\n\n- [**S3**] The notation for truncated SVD is inconsistent: it appears as “t-SVD” (Line 137) and “T-SVD” (Algorithm 2). Please unify this notation throughout the paper.\n\n- [**S4**]  Please explain the meaning of the check symbol and the variable “r” (tubal-rank) in the caption of Table 1.\n\n- [**S5**] At first glance, Equations (6) and (7) give the impression that the gradient is independent of y, which feels a bit odd. Of course, I understand that X itself depends on y, but I think it would be helpful to explicitly mention this dependency in the paragraph for clarity.", "limitations": "yes (but please fill in the justification in the checklist)", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n- [**S1**] Despite the non-convex nature of the problem, the authors provide a theoretical guarantee that their proposed method can recover an exact low-rank tensor $X$ at a linear rate under the following conditions:\n  - A sufficient number of measurements are available.\n  - Each frontal slice of X has a very small rank.\n  - X satisfies an incoherence condition.\n  - The algorithm is initialized by spectral initialization.\n\n- [**S2**] The sample complexity is shown to be proportional to 1/n, which is a favorable result.\n\n- [**S3**] The introduction clearly motivates the problem by highlighting limitations in existing methods and proposing a justified new approach. The authors clearly explain the differences from prior work and the novelty of their own method, positioning their research well within the existing literature. The writing is easy to follow.\n\nOverall, the paper is well-written, and these strengths suggest the paper makes a strong contribution to the community.\n\n### Weaknesses:\n\nThe following are minor concerns, and I do not consider them grounds for rejection, provided the authors make slight revisions.\n\n-  [**W1**] Although the method assumes a small tubal rank and the sample complexity is proportional to r^5, real-world datasets in the ML community often do not guarantee such low ranks. The authors assume rank-5 tensors in their experiments. It would be helpful to illustrate practical use cases where such an assumption is realistic and beneficial.\n\n- [**W2**] The paper focuses only on third-order tensors. While I am not sure if this may be standard in signal processing, tensors of arbitrary order are frequently discussed in the ML community, such as tensor networks. I recommend that the authors either justify their focus on third-order tensors or discuss how their approach could be generalized for arbitrary order as future work.\n\n- [**W3**] To avoid misunderstanding, Assumptions 1 and 2 should be more clearly explained in the introduction. The authors claim: “We prove that despite being nonconvex, with a sufficient amount of measurements, applying gradient descent with proper spectral initialization finds the ground truth X at a linear rate.” However, this result holds under the additional assumptions that each frontal slice has a sufficiently small rank (assumption 1) and the tensor satisfies the incoherence condition (assumption 2) . These assumptions are currently not clearly described in the abstract or introduction.\n\n- [**W4**] In the checklist, the authors do not include a justification for their claims. While this is likely acceptable given the theoretical nature of the paper (with clear assumptions, proofs, and also source code), please ensure this section is properly filled in the camera-ready version.", "was_revised": true, "final_justification": "I did not identify any major weaknesses in this submission. In their rebuttal, the authors promised to improve the clarity of the paper, particularly by explicitly stating the assumptions of the main theorem, which I consider important. Given that my original score was already positive, I will keep it unchanged. I remain supportive of accepting this paper.", "rebuttal": "Thank you for your detailed review and professional comments. We have addressed your concerns and respond to your questions below point by point.\n# [W1]:\n*Although the method assumes a small tubal rank and the sample complexity is proportional to r^5, real-world datasets in the ML community often do not guarantee such low ranks. The authors assume rank-5 tensors in their experiments. It would be helpful to illustrate practical use cases where such an assumption is realistic and beneficial.*\n# Response:\nThank you for your useful question. We have provided a real-world video recovery experiment in  our **Appendix C.2**, where we use $r=3$ to obtain the high recovery accuracy as shown in Fig. (3) and Fig. (4) of Appendix C.2. Although our recovered tensor only has $r=3$, it has a very small reconstruction error for the ground-truth video sequence. This means that the original video sequence approximately has a low tubal rank. Besides the video sequence,  MRI medical images and hyperspectral images often exhibit a low tubal rank structure because spectral (wavelength), temporal (frame), or slice axes are highly redundant. \nLow tubal rank-based tensor methods are often effective for these tasks, as shown in existing works in [1-8]. Thus, this assumption is realistic in practical applications. \n# [W2]:\n*The paper focuses only on third-order tensors. While I am not sure if this may be standard in signal processing, tensors of arbitrary order are frequently discussed in the ML community, such as tensor networks. I recommend that the authors either justify their focus on third-order tensors or discuss how their approach could be generalized for arbitrary order as future work.*\n# Response:\nThank you for insight suggestion. We agree that higher‑order tensors play a vital role in many ML applications. Here we focus on third‑order tensors because 3‑way data are prevalent in many applications—e.g., video (height $\\times $ width $\\times$ time), hyperspectral imagery (row $\\times $ column $\\times $ wavelength), and dynamic MRI (x$\\times $y $\\times $ time). The mathematical properties of t‑product/t‑SVD and tubal‑rank are relatively more mature for third‑order arrays than higher order ones, which allows us to  build our work on these recent results in [52].\n\nA potential direction to extend our local TCS model to arbitrary‑order tensors could be leveraging the recently developed high‑order tensor algebra framework in [9-11]. This will allow us to generalize our low‑rank, incoherence assumptions and the leave‑one‑out proof techniques to develop a general local TCS model for tensors of any order.\n# [W3]:\n*To avoid misunderstanding, Assumptions 1 and 2 should be more clearly explained in the introduction. The authors claim: “We prove that despite being nonconvex, with a sufficient amount of measurements, applying gradient descent with proper spectral initialization finds the ground truth X at a linear rate.” However, this result holds under the additional assumptions that each frontal slice has a sufficiently small rank (assumption 1) and the tensor satisfies the incoherence condition (assumption 2) . These assumptions are currently not clearly described in the abstract or introduction.*\n# Response:\nThank you for the suggestion. We will explicitly mention these conditions in the abstract and introduction in the revision.\n# [W4]:\n*In the checklist, the authors do not include a justification for their claims. While this is likely acceptable given the theoretical nature of the paper (with clear assumptions, proofs, and also source code), please ensure this section is properly filled in the camera-ready version.*\n#  Response:\n Thank you for the notification. We will fix this in the revision.\n# [S1]:\n*Please explicitly state the dimension of the vector y in Equation (6). While I understood that y_ij corresponds to y(i,j,:) as defined in Definition 1, it took time for me to understand it.*\n# Response:\nThank you for pointing this out.  In the revision, we will clarify that $y \\in \\mathbb R^m$, where $m$ is the number of measurements.\n# [S2]:\n*Consider describing the tensor size of R in Equation (11). Where is the set O_R defined?*\n# Response: \nThank you for noting this omission. The set ${\\mathcal O}_r$ includes all orthogonal tensors with size $r\\times r \\times n_3$. Thus. the tensor size of $\\mathcal R$ in Eq. (11) is $r\\times r \\times n_3$.\n# [S3]:\n*The notation for truncated SVD is inconsistent: it appears as “t-SVD” (Line 137) and “T-SVD” (Algorithm 2). Please unify this notation throughout the paper.*\n# Response: \nThank you for highlighting this inconsistency. We will standardize the notation to “T‑SVD” throughout the manuscript.\n# [S4]:\n*Please explain the meaning of the check symbol and the variable “r” (tubal-rank) in the caption of Table 1.*\n# Response: \nThank you for your careful observation. We will add the explanations in the revision.\n# [S5]:\n*At first glance, Equations (6) and (7) give the impression that the gradient is independent of y, which feels a bit odd. Of course, I understand that X itself depends on y, but I think it would be helpful to explicitly mention this dependency in the paragraph for clarity.*\n# Response: \nThank you for this helpful suggestion. We have substituted the expression of measurement $\\mathcal Y$ defined in Eq. (2) into the loss function Eq. (6), which gives the gradient in Eq. (7) and Eq. (8). We will add this explanation to avoid confusion.\n\n# Reference\n[1] Chunyan Liu, Sui Li, Dianlin Hu, Jianjun Wang, Wenjin Qin, Chen Liu, and Peng Zhang. Nonlocal tensor decomposition with joint low rankness and smoothness for spectral ct image reconstruction. **IEEE Transactions on Computational Imaging**, 10:613–627, 2024.263.\\\n[2] Wei Pu, Junjie Wu, Yulin Huang, and Jianyu Yang. Ortp: A video sar imaging algorithm based on low-tubal-rank tensor recovery. **IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing**, 15:1293–1308, 2021.\\\n[3] Andong Wang, Chao Li, Mingyuan Bai, Zhong Jin, Guoxu Zhou, and Qibin Zhao. Transformed low-rank parameterization can help robust generalization for tensor neural networks. **Advances in Neural Information Processing Systems**, 36:3032–3082, 2023.\\\n[4] Andong Wang, Yuning Qiu, Mingyuan Bai, Zhong Jin, Guoxu Zhou, and Qibin Zhao. Generalized tensor decomposition for understanding multi-output regression under combinatorial shifts. **Advances in Neural Information Processing Systems**, 37:47559–47635, 2024.\\\n[5] Andong Wang, Yuning Qiu, Zhong Jin, Guoxu Zhou, and Qibin Zhao. Low-rank tensor transitions (lort) for transferable tensor regression. In **Forty-second International Conference on Machine Learning**.292\\\n[6] Zemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, and Misha Kilmer. Novel methods for multilinear data completion and de-noising based on tensor-svd. In Proceedings of the **IEEE conference on computer vision and pattern recognition**, pages 3842–3849, 2014\\\n[7] Xi-Le Zhao, Hao Zhang, Tai-Xiang Jiang, Michael K Ng, and Xiong-Jun Zhang. Fast algorithm with theoretical guarantees for constrained low-tubal-rank tensor recovery in hyperspectral images denoising. **Neurocomputing**, 413:397–409, 2020.\\\n[8] Salman Ahmadi‑Asl et al. Efficient Algorithms for Low‑Tubal‑Rank Tensor Approximation with Applications to Image Compression, Super‑Resolution, and Deep Learning, arXiv:2412.02598 (2024).\\\n[9] Sheng Liu, Xi-Le Zhao, Jinsong Leng, Ben-Zheng Li, Jing-Hua Yang, and Xinyu Chen. Revisiting high-order tensor singular value decomposition from basic element perspective. **IEEE Transactions on Signal Processing**, 2024.266.\\\n[10] Wenjin Qin, Hailin Wang, Feng Zhang, Jianjun Wang, Xin Luo, and Tingwen Huang. Low-rank high-order tensor completion with applications in visual data. **IEEE Transactions on Image Processing**, 31:2433–2448, 2022.\\\n[11] Dan Garber et al. Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity. arXiv:2308.01677 (2023)."}]

Author rebuttal:

Meta-review: The paper develops gradient descent for nonconvex tensor recovery from tube-wise sensing. The analysis built upon existing GD analyses of tensor/matrix completion with leave-one-out arguments. Although the analysis does not bring new insights, the cleanliness of the results and potential applicability in applications makes the paper well-appreciated by the reviewers. The reviewers are all positive about the paper and I recommend acceptance.
Decision: Accept (poster)