The Power of Small Initialization in Noisy Low-Tubal-Rank Tensor Recovery
Authors: Zhiyu Liu
Haobo Geng
Xudong Wang
Yandong Tang
Zhi Han
Yao Wang
Venue: ICLR 2026 Poster (2026)
Keywords: low-tubal-rank tensor recovery; t-SVD; t-product; over-parameterization;non-convex
Primary area: optimization
TL;DR: For the noisy low-tubal-rank tensor recovery problem, we show that factorized gradient descent with small initialization converges to nearly the minimax optimal error.

Abstract: We study the problem of recovering a low-tubal-rank tensor $\mathcal{X}\_\star\in \mathbb{R}^{n \times n \times k}$ from noisy linear measurements under the t-product framework. A widely adopted strategy involves factorizing the optimization variable as $\mathcal{U} * \mathcal{U}^\top$, where $\mathcal{U} \in \mathbb{R}^{n \times R \times k}$, followed by applying factorized gradient descent (FGD) to solve the resulting optimization problem. Since the tubal-rank $r$ of the underlying tensor $\mathcal{X}_\star$ is typically unknown, this method often assumes $r < R \le n$, a regime known as over-parameterization. However, when the measurements are corrupted by some dense noise (e.g., sub-Gaussian noise), FGD with the commonly used spectral initialization yields a recovery error that grows linearly with the over-estimated tubal-rank $R$. To address this issue, we show that using a small initialization enables FGD to achieve a nearly minimax optimal recovery error, even when the tubal-rank $R$ is significantly overestimated. Using a four-stage analytic framework, we analyze this phenomenon and establish the sharpest known error bound to date, which is independent of the overestimated tubal-rank $R$. Furthermore, we provide a theoretical guarantee showing that an easy-to-use early stopping strategy can achieve the best known result in practice. All these theoretical findings are validated through a series of simulations and real-data experiments.

Published as a conference paper at ICLR 2026
THE POWER OF SMALL INITIALIZATION IN NOISY LOW- TUBAL-RANK TENSOR RECOVERY
Zhiyu Liu Haobo Geng', Xudong Wang".2, Yandong Tang', Zhi Han', Yao Wang
1 State Key Laboratory of Robotics and Intelligent Systems, Shenyang Institute of Automation, Chinese Academy of Sciences, China
2 University of Chinese Academy of Sciences, China
3 School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore
4 The Center for Intelligent Decision-making and Machine Learning. School of Management, Xi an Jiaotong University, China
ABSTRACT
We study the problem of recovering a low-tubal-rank tensor X. E Ruuxank from noisy linear measurements under the t-product framework. A widely adopted strategy involves factorizing the optimization variable as U ut, where Rxx followed by applying factorized gradient descent (FGD) to solve the re- sulting optimization problem. Since the tubal-rank r of the underlying tensor X. is typically unknown, this method often assumes < R < n, regime known wwer-parameterization. However, when the measurements are corrupted by some dense noise (e.g., Gaussian noise), FGD with the commonly used spectral initial- ization yields a recovery error that grows linearly with the over-estimated tubal- rank R. To address this issue, show that using small initialization enables FGD to achieve a nearly minimax optimal recovery error, even when the tubal- rank R is significantly overestimated. Using a four-stage analytic framework, we analyze this phenomenon and establish the sharpest known eгror bound to date, which is independent of the overestimated tubal-rank R. Furthermore, vide theoretical guarantee showing that an easy-to-use early stopping strategy can achieve the best known result in practice. All these theoretical findings are validated through a series of simulations and real-data experiments.
pro-
INTRODUCTION
In recent years, the growing complexity and dimensionality of real-world data have highlighted the limitations of traditional vector and matrix models. As a natural generalization, tensors provide a more expressive framework to capture dineiiidmeesional correlations inherent in data arising from applications such as hyperspectral imaging (Han et al.] (2025). dynamic video sequences (Han et al., 2024], and sensor arrays (Rajesh Chaturvedi] [021] Fu al., 2025). A common trait shared across these applications is the underlying low-rank structure of the data when represented in tensor form. Leveraging this property, a wide range of inverse problems can be effectively reformulated as low-rank tensor recovery tasks. Notable examples include image inpainting (Zhang & Aeron 2016 Gilman et al. 2022, Yang et al. (2022), compressive imaging and video representation (Wang et al. @017|Baranian et al. 2017; Wang et al. 20018), background modeling from incomplete observations (Cao et al. 2016) Li et al. 2022) Peng et al. 2022). and even advanced medical imaging techniques such computed tomography (Liu al. 2024a). The goal of low-rank tensor recovery is to recover the target tensor X, from a few noisy measurements:
= (A,, + 8,, i i= 11,2... m, where 8; denotes the unknown noise. This model can be concisely represented as y (T..)) ) + s, where NT ((),) X,), .... (Am. X, X.)). Since X, is low-rank, the problem can be solved via rank minimization: minx rank(X),ss s. t.. l1 2)222 S 6,, where rank(-) denotes the tensor rank function and c, denotes the noise level.
There are various tensor decomposition methods, such as CANDECOMP/PARAFAC decomposi- tion (CP) CCrroll & Chang 1970; Harshman 1970), Tucker decomposition (Tucker 1966). Tensor
Cooresponding author; yao.s.wange @ gmail.com

---

Published as a conference paper at ICLR 2026
Singular Value Decomposition (t-SVD) & Martin 2011). Tensor Train (Oseledets)
2011
and Tensor Ring (Zhao et al. 2016), each leading to different definitions of tensor rank. In this work, we adopt the t-SVD along with its associated tubal-rank (Kilmer et al. 2013). We adopt t- SVD due to its use of circular convolution along the third dimension via the t-product, enabling it to capture frequency-domat
structures effectively (Wu al., [024). This capability makes it particu-
larly powerful for handling multi-dimensional data such as images and videos (He et al., (024 Wu
& Fan 2024 Wu al. 2025| Liu al.) 2023 Han al. 2023). Furthermore, I-SVD guarantees an optimal low-rank approximation, in manner directly analogous to the Eckart- Seuart-Young Young theorem for matrices (Eckart & Young 1936). Under the t-SVD framework, since problem (2) NP-hard, a common approach is to relax the tubal-rank constraint to the tensor nuclear norm. This reformulates the original problem as a tubal tensor nuclear norm minimization. While this relaxation theoreti- cally sound, solving it typically requires repeated t-SVD computations, which become increasingly expensive as the tensor dimensions grow.
To address this issue, more recent and popular approach is to adopt the tensor Moner-Monteiro (BM) factorization, a higher-order extension of the matrix Burer-Monteiro method (Burer & Mon- teiro 2003). This technique represents the large tensor as the t-product of two smaller factor tensors, thereby transforming the original problem into an optimization over the two factors, often minimiz- ing an objective of the form!
1 wuu = ut)
min MER*XRX: R f(U)= = 4m
w)(-) : R R.xax - R m
where denotes the tensor-tensor product. Factorized Gradient Descent and its variants can then be applied, sig- nificantly reducing computational costs (Liu et al.) [024b] Karnik et al.] 2025). However, such methods typically re- quire prior knowledge of the tubal-rank of the target ten- sor, which is often unavailable in practice. As a result, it common to assume an estimated rank R r, setting often referred to as the over neee-parameterized or over-rank case. However, in the case of noisy low-tubal-rank tensor recovery, over- par--aaaamttrzzationn can lead to larger recov- ery errors. Liu et al., (2024b) showed that the recovery er- ror in the wver-parameterized setting grows linearly with the estimated tubal-rank R. When the tubal-rank is signif- icantly overestimated, the error can become substantial. Furthermore, FGD suffers from a severe slowdown in convergence when the tubal-rank is overestimated. This leads to an important question: In noisy low-tubal-rank tensor recovery, is it possible obtain an error bound that depends only on the true tubal-rank r?
soall Tnin ini
Jntt spectal
Optiaal Icd. cmer
10
10"
10
200
430
2000
4500
6066
5000
1000
Beratiee
Figure 1: Comparison of training and testing errors for Problem ① using FGD with spectral vs. small initializa- tion. The ground-truth tensor has tubal- rank = 2, overestimated rank R = 4, size n 20, 3, m 5kr (2n measurements, and noise a 10 3 Spectral initialization follows Liu et al. (2024b). while small initialization uses a near-zero starting point. Training er- ror is 1 ly DT =u )l( and test- ing error is Iu+ 1x.11%//11 11. "Baseline" denotes recovery under ex- act rank R = Insets show early (first 500 iterations) vs. full error curves.
By investigating this question further, we find that with small initialization, factorized gradient descent con- verges linearly to a nearly minimax optimal error only relying on т, even when the tubal-rank is significantly overestimated. As shown in Figure 1, under over- parameterization, FGD with spectral initialization yields suboptimal recovery error, while FGD with small initial- ization achieves the same error as in the exact tubal-rank setting. However, as the algorithm continues to iterate, the eιror gradually increases and eventually matches that of spectral initialization. We provide a theoretical anal- ysis of this phenomenon and derive the best-known er- ror bound to date. Furthermore, based on early stopping and validation (Prechelt 1998, Stone 2018 Ding et al. 2025), we show that this error is achievable and provide corresponding theoretical guarantees.
4m
As in prior work, we assume that X, is symmetry and positive semi-definite tensor. for detailed expla- nation, please refer Definition
2

---

Published as a conference paper at ICLR 2026
We summarize the main contributions of this paper follows:
Tightest error upper bound We discover that with small initialization, FGD can achieve an error which only depends on the exact tubal-rank in noisy, wer-parameterrzze low-tubal-rank tensor covery. We establish global convergence and the tightest error bound for FGD that depends only on the true tubal-rank. This significantly improves upon previous results (Liu et al. 2024b). To the best of our knowledge, this is the first error bound that is independent of the overestimated tensor rank. Minimax lower bound and near-optimality. We derive an information-theoredt minimax lower bound for noisy tubal-rank tensor recovery, showing that any estimator has mean square error at least S2( arko") ). Comparing this lower bound with our upper bound demonstrates that our method is m
nearly optimal; the remaining gaps are only due to constant factors and dependencies on the condi- tion number
Attainable recovery error A validation-based early stopping method is applied to FGD to achieve the error bound without any prior information about the target tensor. We theoretically show that when the number of validation samples exceeds O(r2x*), the validation error matches the up- per bound up to constants. On both synthetic and real datasets, we demonstrate that in the over- parameterized setting, FGD (small initialization and validation-based early stopping) attains errors comparable to those achieved with the exact-rank setting, and significantly outperforms spectral and large random initializations.
1.1 RELATED WORKS
Non-convex low-tubal-rank tensor recovery under t-SVD framework Nonconvex low-tubal-rank tensor re- covery methods under the t-SVD framework can be broadly catego- rized into two classes. The first class aims to improve recovery ac- curacy by replacing the tubal tensor nuclear norm with nonconvex surro- gates. The second class focuses on improving computational efficiency by decomposing a large tensor into smaller factor tensors. We first discuss the methods in the first category. These approaches de- rived from the tubal tensor nuclear norm and include variants such as the t-Schatten-p norm (Kong) al.) 20188, weighted t-TNN (Mu et 2020).. partial sum of t-TNN (Jiang al.. 2020) and others (Qin et al. 2025) Other methods employ nonconvex functions such as Geman or Laplace penalties in place of the tubal tensor nuclear norm (Cai et al., 2019 Xu et al.. 2019). It is worth noting that Wang et al. (Wag et al.] 2021) proposed generalized nonconvex framework that encompasses wide range of non-convex penalty functions. However, these methods still rely on repeated t-SVD computations, which are computationally expensive, and often lack theoretical guarantees. The sec- ond category includes factorization-baat
Table I: Comparison of several low-tubal-rank tensor recov- ery methods based on t-SVD. The noise vector is assumed to consist of Gaussian random variables with zero mean and variance d²
methods
rate
guarantee
error X
/Zhng et al.
2020
X
(Liu al. 2024b)
sub-
local
nk RkR
linear
m X
(Karnik al.
2025
linear
global
Ours
linear
global
nknor
172
methods that decompose a large tensor into two or three smaller factor tensors, followed by optimization techniques such as alternating minimization (Zhou) et et al. 2019, He & Atia 2023 Wu et al. 2025), ), nonconvex tensor norms minimiza-
et al.
2017
tion (Du et al. 2021 Jiang al. 2023b). factorized gradient descent (Liu et al. 2024b] Karnik et al.)
2025 scaled gradient descent Feng et al.) 2025 Wu 2025 Liu et al. 2025). ). Beyond these two
main categories, there also approaches based on randomized low-rank approximation (Qin al.)
2024) and alternating projections (Qiu et al. 2022) for solving tensor recovery problems.
Over-parameterization in low rank tensor recovery Factorization-batt basedd methods typically re- quire knowledge of the tensor rank. However, the true rank is often difficult to obtain in practice. As a result, it is common to assume an estimated rank larger than the true one, a setting known as wverpparameterization. In matrix sensing, it has been shown that gradient descent can still achieve the optimal solution under over-parameterizztion (Zhu et al.
2018 Stöger Soltanolkotabi 2021 Soltanolkotabi et al. 2025 Jiang et al. 2023a Zhuo et al. 2024 Ding et al. 2025). In contrast, studies on over wee-parameterizee settings in tensor recovery are relatively limited. Although many methods have been proposed to estimate tensor rank, these methods are computationally expensive and lack clear theoretical guarantees (Zhou & Cheung 2019 (hh et al., 202T; Zheng et al.) 2023]
Zhu et al. 2025). Recently, Liu al. (2024b) investigated low-tubal-rank tensor recovery under
3

---

Published as a conference paper at ICLR 2026
over tubal-rank and established local convergence guarantees and recovery error bounds for FGD, where the error depends on the overestimated tubal-rank. Karnik et al. (2025) further proved global convergence of FGD with small initialization under over tubal-rank, in the noiseless setting. In ad- dition, for Tucker decomposition, Luo & Zhang (2024) studied the werrpparametrrzze setting in tensor-on-tensor regression. However, in the presence of noise, its recovery error still depends on the overestimated tensor rank. We compare our method with several closely related works, and the results are summarized in Table
2 PRELIMINARIES
The symbols y, y. Y, y are denoted as scalars, vectors, matrices, and tensors, respectively, Let y |R=x be a third-order tensor. We refer to its entry at position (i,j,)) as (ii,j, and denote the 1-th frontal slice by Y : I), following MATLAB-style indexing. The inner product between two tensors y and 2 is given by ().2) = Ei= (Y)), (1), 2()),, where each Y and (t) are corresponding frontal slices.
For any tensor y E Rmxxxk, its Discrete Fourier Transform along the third mode yields V e Cmxaxk In MATLAB syntax, we have y = fft(() [].3,, and y ifft ( (1.3). We denote Y Cmmxxnk block diagonal matrix of y, i..., Y bdiag( diag( Y r ..... Y (()).
The tensor-tensor product (t-product) of two tensors 2 E gm and y E Raxaxk is Z * y E Rmxaxk, whose tubes are given (Z * (i, 1') = ΣE p(i.p.)) (p, ,:), where denotes the -k circular convolution operation, i.e., (ær y): Eÿ=1 f(odd-)(modk)
For any tensor y E CmXxxx its conjugate transpose y E C"xxxx is computed by taking the conjugate transpose of each frontal slice and reversing the order of slices 2 through k. The identity tensor, represented by I E Ruxaxk is defined such that its first frontal slice corresponds to the n identity matrix, while all subsequent frontal slices are comprised entirely of zeros. This can be expressed mathematically as: ((1) Inxm: I = 0, 2.3...... k.
A tensor Q E g II
considered orthogonal if satisfies the following condition: Q Q
Theorem 1 (t-SVD (Kilmer & Martin 2011)). Let y E Rmxxnk, then it can be factored as y = Vy * Sy Wy where Vy E m. Wy E Raxxxk are orthogonal tensors, and Sy E Rmxaxk is a f-diagonal tensor, i.e., all the frontal slices of Sy are diagonal matrix.
For y mmxxn its tubal-rank rank;()) ()) defined as the nonzero diagonal tubes of Sy. where Sy is the f-diagonal tensor from the t-SVD of y. That is rank; := # (i Sy i,:) * 0}.
And its average rank is defined as rank, ()) = = E rank (((1). The condition number of a tensor y E R is defined as kv)) = a
aenin (Y) where Y is the block diagonal matrix of tensor y and 01 (Y) ... minn (Y) > 0 denotes the singular values of Y. For y E p its spectral norm is denoted as ||>|| == [|bcirc())]] ||Y|| its frobenius norm is defined as
|D' = Ei,,, (i, 1)?; its tubal tensor nuclear norm is defined as |||| = Y %|x KKrmik
et al. 2025).
MAIN RESULTS
3.1 FACTORIZED GRADIENT DESCENT AND T-RIP
Firstly, we present the detailed update rule of the factorized gradient descent method for solving
problem : Uo ~ (O, ) U.41 = U, 12n" (Dr( * U - X * x ) * U
where 2i' Σm A, and X, X x X Raxxx A common assumption for analyzing the convergence of factorized gradient descent is the I-RIP, which is defined as follows:
Definition 1 (t-RIP (Zhang al. 2021)). A linear map M. Ruxak + R. is said to satisfy (r. 8) tensor Restricted Isometry Property (1-RIP for 8 E [0, 1] if for any tensor y E R gnxxxt xk with
tubal-rank I r, the following inequalities hold: (1 | < | & (1 5) |
4

---

Published as a conference paper at ICLR 2026
The t-RIP condition has been shown to hold with high probability (Zhang et al. 2021 if m 2 rnk/8² provided that each measurement tensor A, in the operator D1 has entries drawn indepen- dently from a sub-uuusue Gaussin distribution with zero mean and variance 1. Note that this condition has been extensively used in previous studies (Zhang et al. 20200 Liu et al. 2024b Karnik et al. 2025). making it natural and reasonable assumption in setting.
We decompose the FGD update as
Dt
1 tli
Ui+1 = =u, - - uU - x.) (3
(u, uu x.) +
D1 (s)
m
(b)==E
where maxxxk Roxaxk denotes the identity map. Then the t-RIP condition and tensor concentration bounds are applied to control terms (a) and (b) separately.
3.2 THEORETICAL GUARANTEES
We first establish theoretical guarantees for solving noisy low-tubal-rank tensor recovery via FGD with small initialization.
Theorem 2. Assume the following assumptions hold: (1) the linear map Dt satisfies (2r + 1, I-RIP with 5 S 6 "Kerss (2) the step size 1l S <<=-|1211 (3) the error term E == DD (8) satisfies
||E|| S. CK 2x-=2o2 (xx (x): (4) each entry of the initial point Ug is i.i.d ( a² (5) X, gnxaxk full tubal-rank r tensor. With all these assumptions, the following statements hold with probability at least - ke
-e-- -8 -max(k( max((((C))R-T) R-r+1, kee),
2x² Vrn
10k²
1. When R and the initialization scale satisfies S
then
have
2223/2
1 * U
xx,IIF S VFr,1 where
n1 min (x) In
Vicaomin (2)
When
r
R
3r, and
initialization 10k2
scale
a satisfies a
25
16
2k² /rn
min
(2in(()) (HAn))?
then we have
((RAn) - ||
128/14
narEk 2112 ((((An)) r)a²
11 uU
X.1IF S VFx² E1l. where 8*
In
1jo min
(x)
3.
When R
3r. and the initialization -10k
scale
satisfies
24
min
Omin (X) [RAn)R*
N.T g #
2n V
then we have
((RAn) 111-01117
R28/14
C3 (RA)
v Vnxx" 1|11
[ * u X.IIF S V where ix
10 (2) In
12((RAn) - r) n)a?
Here, C, C, C32 C are fixed numerical constants, and define R.R. := min,(R, n), == x(x).
Remark 1. (Recovery error) Our final recovery error is /rx2||ET1, which depends only on the spectral norm of the noise term E, the condition number k. of X, and the true tubal-rank We make no specific assumptions on the distribution of the noise, requiring only that ||ε|| I CK 202 (Z) wide range of noise distributions. When the noise
This makes our result potentially applicable is Gaussian noise, our bound reduces to that of (Liu et al. (024b). However, a key difference is that error bound depends only on the true tubal-rank whereas the bound in Liu et al. (024b) depends on the overestimated tubal-rank R.
Then present a theorem that characterizes the minimax emrrr in the Gaussian noise case. Theorem 3 establishes the fundamental statistical limit for low-tubal-ram tensor recovery. Specifically, for any estimation procedure, the mean squared error cannot uniformly fall below order (nrko / /m) over tensors of tubal-rank at most r. Furthermore, there exist parameter choices under which the emor attains this order with constant probability.
5

---

Published as a conference paper at ICLR 2026
Theorem 3 (Minimax error). Suppose that the linear map M))) satisfies the (r. 8) t-RIP, X, RuxxxE is a full rubal-rank r tensor, and that s ~ (( then any estimator Xest obeys
nrko²
nrko²
sup Elsx - xx 1+8 x.
sup 8 m X,
P (1iXes= - X.I... 1 2m(1 + +6)
2 e a2k
With the minimax error under Gaussian noise, we further show that when & ~ (N( FGD with small initialization converges to nearly optimal error.
Corollary 1. (Nearly minimax optimal error in Gaussian case) Under the assumptions of Theorem
2 farther assume that the entries of the noise vector are Gaussian with zero mean and variance
o², and that the number of measurements satisfies m Z nkk* (X) Then, with high probability,
we have ii * u - x.1 S nkrs= where U, is the same as Theorem
Remark 2. (Sample complexity) Our assumption on the number of measurements m mainly comes from the t-RIP condition, which requires m 2 nkr/82 In this work, we rely only on the +1, 8) I-RIP, without depending on the overestimated tubal-rank R, which is consistent with the setting in KKrriik al. 2025). In contrast, <Liu et al. 2024b) requires the (4R, 5) I-RIP, leading to higher sample complexity as the overestimated tubal-rank R increases. Note that this sampling complexity required only for theoretical guarantees: in practice, much smaller sample size suffices, as shown in Figure (d).
Remark 3. (Comparison with (Liu et al, 2024b)) Both this work and (Liu et al. 2024b) employ factorized gradient descent algorithms to solve the low-tubal-rank tensor recovery problem. They are the first to apply FGD to this problem and provided convergence and recovery error analyses. However, our work differs significantly from them in several key aspects: (I) Initialization: They relies on spectral initialization to obtain a sufficiently good starting point for its theoretical analysis. In contrast, our method requires only a small random initialization to guarantee convergence. These two initialization strategies lead to entirely different analytical frameworks and theoretical results. (2) Convergence rate: In (Liu et al. 2024b), the convergence rate under phe-pprramelerization is sublinear. whereas our analysis shows that the convergence rate remains linear even in the over- parameterized regime. (3) Recovery error: Their recovery error depends on the over wverpaaramttriizd tubal rank R. while ours depends only on the true tubal rank r. (4) Sampling complexity: They require the measurement operator Mt to satisfy the (4R, 8) I-RIP condition, whereas we only require M to satisfy the (2r + 1, t-RIP condition. As result, the sampling complexity in (Liu et al. 2024b) grows with the degree of over paraaaettettiiiooonnn while our requirement remains mild and independent of R.
Remark 4. (Comparison with Karnik et al. (2025) Another related work is Karnik et al. 2025),
which studies tubal tensor recovery under small initialization. Our work differs from theirs in sev- eral key aspects.
(1) Problem setting: While they focus on the implicit regularization effect of small initialization, our goal is to provide theoretical guarantees for -ubal-aa--rnn tensor recovery with noise under small initialization. (2) Technical tools: Their analysis splits the FGD trajectory into only two stages-the spectral stage and the convergence stage, which does not allow a precise characterization of the noise evolution. In contrast, we introduce a four-phase decomposition that provides a much finer description of the trajectory, enabling us to track the effect of noise through- out all stages. Consequently, directly extending their results to the noisy tensor setting does not yield minimax-optimal recovery guarantees. (3) Theoretical results: Our analysis requires less restrictive bounds on parameters. For example, the upper bound on the initialization scale in our Theorem 2 is significantly more relaxed than that in (Karnik et al. (2025), Theorem 3.1].
Remark 5. (Discussion with tubal-rank estimation methods) Over the past five years, many low- tubal-rank tensor recovery methods with rank estimation strategies have been proposed (Shi et al. 2027 Zheng et al. 2023 Zhu et al., 2025). (1) Problem setting: Our goal is to achieve stable recovery even when the specified tubal-rand rank upper bound exceeds the true tubal-rank, ensuring that the error does not deteriorate as the upper bound increases. In contrast, rubal-rank estimation methods aim to identify or approximate the true tubal-rank. (2) Noise models: [Shi et al. (2027) and]Zhu et al. (2025) considered rank estimation in the presence of spurse noise, while Zheng el al. (202)) focuses on fast and robust rank estimation in the noiseless setting. Our results apply to the situation inthe presence of nab-Gaussian noise. (3) Theoretical guarantees: To the best of our knowledge, the above works do not provide eank-independer error bounds under the t-SVD and tubal-rant, setting. Our main contribution is to establish such tubal- boakl-rank-hae innk--indeeeneett guarantees and demonstrate near-minimax statistical accuracy.

---

Published as a conference paper at ICLR 2026
3.3 PROOF SKETCH
Define the tensor column subspace of X as Vx E RuxxxE Consider the tensor V * Ur and the corresponding t-SVD Vx * U = V. S W. with W. E Rxrxk And we denote Wt,1 E RR((n-r)) as tensor whose tensor column subspace is orthogonal to the column subspace of Wr. Then we can decompose U, into "signal term" and "overrparamettrizaaton term":
Ut = U We * We U WT.1 * W
(2)
signal term
over-prrametrrizatoo term
Through this decomposition, we can separately analyze the signal term and the over- parameterization term. Specifically, consider the following three quantities to study the vergence behavior of FGD:
mmin (Ut Wt): the magnitude of the signal term;
1 * We,i the magnitude of the vve-pparametrrization term;
VV x= Vu.+w,ll: the alignment between the column space of the signal and that of the ground truth.
Then we divide the trajectory of FGD into four phases:
Alignment phase: At this stage, the column space of the signal term U; We gradually aligns with that of the ground truth X., indicated by the decreasing value of [|V Vu.=w,ll Both muin (U We) and [iM, We.1 remain small due to the small initialization.
II Signal amplification phase: Here, min (U Wi) grows exponentially until it reaches least (min(2)) while 11,, W.,1 || remains nearly at the scale of the initialization.
V10
III. Local refinement phase:In this stage, using the decomposition 3 the error is decomposed 11 u, xx11 s 4 V (U, u X.)I + 1 1
The over-parameterization term 1 W.,i 2 remains small, while the in-subspace error || | (U, * u, xI)I decreases rapidly, leading to the lowest recovery error.
IV. Overfitting phase: Eventually, the over-paramettrrzztion term I14, W.,1 starts to grow, which causes the overall error [1,, u X=1|F to increase and approach the error of spectral initialization.
The power of small initialization Through the above four-phase analysis, we can see that small initialization plays crucial role. Specifically, small initialization ensures that the signal term rapidly increases while keeping the vee-parrametrrization term at small magnitude, thereby mitigating the negative effects brought by over parameteriizztioonn In particular, during Phase III, the over- parameterization term | * We,ill remains small, and IIV * (U, U X.)I converges quickly. Moreover, due the introduction of xx we have
V * (U1 * u, X.) r S VFIV (24, * U - Xx)I1:
which ensures that the final recovery error is independent of the over tubal tubal-rank- rank R.
Remark 6. We assume that X is symmetric and can be factorized as X, X' * XT, which aligns with prior works (Liu et al. 2024b Karnik et al.) 2025). Extending the general asymmetric case where X aasym E Taxxxxk factorized as C R requires several modifications. We provide brief discussion here, with more details deferred to the Appendix First, symmetrization step is needed to construct a symmetric tensor X smm E ()) (m))))))))) and its corresponding symmetric model. Second, the trajectories of the two factor tensors are coupled, making it necessary analyze additional imbalance terms, an issue that does not arise in the symmetric setting.
Remark 7. (Comparison with (Ding et al. (025)) Our framework reduces to the matrix setting when nig = 1: the t-product becomes matrix multiplication, tubal-rant becomes matrix rank, and X l uT reduces to X T. In this special case, Theorem recovers the same qualitative phenomenon reported for matrix FGD: small initialization and earty stopping vield ervor bounds that do not deteriorate with the over-specified rank, as shown in literature (Ding al.) (025). However, extending the matrix setting to the tensor setting is nontrivial, one must address several challenges unique to tensors, as discussed in Remark 8
7

---

Published as a conference paper at ICLR 2026
Remark 8. (Tensor specific challenges) First, in the matrix case, the range and the kernel are complementary subspaces. This property no longer holds for third-order tubal tensors. If the true tensor contains non-invertible tubes in its t-SVD, equivalently, if some frequency slices vanish in the Fourier domain, then the range and kernel share common generators. As a result, the classical decomposition of gradient updates into "signal term" and a rover-parameterization term" fails on these non non-inverte inveererteble tubes. This necessitates introducing more refined notion of tensor condition number track the identifiable and unidentifiable components separately. Second, for the power method, each frequency slice of a tubal tensor behaves like an independent matrix power iteration, a known fact in the (gle) 2013). However, in gradient descent for tensor recovery, the measurement operator and its adjoint couple information across all frequency slices. Consequently, the update of any single slice depends on all other slices, making impossible to analyze the slices independently, as in the power method. Finally, in the matrix setting, [andees & Plan (017)) 7) has already established the minimax error for noisy matrix sensing. To the best of our knowledge, however, no such minimax error analysis exists for the tensor setting.
3.4 EARLY STOPPING VIA VALIDATION
Although Theorem 2 provides the sharpest known error bound, is clear that the choice of f depends
on prior knowledge of x,, which is often unavailable in practice. As shown in Figure 1, setting
f too small or too large can lead to increased error. A practical solution to use validation to
determine when to stop the algorithm, common technique in machine learning (Prechelt) 1998] Stone 2018 Ding et al. 2025). Specifically, we randomly split the observed data [A,, 3:) }= into training set (Yrain Murin) of size Merain and validation set (yvva, W..a) of size M.al- We then perform gradient descent using the training set. After each iteration, we compute the validation loss
e, = 7 11 (4, * U )1(2. The final estimate is selected as = arg min, e,, and we output Ui u as the recovered tensor. The full procedure is described in Algorithm 2 Appendix D
We then provide a theoretical guarantee showing that, when é arg min s et, the recovery error 14; + U xx achieves the bound stated in Theorem Theorem 4. Assume the same conditions as in Theorem
2 except that (t) is replaced " logT
(rukkt)2. and T be the max i in Theorem 2 Assume that each entry of the noise vector is independently sampled from the Gaussian distribution NN0,00 Define i = arg minisisTe et. Then, with probability at least
by (Yonin: gain) In addition, suppose that Myat 2 Ci
1 1T 2T exp
Ca(nkric misal
|1 * U X.133 S C n
Miraiin
Mhom
Remark 9. In Theorem 2 we require Mynain 2 = Substituting this into the condition Myyal 2
obtain moat Z x² Pogg T. This is relatively small compared to Marain making it practically feasible. Experiments also show that relatively small myat suffices to achieve an error close to that under the exact tubal-rank.
Ci muan log' Trakk")F
4 EXPERIMENTS
We present series of experiments demonstrating that, under over-rank settings, using small initial- ization combined with validation achieves recovery error comparable to that under exact parame- terization. Compared to FGD with large random or spectral initialization (Liu et al. (024b), our method achieves the lowest recovery error, highlighting the unique effectiveness of small initializa- tion. Additional simulation studies and real-data experiments are presented in Appendix ! Experiments settings We first generate a ground- -rouh tensor X, E x of tubal-rank r by setting X, = X * XT, where X E paxrxk has entries independently drawn from a Gaussian distribution (0, 1). Next, we normalize the tensor by setting X, <- X=/1|xx111. We sample the measurement operator Di by selecting each entry independently from a Gaussian distribution (O, 1). The noise vector 8 has entries independently drawn from AO, o²). Finally, the obser- vations are obtained via the measurement model y M)x + In all experiments, we set m = nik, and n = 30, k = 3, r = 3, Mval = 0.05m. For FGD with small initialization, set the initialization scale to same initialization procedure as in the original paper. For FGD with large initialization, we set the initialization scale to 10, with its step size 1) 0.001 to prevent divergence. We use FGD with
10- 10 For FGD with spectral initialization, we follow the
8

---

Published as a conference paper at ICLR 2026
Spaie 1112
(b)
(c)
(d)
Figure 2: Performance comparison under varying r, o, n, and m. Subtigure (a) illustrates the recovery eπror of all methods under different over-rank values R. with parameters set as m = 10nrk, n = 30, a = 10- 1) = 0.1, and = 5000. Subfigure (b) illustrates the error under varying noise levels a, with = 10nrk, = 30, R = 3r, 17 = 0.1, and T 5000. Subfigure (c) illustrates the error as the problem dimension n changes, where m = 10nrk; = 3r, 7 = 0.1, T = 20000, and 10-3 Subfigure (d) illustrates the performance under different numbers of measurements C... with m = ark, n = 30, R = 3r, = 0.01, T = 20000, and o = 10-3
the exact rank as a baseline method, where "Small random ini (best)" denotes the minimal error obtained by FGD with small random initialization and "Small random ini (ES)" denotes the error obtained by FGD with small random initialization using validation and early stopping. We use the relative square error (RSE) [ 1I. to evaluate the performance of different methods and all
12
experiments are repeated 20 times.
Comparison of different initialization methods From Figure 2 we make these observations:
1. In all four settings, using small initialization yields the same minimum error as the bascline method, which demonstrates its effectiveness. Morcover, by combining small initialization with validation-based early stopping, any prior knowledge of the target tensor. This supports the conclusions of Theorems.
can achieve errors very close to the baseline without requiring
2. For spectral initialization and large random initialization, the recovery error increases as the over- estimated rank grows, and remains higher than that of small initialization. The error from large random initialization particularly high due to its slow convergence. However, in the experiment shown in Figure (c) and (d), where the number of iterations is large enough, its error matches that of spectral initialization.
3. As shown in Figure ( small initialization also significantly reduces sample complexity. Even when m = 3nrk, it still achieves low error, clearly outperforming the other initialization methods.
Verify the validation and early stopping ap- proach We verify the effectiveness of the vali- dation and early stopping strategies. As shown Figure 3 (a), the relative recovery error is minimized when the validation loss reaches its lowest point, demonstrating the reliability of using validation loss as stopping criterion. Figure 3 (b) shows that when too many sam- ples are used for validation, the recovery error increases compared to the minimum achievable error due insufficient training data. Con- versely, when too few samples (less than 5%) are used for validation, the validation-bart method may become unreliable, resulting in in- creased recovery error. Therefore, allocating 5%-10% of the total samples for validation is a reasonable choice.
Figure 3: Validation of the algorithm with m 10nrk, R 3r, 30, 10-3 (a) Validation loss vs. RSE, with the blue dot marking the minimum. (b) Error of the validation- based method compared with the minimum errors of baseline and amall-iniiialization under varying Marain
1/ 3, 0.1.
Real data experiments on tensor completion
We conduct real-data experiments on the low-tubal-rank tensor completion problem. We consider the problem of low-tubal-rank tensor completion under the Bernoulli observation model. Let the target tensor be X, E Ra1 X X with unknown tubal-rank r, where each entry is independently
observed with probability p. Denote the set of observed indices by Ω [ [mi] x [na] x [na). and

---

Published as a conference paper at ICLR 2026
Table 2: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels. "FGD-ES" denotes FGD with early stopping, while "FGD-best" refers to the minimum error achieved by FGD over all iterations. We write GTNN-HOP as GTNN for short.
p
0.2
p 0.3
Methods
0 = 0.07
=
0.1
=
0.07
0 = 0.1
PSNR
RE 4
PSNR
RE 4
PSNR
RE
PSNR f
RE
TCTF
16.5892
0.3175
16.5484
0.3191
20.6744
0.2008
20.6335
0.2024
TNN
21.2692
0.1851
19.7672
0.2188
22.0592
0.1681
20.1682
0.2082
TC-RE
20.9288
0.1921
19.5480
0.2242
21.5387
0.1782
19.8376
0.2161
UTF 16.3227
0.3243
14.8770
0.3802
19.2245
0.2355
17.8283
0.2734
GTNN 22.1092
0.1675
20.3132
0.2051
23.1542
0.1481
21.1111
0.1867
FGD-ES 22.5912
0.1616
21.7977
0.1765
23.6579
0.1426
22.7157
0.1585
FGD-best
22.7438
0.1587
21.9268
0.1739
23.8422
0.1395
22.8550
0.1559
define the observation operator o A, where @ denotes the Hadamard product. The goal is to accurately recover the low-tubal-rank tensor X, from the partial and noisy observations Pn + S,), where S, is assumed to be Gaussian noise with entries i.i sampled from Gaussian distribution N a²) in this paper. Under the t-product framework, we adopt the Burer-Monteiro factorization C R where L RT R E RaaxXxxs, The recovery is formulated by minimizing the following factorized loss function: S(C, R) 2p 1 R X S S.) l
= 2
which can be optimized using gradient descent over (c, R.).
Then we perform color image completion experiments on the Berkeley Segmentation Dataset Marr- tin et al. 200T). We randomly select 50 color images of size 481 x 321 We compare three categories of methods: a convex approach: tubal tensor nuclear norm Minimization (TNN) (Lu
al.) 2018), non-convex methods: UTF (Du al. 2021) and GTNN-HOP (Wang et al. (024). and rank estimation-
methods: TCTF (Zhou et al. 2017) and TC-RE (Shi et al. 2021). We
use PSNR and RE as evaluation metries, and for more detailed experiments settings, please refer to
Appendix J.2 The results, shown in Table 2, demonstrate that FGD with small initialization sig- nificantly outperforms all other methods, while FGD with early stopping performs slightly worse but remains acceptable. Therefore, even though the tensor completion problem does not require the t-RIP assumption, FGD with small initialization still achieves the lowest reconstruction error. In addition, evaluate the sensitivity of the algorithm different tubal ranks. As shown in Figure 4 choosing different values of R has only a minor effect on the recovery performance. There- fore, when the true rank is unknown, selecting slightly larger rank for recovery is practical and effective strategy. Moreover, experiments on video completion are presented in Appendix J.2
5 CONCLUSION
We propose novel procedure, that is, factorized gradient de- scent with small initialization, to solve the noisy low-tubal- rank tensor recovery problem. We prove that, even when the tubal-rank is overestimated, the recovery error still depends only the exact tubal-rank r, and is independent of the over- estimated tubal-rank R. This significantly improves upon the error bound in (Liu al.] (2024b), and to the best of our knowl- edge, is the first error bound for noisy low-tubal-rank tensor recovery that does depend on the overestimated tubal-rank and is nearly minimax optimal. Moreover, we demonstrate that this error bound can achieved though validation and early stopping procedure without requiring any prior knowl- edge of the underlying tensor. Numerical experiments are fur- ther conducted to support our theoretical findings.
24
PSRRR (d8)
20
FCD ES, Ext3
FGD 6S 8x13
FGO Bert 8-10
60.1 Fert suild
FCD 94128
16
26
31
35
46
Image indox
Figure 4: Validation of the sensitiv- ity of FGD to different tubal-ranks.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported in part by the National Natural Science Foundation of China under Grant T2596040, T2596045 and U23A20343, CAS Project for Young Scientists in Basic Research, Grant YSBR-041, Liaoning Provincial "Selecting the Best Candidates by Opening Competition Mecha- nism" Science and Technology Program under Grant 2023JH1/10400045, Fundamental Research Project of SIA under Grant 2024JC3K01, Natural Science Foundation of Liaoning Province under Grant 2025-BS-0193 Joint Innovation Fund of DICP & SIA under Grant UN202401.
REFERENCES
The power and arnoldi methods in an algebra of circulants. Numerical Linear Algebra with Appli- cations, 20(5):809 831, 2013.
Richard G Baraniuk, Thomas Goldstein, Aswin C Sankaranarayanan, Christoph Studer, Ashok Veer- araghavan, and Michael B Wakin. Compressive video sensing: Algorithms, architectures, and applications. IEEE Signal Processing Magazine, 34(1):52--6) 52- 2017.
Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefi- nite programs via low-rank factorization. Mathematical Programming, 95(2):329-33 2003.
Shuting Cai, Qilun Luo, Ming Yang. Wen Li, and Mingqing Xiao. Tensor robust principal compo- nent analysis via non-convex low rank approximation. Applied Sciences, 9(7): 1711 2019.
Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions Information Theory, 57 (4):2342-2359, 2011.
Wenfei Cao, Yao Wang, Jian Sun, Deyu Meng, Can Yang, Andrzej Cichocki, and Zongben Xu. Total variation regularized tensor rpea for background subtraction from compressive measurements. IEEE Transactions on Image Processing, 25(9):4075-4090 2016.
J Douglas Carroll and Jih-Jie Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of "eckart-young" decomposition. Psychometrika, 35(3):283-319, 1970.
Lijun Ding, Zhen Qin, Liwei Jiang, Jinxin Zhou, and Zhihui Zhu. validation approach over- parameterized matrix and image recovery. In Conference on Parsimony and Learning, pp. 323- 350. PMLR, 2025.
Shiqiang Du, Qingjiang Xiao, Yuqing Shi, Rita Cucchiara, and Yide Ma. Unifying tensor factoriza- tion and tensor nuclear norm approaches for low-rank tensor completion. Neurocomputing, 458: 204 218, 2021.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- Irika, 1(3):111-218, 1936.
Lanlan Feng, Ce Zhu, Yipeng Liu, Saiprasad Ravishankar, and Longxiu Huang. Learnable scaled gradient descent for guaranteed robust tensor pea. arXiv preprint arXiv:2501.04565, 2025.
Mingcheng Fu, Zhi Zheng, Wen-Qin Wang, and Hing Cheung So. 3-d near-field source localization using centro-symmetric cross array via cumulant tensor reconstruction. IEEE Transactions on Aerospace and Electronic Systems, pp- 1 1-14, 2025. doi: 10. 1..10099AESS.22553555555
Kyle Gilman, Davoud Ataee Tarzanagh, and Laura Balzano. Grassmannian optimization for online tensor completion and tracking with the t-svd. IEEE Transactions on Signal Processing, 70: 2152-2167, 2022.
Bo Han, Yuheng Jia, Hui Liu, and Junhui Hou. Irregular tensor low-rank representation for hyper- spectral image representation. IEEE Transactions on Image Processing, 2025.

---

Published as a conference paper at ICLR 2026
Zhi Han, Shaojie Zhang, Zhiyu Liu, Yanmei Wang, Junping Yao, and Yao Wang. Tensor robust principal component analysis with side information: Models and applications. IEEE Transactions Circuits and Systems for Video Technology, 33(8):3713-3725 2023. doi: 10.1109/TCSV/
2023.3239376.
Zhi Han, Yanmei Wang, Shaojie Zhang, Huijie Fan, Yandong Tang, and Yao Wang. Online video sparse noise removing via nonlocal robust pea. IEEE Transactions on Multimedia, 26:7130-7145, 2024.
Ra Harshman. Foundations of the parafac procedure: Models and conditions for an" explanatory" multimodal factor analysis. UCIA Working Papers in Phonetics, 16(1):84, 1970.
Chengxun He, Yang Xu, Zebin Wu, Shangdong Zheng, and Zhihui Wei. Aulti-dimensional visual data restoration: Uncovering the global discrepancy in transformed high-order tensor singular values. IEEE Transactions on Image Processing, 33:6409-6424, 2024. doi: 10. 109/TTP.2024. 3475738.
Yicong He and George K Atia. Robust and parallelizable tensor completion based on tensor factor- ization and maximum correntropy criterion. In ICASSP 2023-2023 IEEE International Confer- ence on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Liwei Jiang, Yudong Chen, and Lijun Ding. Algorithmic regularization in model-free over- parametrized asymmetric matrix factorization. SIAM Journal on Mathematics of Data Science, (3):723-744, 2023a. doi: 10.1 10.1137/22M1519933.
Tai-Xiang Jiang, Ting-Zhu Huang, Xi-Le Zhao, and Liang-Jian Deng. Multi-dimennsonall imaging data recovery via minimizing the partial sum of tubal nuclear norm. Journal of Computational and Applied Mathematics, 372:1 12680, 2020.
Wei Jiang, Jun Zhang, Changsheng Zhang. Lijun Wang, and Heng Qi. Robust low tubal rank tensor completion via factor tensor norm minimization. Pattern Recognition, 135: 109169, 2023b.
Santhosh Karnik, Anna Veselovska, Mark Iwen, and Felix Krahmer. Implicit regularization for tubal tensor factorizations via gradient descent. In Forty-second International Conference on Machine Learming. PMLR, 2025.
Misha E Kilmer and Carla D Martin, Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):6411655) 2011.
Misha Kilmer, Karen Braman, Ning Hao, and Randy Hoover. Third-order tensors as operators matrices: A theoretical and computational framework with applications in imaging. SIAM Journal on Matrix Analysis and Applications, 34(1):148-1))) 1722, 2013.
Hao Kong, Xingyu Xie, and Zhouchen Lin. t-schatten-p norm for low-rank tensor recovery. IEEE Journal of Selected Topics in Signal Processing, 1000:1405-119 2018.
Zina Li, Yao Wang, Qian Zhao, Shijun Zhang, and Deyu Meng. A tensor-based online rpea model for compressive background subtraction. IEEE Transactions on Neural Networks and Learning Systems, 2022.
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-622 2024a.
Xiao-Yame Yang Liu, Shuchin Aeron, Vaneet Aggarwal, and Xiaodong Wang. Low-tubal-rank tensor completion using alternating minimization. IEEE Transactions on Information Theory, 66(3): 1714-1737, 2019,
Xinling Liu, Jingyao Hou, Jiangjun Peng. Hailin Wang, Deyu Meng, and Jianjun Wang. Tensor compressive sensing fused low-rankness and local-smoothness Proceedings of the AAAI Con- ference on Artificial Intelligence. 37(7) 8887, Jun. 2023. doi: 10. 10.1669/am 2677. ee/
URL htt.:http:///o/ aaai. org wwtp:/xwxxxpppppp..peep
12

---

Published as a conference paper at ICLR 2026
Zhiyu Liu, Zhi Han, Yandong Tang, Xi-Le Zhao, and Yao Wang. Low-tubal-res tensor recovery via factorized gradient descent. IEEE Transactions on Signal Processing, 2024b.
Zhiyu Liu, Zhi Han, Yandong Tang, Jun Fan, and Yao Wang. Efficient low-tubal-ran tensor esti- mation via alternating preconditioned gradient descent, 2025.
Canyi Lu, Jiashi Feng, Zhouchen Lin, and Shuicheng Yan. Exact low tubal rank tensor recovery from gaussian measurements. In Proceedings of the 27th International Joint Conference on Artificial Intelligence. pp. 2504-2510, 2018.
Yuetian Luo and Anru R. Zhang. Gensor-on-tensee regression: Riemannian optimization, over- parameterization, statistieal-computaaiiona gap and their interplay. The Annaly of Statistics,, 52 (6):2583 2612, 2024. doi: 10. (0.1214/2-A002236. URL. pistss:/ddor http://tto.oo//////////o 1214/ 24-A062396
D. Martin, C. Fowlkes, D. Tal, and J. Malik. A datahase of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proc. 8th Int'l Conf. Computer Vision, volume 2. pp. 416-423, July 2001.
Yang Mu, Ping Wang, Liangfu Lu, Xuyun Zhang, and Lianyong Qi. Weighted tensor nuclear norm minimization for tensor completion using tensor-svd. Pattern Recognition Letters, 130:4-11, 2020.
Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295- 2317, 2011.
Jianguun Peng, Yao Wang, Hongying Zhang, Jianjun Wang, and Deyu Meng. Exact decomposition of joint low rankness and local smoothness plus sparse matrices. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45:5766-577 57816,5771777 2022.
Lutz Prechelt. Early Stopping But When?, ?, pp. 55 59. Springer Berlin Heidelberg, Berlin, Heidel- berg, 1998. doi: 10.1007/3-550-444300
Wenjin Qin, Hailin Wang, Feng Zhang, Weijun Ma, Jianjun Wang, and Tingwen Huang. Nonconvex robust oigh-order tensor completion using randomized low-rank approximation. JEEE Transac- tions on Image Processing, 33:2835 28500, 2024.
Wenjin Qin, Hailin Wang, Jingyao Hou, and Jianjun Wang. Accelerating large-scale regularized high-order tensor recovery. arXiv preprint arXiv:2506. 095594 2025.
Haiquan Qiu, Yao Wang, Shaojie Tang, Deyu Meng, and Quanming Yao. Fast and provable noncon- vex tensor rpea. In International Conference on Machine Learning, pp. 1821 1-82499. PMLR, 2022.
Rajesh and Ashvini Chaturvedi. Data reconstruction in heterogeneous environmental wireless sensor networks using robust tensor principal component analysis. IEEE Transactions Signal and Information Processing over Networks, 7:539-550, 2021.
Qiquan Shi, Yiu-Ming Cheung, and Jian Lou. Robust tensor svd and recovery with rank estimation. IEEE Transactions on Cybernetics, 12610):0067-10682, 2021.
Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie. Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing. IEEE Transactions Information Theory, 71(4):2991-3033 2025.
Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruc- tion. Advances in Neural Information Processing Systems, 114-23311-2344,, 2021.
M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society: Series B (Methodological), 36(2):111-133, 12 2018. ISSN 0035-9246. doi: 0o1111/.2577-6611197...o66
13

---

Published as a conference paper at ICLR 2026
Ledyard R Tucker. Some mathematical notes three-mode factor analysis. Psychometrika, 31(3): 279-311, 1966.
Hailin Wang, Feng Zhang, Jianjun Wang. Tingwen Huang, Jianwen Huang, and Xinling Liu. Gen- eralized nonconvex approach for low-tubal-rank tensor recovery. IEEE Transactions on Neural Networks and Learning Systems, 33(8):3305-3319 2021.
Yao Wang, Lin Lin, Qian Zhao, Tianwei Yue, Deyu Meng, and Yee Leung. Compressive sens- ing of hyperspectral images via joint tensor tucker decomposition and weighted total variation regularization. JEEE Geoscience and Remote Sensing Letters, 14(12):2457-25) 2461,, 2017.
Yao Wang, Deyu Meng, and Ming Yuan. Sparse recovery: from vectors to tensors. National Science Review, 5:756-767, 2018.
Zhi Yong Wang, Hing Cheung So, and Abdelhak M Zoubir. Low-rank tensor completion via novel sparsity-inuucing regularizers. IEEE Transactions Signal Processing, 2024.
Tong Wu. Guaranteed nonconvex low-rank tensor estimation via scaled gradient descent. arXiv preprint FrxXi:2500101666, 2025.
Tongle Wu and Jicong Fan. Smooth tensor product for tensor completion. IEEE Transactions on 2024. doi: 10. 109/TIP.2024.449227
Image Processing,
Tongle Wu, Bin Gao, Jicong Fan, Jize Xue, and W. L. Woo. Low-rank tensor completion based on self-adaptive learnable transforms. IEEE Transactions on Neural Networks and Learning Systems, 35(7):8826-885 208888866-888,8,,888888888888888 2024. doi: TT..T//NNS..02...2222222
Tongle Wu, Ying Sun, and Jicong Fan. Non-convex tensor recovery from local measurements. Proceedings of the AAAI Conference on Artificial Intelligence, 39000)21590- Apr. 2025. AAAI/
doi: v3160///aa...9122.3333..3. article/view/35455
URL
Wen-Hao Xu, Xi-Le Zhao, Teng- Ji, Jia-Qing Miao, Tian-Hui Ma, Si Wang, and Ting-Zhu Huang- Laplace function based nonconvex surrogate for low-rank tensor completion. Signal Processing: Image Communication, 73:62-69, 2019.
Ming Yang, Qilun Luo, Wen Li, and Mingqing Xiao. 3-d arry image data completion by tensor decomposition and nonconvex regularization approach. IEEE Transactions on Signal Processing, 00:4221-4304 2022.
Feng Zhang, Wendong Wang, Jianwen Huang, Jianjun Wang, and Yao Wang. Rip-based perfor- mance guarantee for low-tubal-rank tensor recovery. Journal of Computational and Applied Mathematics, 374: 2020.
Feng Zhang, Wendong Wang, Jingyao Hou, Jianjun Wang, and Jianwen Huang. Tensor restricted isometry property analysis for large class of random measurement ensembles. Science China Information Sciences, 64:1-3, 2021.
Zemin Zhang and Shuchin Aeron. Exact tensor completion using t-svd. IEEE Transactions Signal Processing, 6516):1511-1524 2016.
Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring decom- position. arXiv preprint arXiv:1606.05535, 2016.
Jingjing Zheng, Wenzhe Wang, Xiaoqin Zhang, and Xianta Jiang. novel tensor factorization- based method with robustness to inaccurate rank estimation. arXiv preprint arXiv:2305.1145: 2023.
Pan Zhou, Canyi Lu, Zhouchen Lin, and Chao Zhang. Tensor factorization for low-rank tensor completion. IEEE Transactions on Image Processing, 27(3):1522-1663 2017.
Yang Zhou and Yiu-Ming Cheung. Bayesian low low-tubal-rank robust tensor factorization with multi- rank determination. JEEE Transactions on Pattern Analysis and Machine Intelligence, 43(1): 62-76, 2019.
14

---

Published as a conference paper at ICLR 2026
Qile Zhu, Shiqian Wu, Shun Fang. Qi Wu, Shoulie Xie, and Sos Agaian. Fast tensor robust principal component analysis with estimated multi-ran and riemannian optimization. Applied Intelligence, 55(1):52, 2025.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. Global optimality in low-rank matrix optimization. IEEE Transactions on Signal Processing, 66(13)3364--3628, 2018.
Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the computational and statistical complexity of ever-parameterized matrix sensing. Journal of Machine Learning Research, 25(169):1-47, 2024.
15

---

Published as a conference paper at ICLR 2026
CONTENTS
A ORGANIZATION OF APPENDIX
The Appendix is organized as follows:
Section
provides the statement on the use of large language models.
Section
presents the reproducibility statement.
Section
introduces additional preliminaries supporting the main theoretical results.
Section
gives the detailed proof of Theorem 2 and Corollary T
Section
gives the detailed proof Theorem
Section
gives the detailed proof of Theorem
Section presents several technical lemmas together with their proofs.
Section discusses the extension asymmetric case.
Section reports additional simulation results under various noise distributions, along with real-data experiments.
B USE OF LARGE LANGUAGE MODELS
We used GPT-5 exclusively for language polishing and grammatical refinement of this manuscript. The model was not involved conceiving research ideas, developing algorithms, conducting exper- iments, or analyzing results. The authors take full responsibility for the technical content, theoretical contributions, and experimental findings presented this work.
C REPRODUCIBILITY STATEMENT
All theoretical results in this paper are fully supported by detailed proofs provided in the appendix. In addition, the code used for the experiments included in the supplementary material ensure that all results reported in the paper can be reproduced.
D ADDITIONAL PRELIMINARIES
For two positive scalars T, J.Y. S (or Z y) denotes that there exists a universal constant such that < zy (or 2 28), and x: x y denotes that there exit two universal constants 21, >> such that 2 S y S .2
Definition 2 (Symmetry and positive semi-definite tensor). A three order tensor A E Bnxaxk is called symmelry and positive semi-definite if satisfies the following condition:
AT = A, and A is positive semi-definite
Definition 3 (Block diagonal matrix), For any tensor E <Rmxnxk we denote Y E Cmkxnnk block diagonal matrix with it's i-th block the diagonal the i-th frontal slice Y of i.e. (1)
(2)
Y bd)
Y
Definition 4 (Block circulant matrix (Kilmer & Martin 2011)). For a three-order tensor A E n X we denote bcirc(AA) 1n ng Xnigiig as its block circulant matrix, i.e.,
A
A (na)
A 2
(
A
3)
bcirc(A) =
A (ns)
A nns
(1)
16

---

Published as a conference paper at ICLR 2026
Definition 5 (The fold and unfold operations (Kilmer & Martin 2011)). For three-order tensor A R X2nxxn, we have
unfold(AA) = [A(); A ;... [ma)]
fold(unfold(A)) A.
Definition 6 (T-product (inoduct(Kilmerr & Martin 2011 ). For A E R Xn2xns B product of A and B is C - i.e.
IR x the
C = A B = fold(bcirc(A) unfold(B)).
The t-product can also be computed by Algorithm 7
Definition 7 (Identity tenson Kilmer & Martin 2011)). The identity tensor, represented by E
Ruxaxus, is defined such that its first frontal slice corresponds the identity matrix, while all subsequent frontal slices are comprised entirely of zeros. This can be expressed mathematically as:
I Innns
= 0 i
n23
Definition 8 (Orthogonal tensor (Kilmer & Martin 2011)). A tensor Q E Raxaxxs is considered orthogonal if it satisfies the following condition:
*
2 =I
Definition (F-diagonal tensor Kilmer Martin
2011 A tensor is called f-diagonal if each of
its frontal slices is diagonal matrix.
Theorem 5 (t-SVD (Kilmer & Martin 2011 factored as
Lu et al. 2018 ). Lef A E R then it can be
A u S VT.
where E R Xng V E R are orthogonal tensors, and E PaIxnann a f
diagonal tensor.
Definition 10 (Tubal-rank (Kilmer & Martin 2011 For A E R X its tubal-rank rank, (A) is defined as the nonzero diagonal tubes of S, where is the f-diagonal tensor from the 1DD of A. That is
Vank,(A) = S(,,,;)) #0}.
Algorithm Tensor-Tensor Product
Input: y E R Xns 2 E Ro2xNaRRs
Output: X' = == Z X
Compute y fft 3) and Z fft(2.
2: Compute each frontal slice of C by
Y (()
i = 1,
113 +
x
2
conj X (mg (x2))
i=
n3 +
+ 11.....44. n3.
2
3: Compute X' = ifft(((())
The (-SVD of tensor y Buxxxx as Vy Sy W In addition, define Vy as the tensor-column subspace y, and Vyu as its orthogonal complement, i.c., VJ. Vyu =
Based on the t-RIP condition, introduce the following two definitions to facilitate analysis. Definition 11. (S2S-r-RIP) A linear map Mi Baxnnk - Ih is said to satisfy the spectral- to-spectaal (r, 8) tensor Restricted Isometry Property (1-RIP) [(r, 8) S2S-t-RIP] if for all tensors y E kuxnxk with tubal-rank <
(3 (3- m
(2)
$ 81111
17

---

Published as a conference paper at ICLR 2026
Definition 12. (S2N-1-RIP) A linear map 2t Ruxuxk + R is said to satisfy the spectral-to-
muclear tensor Restricted Isometry Property (1-RIP) --S22---RIIP if for all tensors y E I x with tubal-rank
DN M (3-
(3)
6|
m
Then, we provide the detailed pseudocode of Algorithm described in Section 3.4
Algorithm Solving (1) by FGD with early stopping
Input:
Train data (Hurain M.sin), validation data (Bhas, a.), initialization scale step size Y),
estimated tubal-rank Rt iteration number T
Initialization: Initialize
Uo. where
each
entry of Uto is i.dd from
a² (O,
1: for / to 1 2. M maai (U * u,) Surain Ui
2:
U = U,
Validation loss: e, 2m V/lll Mm (L1, U, )1
4: end for
5: Output: U1 where i arg minns
E PROOF OF THEOREM 2
In this section, we absorb the additional factor into 2) for the convenience of presentation, i.e.,
/m
A, t A.//m. Thus, we have (1 - 11 < [()()))) s (1 + 1)
E. ANALYSIS THE FOUR PHASES
Define the tensor column subspace of X as Vx E Rxxxx Consider the tensor V * Ui and the corresponding t-SVD V x UI V, S, W. with W. E RrxRxk, And we denote W., as a tensor whose tensor column subspace orthogonal to the column subspace of W, Then we can decompose 44 into "signal term" and toraettaraattteiiizaionn term":
Ui = U4 We W. U W W.
(3)
signal term
over-parameterization term
Through this decomposition, parameterization term. Specifically, we consider the following three quantities to study the con- vergence behavior of FGD:
separately analyze the signal term and the over-
Emin(U, W.): the magnitude of the signal term; 121 * Wr,i the magnitude of the prratettetttiinnioonnn term;
VV Vu,-w,ll= the alignment between the column space of the signal and that of the ground truth.
Using these three indicators and the recovery error [ * U, X.Ile, identify four phases in the FGD trajectory and analyze them one by one.
E. PHASE ALIGNMENT PHASE
In the first phase, Lemma D states that if the initialization scale is sufficiently small, and under appropriate t-RIP conditions, step size constraints, and an upper bound on the noise spectral norm, the signal term is nearly aligned with the column space of the ground truth tensor X.. At this stage, both the magnitude of the signal term and that of the over- pwrrparratttiiiiioonn term remain small, but the former is significantly larger than the latter.
18

---

Published as a conference paper at ICLR 2026
Lemma 1. Fix sufficiently small constant > 0. Let U E R"xRxk be random tubal tensor
with ii.d NO0, of) entries, and ler e E 1), Assume that Di Ruxaxk + IR satisfies the 01-S2R-1-RIP for some constant 81 > 0. Also, assume that
M
X + + x x + Ex
with || || I (x
(1) (") for each
I J S k. where ó S cix 2 and |E s
1 20 min (2). Lettl u where
15kx
E(RA 1212
2x km
iR 3r
12213/2622
Ca(RAn)8/22
a² x
-15k3
21
k2k2kn0/2
3r
12
c3r2/2
Assume the step size satisfies 17 S 02k c2 2| -1 Then, with probability at least p where
[k(CC))-227) R-24+1 ke- öR
if R 2 2r if R < 2r
ke + ke-ER
the following statement holds. After
2x Vn
miin Sisk or (XU1)2 In
if 3r
03F C3EV (R RAA) 2R² vrn
L. S
if 3r
Uminisisko
036
iterations, it holds that and each 1 j S k have
| |1 - 3/ X1
IV *ld, W. S cr
or U1. *We. (1) ) 2 -03
1
σ U, *W,,,! (1)
K - ag
where
2x v
10k²
ev
if 2 3r
CseV RA RAn
8
cvk
2x² /rn
10k²
if R
C3E
and
cvk
R 3r
B 8Z
EVR
if < 3r.
Here, C12 C1,02, C3 > 0 are absolute constants only depending on the choice of Moreover, Ö, are absolute numerical constants.
1.2 PHASE I:: SIGNAL AMPLIFICATION PHASE
In the second phase, building upon the results from the first phase, the tensor-column subspace of the signal term remains well-aligned with that of the ground truth X., i.c., || x Vu.ww,l remains small. Meanwhile, the magnitude of the signal term, measured by amin (V x Ut)) grows exponentially. In contrast, the over over- parametttterinnnonnn term U W., stays small due to the small initialization.
19

---

Published as a conference paper at ICLR 2026
Lemma 2. Suppose that the step size satisfies 1) I C1K 2 C1K 20
|| || o (x). and W1 Raxaxk - R satisfies (2r + 1, 1 1-RIP for some constant < 8 _
for some small e1 0. [ S
6 "'Vkr" Set y E (0, })), and choose a number of iterations t, such that J (U: *W..) 2 7. Also,
assume that [ W S 2%, 5 3||21
eadmin(X) and VV * Vu., wW., Re (
C2k for some small 0g > 0. Set
4 min min t 2 to minu (V
1
m * Ut)
min (X) /
v10
and, Then the following hold for all E [tx, t1]:
1 (1 8 min (2)²
Miin ( * U.1 2 2
(5)
[ Wi,1l $ 2y (1 + 0 (2) t-to
(6)
[24e1| S 3||2||| and V Vue-w || S C2K
where t t, S
In( Emia
110
E.1.3 PHASE III: LOCAL REFINEMENT PHASE
Once the magnitude of the signal term min (V U1) exceeds (min third phase. In this phase, the recovery error be decomposed v10 the algorithm enters the
U4 U, x-11 s V (U, u X.)1 + 11 We
Due to the small initialization, the weerparaaeterizzatoon term ii4 W.,. grows slowly, while the in-subspace error V (Ul, 21, we have
Xx)II decreases rapidly. Moreover, since Vx E Rexxxk
| x (Ut, * u, x x.) S VT (2, + u - X.)I,:
which explains why the final recovery error depends only the tubal-rank r, despite the over- parameterization.
Lemma 3. Suppose that the assumptions in Lemma 2 hold. If R > then for
x||21||
70 (2)) In
+ 4
((RAn) - () r)
iterations it holds that
1 * u X X TTll || I VOk 13/16366// - 2/33/ 21/16 11/16 + / (8)
if R then for any? t ti.
11, * u X x
x T|r I Vr(1
7 400
o² min (x)) + vFx?
(9)
E.1.4 PHASE IV: OVERFITTING PHASE
The fourth stage is a natural continuation of the third. Consider the decomposition from Phase III:
11 u, - X.I1 < 4 (U, U, xx.)) + 14 1
In the fourth stage, the over- over-parantnn seer-parameterization term U4 * I,.1 starts to grow, eventually domi- nating the recovery emor until it matches that of spectral initialization.
20

---

Published as a conference paper at ICLR 2026
Phase 1-3
Phase plase
10"
10
10
10
10
10
Saaill 19))
1 Wir
V.zz 322
10 10
10
10
10
10
200
400
600
800
1000
2000
4000
6000
8000
10000
Iterations (a)
Iterations
(b)
3.3. The left panel shows the first 1,000 iterations; the right panel shows the full 10,000 iterations. The orange to the orange axis on the right, and the blue curve corresponds to the blue axis on the left. Parameter settings: n 10, 3, r R 10, m 5knR2, 7 0.1, noise standard deviation 0.01, and initialization scale a 10-7
Figure 5: Validation the four- sour-phase convergence analysis in Section
corresponds
E.2 VALIDATE FOUR PHASE IN SECTION 3.3
We conducted experiments to validate the four-phase convergence described in Section 3.3. As shown in Figure observed that:
Phase 1, the column space of the signal term Ur W, gradually aligns with that of the ground truth X., as indicated by the decreasing value of \V* Vu,,w, Both mmin(( (l1 W:) and [it, Wt,i remain small due to the small initialization.
In Phase 2, mmin (u, * We) grows exponentially until it reaches at least
Cmin (2) while
v10
124 W.,i remains nearly at the scale of the initialization.
In Phase 3, the over-parameterization term 1 W remains small, while the in- subspace error VIV * (M, * U - x.)) decreases rapidly, leading to the lowest recovery eπror.
In Phase 4, the in-subspace error IV (4, u X.)II continues to decrease, but only very slightly, while the wee-paraaeteerization term 1 W.,ill grows rapidly and dominates the total recovery error, causing the overall error 14 uU X, || to increase.
E.3 PROOF OF THEOREM
Since the linear map Di satisfies (2r 1, t-RIP, then by Lemma 14 Dt satisfies (2r, v 22kko) S2S-t-RIP. Therefore,
|| x || [[(] Di Dt) (X * X Dt (x)]
$ 22kkō X X 1 + 12 (s)ll
2rk cx (rk) 1/2 || (s)l
(10)
2ee - 20 min (x)² + || (s)
(0)
< V2ok" "min (x) + cin' Omin (2)
$ cs Omin (2))
where (a) use the assumption E S CiK 2 (X).
Then Lemma holds with probability at least 1 - ke RR max ks (-C))R--rr kee). We then divide the proof of Theorem 2 into three cases: r R 3r, and R > 3r.
21

---

Published as a conference paper at ICLR 2026
E.3.1 CASE :R=
In this case, by the results of Lemma
the following statement holds: choose
2n: kn3/2
15x²
and C3 C36,
p/22
2zr2/2
then after
2n²² Vrn
t. 2
n0 min (2)2 In
iterations, it holds that
[1 11 s 3 and x| * VVu., W. I SCx=
(11)
for each S j k; have
or U1, We. 0 2 aB
S 1
2 2
a1 Uu * W.,.!
8 033
where
Vk
Vk
2x² nr
10k²
3 S
and é3 cCg c0/12cg. Cg. By taking
T min (X)
2xx² Vrn
10x
23 14 R n)n²
C3
(x) have 7 faB x (RAm)
Also, have
7
[e W.
08
S
S 27
2x²
Therefore, the assumptions of Lemmas and 3 hold, then we can use the results of Lemma 3 to obtain:
11, xU; X x 110 S Vr(1
7
o min (2)) Vrk |
400
for all t 2 t1, where
1
2k V
T Sinin(X)) (2(
t1 a t, (t1 -t))
In
In
(12)
m0 (x)²
03
110 2
mimnn (x)
min
7
I/ 2V
1
k² Vrno min (X)
In
(13)
mi (2)
EzaB
2/2
/niomin (X)
(14)
m0 (x)
Via
where (a) uses the fact that 7 4 (b) uses the fact that 3 2 ye
r
Then define μ = 100 min (X.) 10. Using the fact that (1 11) es- have
[1 x U1 - x &lll S -re-ult-o m(t + vrx2
E.3.2 CASE 2 :r < R < 3r
The analysis for this case is almost the same way that of the previous case, except that it relies on a different result from Lemma 3, namely that when r, we have
u4 x u.
X X |le S x 1/2 (RAA))
3/3 21/16 X
11/16
vFx² /
where
1
x X
ix 4 + mo (2)
((R A n) - r)y
22

---

Published as a conference paper at ICLR 2026
Taking the bound in Case 1 for t1, we have
re] x1
x (11 (4) + 4,
110 (x)) In
(15)
((RAn) n) -r)
n n2/2, 5/2 xx
x ||
In
(16)
110 (x)
( A n) r|a?
To obtain the result || * u - - * x S x-1| we need to ensure K 13/16 A n)
1/8/413/2 X|| 11/11 - E which leads to
10nx
2nx²
vrn
35/21
4/7 rk 15/14 | [R (RAn) r]
11/21
16/21
(17)
C3
Vk
2xx vrn
10x²
Using the facts that 7
a I
and
B x
in order satisfy the assumption
r
C3
C20min (X) we also need x
10x2
C2 min (X)
2k /rn
rm
(18)
(2 A n) 233114
C3
Combining the bounds
17 and
18
we obtain the bounds for a
ra (x)
TK 35/21
||E |66/21
nnx² /rn
-10x²
S min
(19)
123/14 R
(RAAH((A))) r| 11/21
23
E.3.3 CASE 3: R 3r
In this case, we also use the result from Lemma l. and are different.
However, according to Lemma
the bounds for
Specifically, we have
2k² Vn C3EN COEV(RRA) (RAn)
1 (2)) In
(20)
2x²² Vn
10k²
cv SBS
C3E(RA A
which implies
x t. + t to + -1
2x vn
Tmin (X)
In
11 min (2))
1)0 1) (2)
x=||2|||
(21)
1J0 (2))2
(RRAn) -r)nk)
Vnx² 12
110 min (x) In
(2((AAn) (R A A)
Using the relation 7 2aB S
(2) <2(RAn)
we obtain
10k.
Gmin(X
2n In (R
(22)
/23/14 n)n
Moreover, according to the result of Lemma need to bound
order to obtain [1 * +U,
X X
11 S k²
|
K 35/21
(RA - -r]
X
11/21
16/21
100m
(a) S x. 35/21
[RA m) - -r] - 1/7 4/7
11/21
2x² V C (RAA
(23)
EVT.
23

---

Published as a conference paper at ICLR 2026
where (a) uses the upper bound for 3. Combining these two bounds for a:
22
23
obtain the bound
-10k
minn (X) /23/14 n)nx² 1:15114 | 11 (R
/5/211 || 16/21
}
2x² Vn
a S min
(24)
r|1/7
(RA(
Therefore, we complete the proof of Theorem
E.4 PROOF OF COROLLARY 1
The proof of Corollary follows directly from Theorem 2 combined with the spectral norm bound of ||| Note that
(a) S
nk (b)
| (s)ll
m σ S cn
minn 20 (X),
(25)
where (a) use the result in (Lu et al.
2024b); (b) the assumption that Z nkk /0 min (x). Thus the assumption (3) in Theorem is satisfied. Then we can directly use the results Theorem
to get
ukro
x - X.112 S rk 1111
(26)
E.5 PROOF OF LEMMA
Lemma I is proved based on [(Kamik et al. 2025). Lemma D.8 and Lemma D.9), with the substitu- tion of M Dt' ( by DUWI 2t() E, where & D1 (s).
Lemma 4. Suppose that the linear map Wi Raxx R satisfies (2, 81) 1-RIP and define t* as
t = =in min {i JjE:: | - 1 |
Then for all S1 S t*, we have
a | 1i,,, 8(1 8 (RAn)
U 11 + ?MMM)
[M]]
Proof. The proof of this lemma builds upon (arnik et al., 2025), Lemma D.I]. By incorporat- ing the results from Lemma 14 Lemma 15 and Lemma [6] we can derive the theorem. Com- pared to [Karnik et al. 2025). Lemma D.I], this lemma leverages the inequality ||U <
V(R A n) 2 -1ll reduce the dependence on the third dimension k leading tighter upper bound on
[644 1.
Lemma 5. Suppose that the linear map Di: Ruxnxk -> T satisfies (2, 61) I-RIP. Consider tensor
M 2t (XXX X" " E e gaxnxk and Ut == (I + nM) Uy Let M E Cnkxnk be the corresponding block diagonal matrix of the tensor M with the leading eigenvector in Cnk,, then we have
||Mll U4 2 eilli
In
8(1+61 (RAn)o=112411
t" 2
2 2nn(1 Mll)
Proof. The proof of this lemma can be obtained by incorporating the result of Lemma 4 into the proof of [(Karnik et al., 2025). Lemma D.2].
Lemma 6. Assume that D RRxnnx + R satisfies the ón Vk-S2N-1-RIP for some 8n > Also,
assume that
= D1 MX X + -
x X + MX'' X + X X*X
24

---

Published as a conference paper at ICLR 2026
with | as VM * SM * Wy then define C == VM(i r;:) Raxxxk, and define the initialization Uo = oll with the scale parameter such that:
(X, for each < S k and ò cg2² Denote the 1-SVD of w
18kx
2 12 (R TI 2
2x 44
a²
min mmin (V/2 * (44, in llle
min (V/ * L1)
where uy E Ih is the leading eigenvector of matrix M E Bukxnk
Assume that the learning rate di satisfies yl C35 1355~2112 21 -2, then after t, iterations with
1
2x²² 11
In
or (x
C30 (V) +
the following statements hold:
14, S 3111|
V Vu.. 2x
and for each 1 j S k have
Ur * W.. ( 2 0B
4
(27)
(i. Wi..l (
K" ax3
ag
10k²
where B satisfies min (V) * 2) S B S minu ( U)
2n 24
Cyomin (VI
Proof. The proof of this lemma relies on the result of [ [KKami et al.
2025 Lemma D.7], The first
condition ((Krnik al. 2025). Lemma D.7] is:
max o (Z: ( ||| +1E 1SSSK
S S22N2.
min o (Ze () SSiS
min (VC x
By the definition of 7, it sufficient to show that
0++
(1)
||21|||
min
(Ze ()) Jamin
V 44
(28)
ISTSk
2n 1sjsk
and
C3
min or mmi Sšick
V/2 x U1
(29)
2x²
Since for 2: + nM)² the transformation in the Fourier domain leads the blocks
(Ld + nM 1),
combining the result of inequality
288
leads to
(Ze (5)
min
1 n min or (M
2n U
15ick
(30)
m37 ( x 21)
o (Z( 15isk
1 1 max o (M (1))
max
Taking the logarithm on both sides of the inequality yields
min Gr (1))
2x |
Isisk
In
S in
(31)
C37 (VC +())
1 + max o (TT()) 15isk
25

---

Published as a conference paper at ICLR 2026
Therefore, if we take tx as
1 min or (M (M Sisk
2x² 21
4. = In
In
(32)
m30 (V2 21)
1+ 1i SSsc
+++1 M
then condition (28) will satisfied each block in the Fourier domain. For notational simplicity, we define
2x² [
= In
(33)
m3 (V xu)
Then we use Lemma to show that the second condition, i.e., inequality 29 is satisfied. To use Lemma 4 we need to guarantee that t I t². As proved Lemma we have
|| U4o eillis
In
8(1+61V V (RAA)
(34)
2 21 + M(I)
In order to guarantee t, < f", we need to prove
M
144 u1
8(1+5L R) / (RAn)a 41p
(35)
Eyming (3 4 Kjsko, 11761))
2
2 In + [|]])
In
To prove this inequality, first bound In(1 m/||||)/ fact
1tnpinng
Using the
149maxi 11500,
2
S In(1 + x) x. we have
1t
In(1 + m|
|| + mmini
(36)
14 (T76))
minisisa, (M +1
In
Using the assumptions 8 < and D.6], we have
and 1/ S caK -3x -2 and the result of Karnik et al.
2025). Lemma
2
[M]][( + (mim)
(1 + T1
1
m max (M (1
(1 (T()))
x: |
² 1 + 8
1 28 + ca
5x
(37)
where (a) uses the fact that s 1/3 and 03 is sufficiently small. Therefore, we have
In(1 + MI))
55
(38)
1+mmin ++ Si
(Mg
In
With this upper bound, we recall inequality
35
MI 11400 11 8(1+ kk) k) (1 14
2x [4
vilke
20k In
< In
(39)
C3o (VI + 24)
which is equal to
2x [2||
20x²
|M
Uu00 11
ville
(4)
|
<
C30 (VC * U)
8(1 + 81 k)
8(1
6
n)aa
|
(40)
26

---

Published as a conference paper at ICLR 2026
where (a) uses the fact that |i240 Ui 11l1///a == 1ite"
vn vills- To prove inequality (40p. we choose a as
-20x²
2x²² [4]]|
|M ( R ( RA
1
vi lk
a² < man (Vc * ())
(41)
With the fact that S and || 2 1| we set a smaller as
20N22
2n [
|| 1 1n 112 1 (R A n) 21
(42)
Cyo (V2 U))
Thus l, S 6" is satisfied, then the conditions [(Karnik et al. (025), Lemma D.7] hold. Therefore, using the results of ((Karnik et al. 2025), Lemma D.7], we have
|| || S 8(1 + 81 VIVE
11] + +1|M))) |M
(43)
(a) 12 (RA n
a
4 (1
?||M))
[M
where (a) the fact that 5 3 and |M
X
from (Karnik et al. 2025
Lemma D.6].
Thus, using that Z(6) (Id n y) inequality
29
holds if
a M
12 (RAm))
u (1 ml| 3t. S
C3
min or (Ird + n omin (V2 *
u
2x²
(44)
which is equal to
V + 24
||
(Id + no, poT ()
Umin
a² S C3
(45)
/2
R m)kk² |
(1 + ml m||l))
Note that
Id + no, no.(MM (1)
(Id+ 1o, (
))
exp ta In (1 M|133
2 exp (-31, In(1 ml(M)))).
(46)
(1+ 7/
1+7 min (.(M))) 18754
Using the definition of t,, i.e., t, =
②b In
and inequality (38) we have
1+0 max isass
(35
15kc²
2x² |
exp (-3t, In(1 m||l)113) 2 exp (-13dx?)-
(47)
C30 (V2 2t)
Combining inequalities
45
and
47
we choose
o Uwin
V * 4
|
2x |
-1kk²
<
(48)
/2. n kn2 2
C30 (V2 +
With this a, inequality (29 holds, and the condition of [Karnik et al. 2025), Lemma D.7] is satis- fied, leading to
V Vu.-w.ll 14(6 + 7) < cx -2
(49)
where (a) uses the assumptions that 5 ~ and 17 C3K 2 and then sets the constants C and C3 small enough. Moreover, for each 1 < _ < k. using the results from [(Krmik et al. 2025).
Lemma D.7], have
mmin U, W. (1)
> 0.8
(50)
11) -
0 U
W.
8 03
27

---

Published as a conference paper at ICLR 2026
where 3 == minigisk or (Z. min (V U).
Then prove the bounds for B and |111111.
Consider 3 == min minnsjss 0, (Z, min V2 + U.. By the definition of Z and inequality 38 we
have
(1 10, (o, S exp (4, In(1 + n1, n0, (M) S exp (4~ In(1 + m/MM)))
In(1 + mlllll
S exp
26 max 15iSk
S exp (10@k*)
1+ (37
(51)
1 1
10k²
2x² |1]
C30 min (V2 + U
holds for all S k.
Then we have
2x 211
B S min (VI 2))
(52)
030 (V/ + zt)
Finally, prove that |4. < (41 By the definition of Zi, * Uo E7,, we have
14. || a Zr, |1-1 ||
(53)
By inequality 29 we have
|| a 2 2:llomin
(22 xu
C3 2n.2
201 2 2 (V 12 mmax (2) a: 2.11 (54)
2x²
which leads
[4, <
+ (10m01+++MMMM]) -
10x²
2x [
In M||M)) [2l|| 3 2aI|211|
C30 (V 22))
(b) < |c|3/
Omin V * 44
||
2x
-15x2
(55)
12 (I ki 11113
c30 (V * +1)
Twin (vI #u
-15k?/2 /2
2x21
= 2cs =2ca||X11 x1||
$ <3111
12 [JA
min (V +4)
where (a) uses inequality (TT): (b) uses the inequality 48 Lemma can be obtained as a direct
consequence of Lemma 6 and the proof strategy used in Karmik et 2025). Lemma D.9]. n
28

---

Published as a conference paper at ICLR 2026
E.6 PROOF OF LEMMA 2
Note that for t = t., these four inequalities trivially hold using the assumptions. Before prove the
t ++ 1 case, we bound
(M - 3) (x' * x² -U, * u. + E as:
|| (2 J) xx=xT -u, -u, + 1Ell
(11 (x* xx -u, W. Wi: xu, ||
+11 -3) -3) (u, W.. W * u4 || + |18|
(a) <övkrll X - W, W u, 68 W WT_1 su, ||. +18||
S 88Vkr [ * x |||+|1, W: W. uu Sv We.1 * WT_1 xu, ||+ + ||||
5vKT (1|x11 + |1 W. U. W.. WT,1 + +u 1|+ + ||1
S SoVAr
+vk W.. * W., *U 11. + ||1
(0) Sōvkr
- -) We,1 =. U + ||
S 100V 100vk0KK krk= min (X) + 1.,1 ||
(c) $10c1K 20 (x) ( (1+ 880es V Koo (2)) + cin 2o (2)
(d) S 10 -0 min (X) (RA - 7/40 m (2) 2/1 + 01K -2 amin (X)
(e) S 40c mimi (X),
(56)
where (a) uses the assumptions that Di satisfies (r, 8v S2S---RIP and VE8-S2N--RRIP: (b) fol-
lows from the assumption ||,||| S |||||||| and [[,, * Wt,1 W. 1 * U ||- S ((RAA)) -r) U
Wt.1 WT_ * 24,'1 ||: (c) uses the assumptions S
61 and the induction hypothesis; (d) uses
~² <vvkr
the definition of f and t+: (e) uses the assumption 7 18/7x=(RAm
oggmin (2)) and chooses a sufficiently small
C2. With this inequality, one can replace [1A4AA I) [x* -M, * +l1 || in [<Knik et al.
2025
Lemma E. -Leema E.7] with || (20t' 2N - 3) X * x U, * u, + Ell since they have
same upper bound.
By choosing a sufficiently small C2. together with other assumptions in Lemma 2 we have the assumptions in [(Karnik et al. 2025), Lemma E.6] satisfied, then we can directly use the result in
(Kamik et al. 2025), Lemma E.6] to prove [Me41l| I ||
Also, the assumptions in (Karmik et al. 2025). Lemma E.1] are satisfied, then we use the result of Karnik et al. 2025), Lemma E. to prove the induction hypothesis ():
Juin (ein(12 VV M(+1) 2 miin (V U4+1 Wi+1)
amin (V (1+11
1 + 707min (2)² n0 (Vx 24,)²
mmin (V U++1)
1
7 m)))) 0. 0.1 (2)
Omin
7 1++11
n (2x)²
(57)
1
mo (2))2 t-to
2 1 1 8
170min (x))
1 + 8
2
1 (1+ min (2))
(++1)-e.
29

---

Published as a conference paper at ICLR 2026
This inequality implies that all singular values of V Ue+1 are positive, and then together with the assumptions of Lemma 2 and equation (56), the assumptions of [[Krmikk et al., 2025). Lemma E.3] are satisfied. Then use the result of [(Karnik et al. 2025), Lemma E.3] to prove the induction hypothesis
6
M4+1 11+1,1 1
1 "
2 [1 We,1 112 + 9n V Vee.... 11 11 ||x||p) 112, We, 10
+ +2n1((00 w 3) x Ue x(1,) + E11
11  We,1
1 " 21 + 80n020 min (x)) 9noz 2112112) [11 W 5
(58)
+ 2n 40c, ni 2 0 min (x 2 * WT.1 1'1
< (1 22m2 + 80nc20 min (x) + mmeo (2) 12 We,1 0
+ 80n CiK 0 (x) U1 W (1)
(1 + 80c27/0 (x) U1, W.,1 (1)
21 + 80c min
1
A1
A2
Note that for any block diagonal matrix A
we have ||||| S max, ||A:/|-
An
(1) since U * W1+1,1 is block
Then we have [i * Witi,il S max, [1+11 W1+1,1 diagonal matrix. Therefore we complete the proof of induction hypothesis (6).
Then we proceed to prove ||
Vu... S c2x-2 via [(Kannkk al. 2025 Lemma E.5].
Note that the assumptions in [[Karnik et al. 2025). Lemma E.5] are satistied using the assumptions
of Lemma and the induction hypothesis (5 7
VV Vu..i-W...
< (1 minl >>1 Vu.-w.ll + 150m|| (2I*N 3) (x x u, =u,uu + Ell
"
4
+ 500m? |128 2 X² -U, * 112
$ (1
27
min 222) + 1507 40c 202 20 + 500,)(11 + 1122,1112
4
< (1
77
Jmin (2)
2222) + 6000c177 202 min (x) + 500,) + 9 ?
4
= (1
Jminl (x))
))22) 6000c177 min (X) + 50000r² |||
4
< (1
"
mmin 22)2)22 6000c 2 min (X) + 50000n -1x-11|<111
||
4
< (1 mini (2))))22 -2 6000c177 2 min (X) + 50000m <iK ==xx-
|
4
< (1 Omin (2) )))²)o2k=2 6000c 202 min (X) + 50000mc1 20 0
27
4
< (1 Tmiu (2))) + 56000mc1 o min (x)
77
(59)
4 By taking sufficiently small e (i.e., ci S 5000 ) we have II * Vulu $ C2x Therefore, complete the induction proof.
30

---

Published as a conference paper at ICLR 2026
E.7
PROOF OF LEMMA
Using the definition of ( (equation aadd
1 (
1
min (V x(t 2
1 (1+
no (2))
8
from Lemma 2 we have
1
( 1+ nomin (x)2
v10 mmin (X) 2 Omiu (VX O * [1,,) )
2 2"
which leads to
log 2
vv10 min (2))
(4)
16
2
min (8))
t t,
log
(60)
log (1 + 110 min (2)
17m (x)
9v10
where in (a), we use the fact that log(1+x) S for 0 <<<<<> Therefore, bound [i, We, as
U4, * W
< 27 (1 + 0 (2))) -1
(a)
Tmin (X)
1280cz
I 27
v10
(6)
2
m (X) 1/64
(61)
$ 27
vTO
(c)
- 3-
63/61
mmin
x)) 1/61 < 3/8 m (x)
1)11/11
where (a) follows from Equation 60 (b) uses the assumption that C2 is chosen sufficiently small;
(c) uses the fact that mmin (X) 2
Then divide the proof of Lemma into two cases: the exact-rank case and the over-parameterized (over-rank) case.
Over-rank case: Set é = t1+
no? (X)
300
In
[TGN[[RAn)
k2/4
| 7/4 7//4
)
We first state our induction
hypothesis for t S iti
o (X)
Juin (U1 W.) 2 mmin (V* * xUl)) (
(62)
V1O
[4, W.,1ll 5 (1+ 80nconnoon... (x))
We,
(63)
[2.]l| < 3/1211.
(64)
[V * Vuu.w,ll 5 22
(65)
VV (X * x -1, u1 Ill S 10(1
"
2
(66)
400
187/ | |1111111111
(1-
-
(
(67)
+=6+1 200
When t = f1. the inequalities 62 64 and 655 follow from Lemma 2 As for inequality (63 it
holds when = 4 obviously. When L, we have
V (X * T -U,, U1,,,, )| = | (X * T -U We, WT, *4,))I
< X xT + [1,, W., * WT, U.,1l
<
| + || 111MW, 112 S 10 x0
31

---

Published as a conference paper at ICLR 2026
where (a) follows inequality (64). Next, aim to prove that these inequalities also hold at step t+ 1. To do so, we need to bound the term
(M -J J) X X - -U, * x1 + E as
(2 21 X (x* x - U, u +111
(a) I 100 108V oinn (x) + 8V1*
- [4 W 11 +11111
(b) $10cK 20 (2) + 8v 1.3 (R n) - (1 + 807020 min (2)) 2 (0)))(t-+))112) 1 * Wo
t 20 (X)
(6) S 10c 20 mia (x) + 9dv ((RA
r1 - +0 201 min ( (2))) 7/4 m (2) 1/4
+ c1 -0 min (X)
1/4 || ((r2)
(d) < 10c -2 20 min (X) + 90V (( -r) 166((RAA) -r)
77/4
+ c -210000 (X)
(e) s =0ccxx-2000 (X),
(68)
where (a) uses the result of equation (56): (b) uses the induction hypothesis (63) and the assumption
of ||&||; (c) uses the results of (61) and induction hypothesis 63 (d) uses the definition of E; (e) uses the assumption that C2 are sufficiently small.
Therefore, the condition required for bound 62 (64) and 665 in Theorem E.1 (Karnik et al. 2025)
satisfied. We can thus invoke the corresponding result conclude that inequalities 66 644. and 65 also hold at iteration + 1.
Note that we have all singular values of V
x +lt,+1 * W, are positive using the induction hypothesis
(62). then we have the assumptions of Karnik et al. 2025 Lemma E.3] are satisfied. Therefore,
we use the result of [(Krmik et al.) (025), Lemma E.3] to prove the induction hypothesis (63). which
exactly the way as proving inequality (6) We directly present the result without detailed proof:
U1+1 Wetll S (1 + 80c2110 (X)) +1
U4 Will-
(69)
Then we proceed to prove inequality (67). Note that the condition (7)) in Lemma 7 is satisfied since inequality (88. Moreover, the other conditions of Lemma are satisfied using the induction hypothesis and (65) Therefore, we have
1| (X * X U611 U1+1il
(a)
17
Mmin (x))) V (X * T -u, * u. Il
200
+
77
mmin (2) * We, * W.T. * u, 11+ + 18m/ x | |3
100
(6)
10
1)
min (2)2) (1 400
"
o min (x)) 1|11
(70)
200
+
17
mmin (2))
WT,1 W.T. U
100
H+1 Σ
+ 187| 111111111
(1
7
o (X))
200
+=4++
where step (a) follows the result of Lemma] 7 step (b) uses the induction hypothesis 67). Note that inequality 67 holds for 1+1 if
U * WT * WT, +Uel. I 4
17
o² 2
(71)
400
32

---

Published as a conference paper at ICLR 2026
Using the relationship between operator norm and tubal tensor nuclear norm, have 1 Wt,1 Wt,1 U.ll. S ((RAn) - u 1
(9)
v 1n A((RAn) r1 - 80nc20 min (2)) Ud, * Wl,
9 - (1 m0n ((t))((( o m2)
(72)
where (a) uses the induction hypothesis (63 (b) uses inequality 61
Then we need to bound term 1id2, We..
Combining Equations and
72 and 61.. we note that the inequality
holds if c2 is sufficiently small
9k((RAn) - r)> 7/4 min (2) (x) 2
17
(2)))
6-6
|122
o min
350
This inequality holds so long as 1 S i 41 fact that In(1 + z) 2 - Therefore, we complete the induction of over-rank case.
300
In (R((RA))-))
1/4
| 7/1
by using the
(22)
7774
Then we proceed to prove the upper bound for || X U, U, llf:
(a) S
|| * X -U, 24, ||r
x (X * x U; * U }||F + 1 Wi.1 WT +u 11.
Vr(1
(2)) ||
400
min
/rrll | 11 E|l Σ
(1
1i
- min (-1))-(111
200
7=1+1
2A
k2/4
1//1 3//4
VT
|| +
/
9k((RAm) r)) 7/11
$
3/00 - /33/4
X 11/16 +VrK* ||
(73)
where (a) uses the result of Lemma (b) follows from inequalities definition of f.
67 and
(c) uses the
Exact rank case: As = r, we have u, U, W. * W and W., 0. Using similar approach as in the wver-parameeerize case, we can show that the induction hypotheses (62 65 hold for all 2 4 For induction hypothesis (67). note that
U,W W WT 0,
which implies that 67 also holds for all 2 4, Therefore, we conclude that:
[ U X
S VF(1-
7 o o (2))
400
t+1
+ Vryl
X 211
Σ (1
200 0 min
(2))
4
(74)
+=+++1
2 Vr(1
202 min (x))
VFr²
400
E.8 PROOF LEMMA
Lemma 7, Assume that the following assumptions hold:
||,,1| < |
17 S ck -xxxx211220 -1
(75)
amin (Ld, * W.) 2 V10
mmin (X)
I * Vu-w |l 5 cx
33

---

Published as a conference paper at ICLR 2026
and
[I(] - -10-- * (x) * Xx Ui =U)ll
S -x (11x xx X U; W. * W uu || + I * WT,1 * WT,1 * *Uell.) (76)
where the constant e > O is chosen small enough. Then holds that
x * (X X U441 + + +1(+111l= S (1- 7
200 min minn (x))) V1 * (X * xx -U, u4,'l ]||
+ 77
100 min (2) * WT,1 * WTT, * *u, || + 187| ||||||
(77)
Proof of Lemmal 7 In order to establish Lemma 4, we begin by introducing a key auxiliary lemma and providing its proof.
Lemma 8. Under the assumptions of Lemma 4, the following inequalities hold:
VX== * xu, * U1 3 V x- (X * X - U1 * u1
+ U1 We * WT, u
X X UR * u || - 4 Vx (X * x U1 * 21 ) |e+ * We.l * WT,1 +
X X -u We * W =u; || s <<41|>> * (X x U1 x11
(78)
where ||||| denotes tensor norms, such as spectral norm
Proof. The first two inequalities are derived based on Lemma E.7 in (Kariik et al. 2025). 5.. By leveraging the equivalence between matrix norms, we obtain the desired results by replacing the Frobenius norm in Lemma E.7 with the spectral norm.
Next, we present the proof of the third inequality. We decompose X * X -U * We * W uU as
Vx
V x
U * W. WT_ =U,) + x= (X * X
+Vx+ * *Vx (X * X
-U W, * W. x.
2,
For 31, we have
Z = Vx VI * X * x
-Vx Vx * U2 W. * W. +u;
(79)
1 Vx Vx X * x
VVx V * UU =u,,
where (1) uses the fact that
Vx V Ll, U
Vx Vx * [U, W., * W. +W., * WT... * U4 * W. W. +u, * W..1 W. TT
Vx + * Ub *W, * W =u, +Vx * V +U: * *W,,1 WT,. =u,
-Vx V * Ui W. * W. uU +Vx*V.*S. V. WW, * WW,1 * W. +U
= =Vx V * U, W. * W. UU
(80)
Therefore, we have
| = 1/ Vx X'
x X - Vv * V * U1 * 27
< <1/1xx (X + x - -2,, * u. ||
34

---

Published as a conference paper at ICLR 2026
Then we proceed to bound the term 22
2
Vx-= * VX * (X * xx - -U * Wi * W. =u,) * (Vx * VX + V Vx * vxx))
<< V/x' x Vx-- * (X xx -u Wt * W. =u.) * *Vx[|
+ ||| | x * V (X * xx -u W. * W. *U,) >x * V
(2) || X (x**** X U1 xU Vx + V * U. * W, W. +u xVx1
23
(81)
where (a) using the facts that VX * W 0 and Vx *U =V xx + We * W. =u! For term 33 we have
V * U, We W. * U, * x
1x * Vu..w, Vu..., = Ui + W, = Wi uu * xx=
Vx= * &Vu.., (Vx V.l...)) V * Vu.-w Vuew. * Ui W. * W. zu, * *Vx'
1 V -uu-well 11(V Vei...) | Vui.w. * Vil... xu, * W. * W. * +U; =V--
11Vx
Vuu.w.ll
V Ui * u1; x xxx1
mmin (Vx * -v.=w.)
11V Vue-w.ll
Vx (x*x* - U, -u, uU
Vxx x!
Omin (Vx * w.)
22 V * (x= xT - U2 * U[, )||
(82)
Therefore, we have the third inequality holds.
Based on the results of Lemma we proceed to prove Lemma 7 We decompose X + x U1+1* u into five terms by using the update formulation
U4+1 = Ue + (1 (X) x u; + El xue
X+X - U4 * U
II- (I- * U * (X*x** x U. =u: * (I 1-7, * U,
K,
+ 1) [J 22 (2) (X T - Ui xU, + El * Ui U!!
K2
+ n/ * U1+ * 1(3 22" (1 + T -U, uu ) +
Ka
- u1 * uuT * (X * T - U, U1,
*11, u
K4
n (DU2) * xT_ -1; x U, + El * U1 u, * ((T * XT -U, * x1, ) + E
Ks
(83)
35

---

Published as a conference paper at ICLR 2026
We now bound each of these terms separately. Bounding K1: We note that
Vx= x (I - nHu * U, * (X' xx*xx* x - U1 [1; (I - n +1,)
=Vx * (I - n11, U1 V 1/ (X' * x - U, U1) (I 1211 x
+ +Vx* * (I - n * =Vx
- U, x U, ) * (I - n * U,)
= -Vx * (I - -1,, -
xU,) * (I - nu,, * )
(84)
+1* Vx * *u u1 xVx= * +U, U, x(,)
= (I - 1/ =u; xu, * +Vx) * (X' U, 11 xU,) * (I -np xu!)
+ 17 V/ * U, U x V *U (I U ).
detail
Therefore, we obtain
IV* K, || = 11 (I - nH x1, (X+ -U,* (I n2l,, u(,)) !
1 (1
" omin (x)) 11 (X + x -U, * xU, ,1l }||
40
(85)
22 (X)
+ 1]
min
11 * We,1 * W._1 *Vell-
400
Bounding KC2: Note that
|IV K2 = 1 * [(3 20) * x -U, x1, + E) * U1 * #1 ||
K (II(3 - Dr (X x T -2, * U1 ||| 1 El|) 114,11
9 (II(3- w ")"")) x -U, +2, ||| | +E11) ||x112
9c0 mic (24)
(IX** x uu * W. * W. uu || + 14 W.,1 WT * U.ll.)
+ 9 x * E|||
9c0 min (4)
(1Vx (X X- U, u1 )1 + 11, + W., WT, :..ll.)
+ > *
|||
(86)
where (1) use the assumption | |4,1| < 3 |||: (2) use the assumption 76); (3) use the the result of
Lemma 8 Taking a small constant >> we obtain
IIV x * [(J D2 (X * T - U₁ * U1 ( + El U. * u,!
<
1000 imi (2) | (X x - -u, U1 )|l + +1 We.1 WT, =Uoll.)
1
(87)
+ I * 2112
Bounding K3: Similar to K2,, we have
V x * U, * Ue * [[] - 11')))) * T -u+x4,) + El1
1000 d min (x)
[| * (X x U. * 21,
(01 Il| + +1u W WT_ &.ll..)
(88)
+ + I * E 21|
36

---

Published as a conference paper at ICLR 2026
Bounding K2:: Note that
V x + U1 U2 +X * x T -U, * u!!) +U1, * U
14' X * xx -U, U, ||
233
||x1| |||| X * x -U, x u!!
||x|||
$ (IV**> (X * x U * U, |I| + ||, * We. * WT_ * xu,
(89)
where (1) uses the assumption [4, v 3 | (2) uses the result of Lemma g assumption 1) S cx -||1211|
Then combining the
1- then we obtain
V U1 * U * (X x -1+ ux,) * xu U
< 7 2 (X) 1 | x * (X* -M u
((,)) ||| + 1) 1000
min (x)
11, * W.,1 * W.T. * uU 11.
200
(90)
Bounding K55: Note that
(2))")) * Xx - U4 *u, |||
I ||X * x T -u, * (W, W. + W W.
* uul!
+ +1( 2 - (X * xx -u, + +u ||
T - -U, * We+ * W. *u, || + 14 We_1 WT 4!ll) ||X * X
+ ok 2 (1xx x -U, * W., W +4, + +Iu Wi.1 WT,
( XX X -u, * W., * W U, || + 114 * W. * W. W.T.ul11.
2 (|æ + 112,, * will + 11, W.,1 * W..u u 11.)
_ 2 1| + 2)
(91)
where (a) uses the assumption 76 (b) uses the assumption [1, W., * W.T. u < -1..112.
Then we have
V x= * Kssll = 11V
(X' * X -u * U1 + E) x U, U
* x U2 * x1 ) + Ell
(((2))))) X - Ui U, |l| + ||11] |12,11 2 (1(20)"))) (X X - -1, x4, |l| +
||E1) |||+|||1)
(0)
S (11 + T T-u * -u+ W,, uu + U1 W1,1 W.,,, +u ||| + (11l) 114.11 (112112 + 21121 + +|881)
(6)
2 432 (1x* * x -u,, * >W * W = uu + 14 W., W. * #4, ||. + |111) 114,11*
(0)
< 1728
(IV* * (X' * x U² u, || + 1. W., WT,, U, ||. + [181] 11,11
(92)
where (a) uses the result of Equation 11: (b) uses the assumptions [4,1 < 3 ا|| and ||]|
<
X ||:: (c) uses the result of Lemma 8 Based on these results and the assumption S CR 2| X -2
have
x * (1
* X T - -u u,*U,) + E) * U, * U * +1("" x -M, u,] ) + Ell
" 2 (X))
|V x (X * T Uu= u. ||| + " min (2) WT,1 WT,, U, ||.
S
1000
400
17 mi (x)1|E))
400
(93)
37

---

Published as a conference paper at ICLR 2026
Combining the bounds of these five terms, obtain
IIVe (X x U1+1 ul (+1+11
200 min (2))) 11 x (X Xx - -U U. |||
11 + 200 min (x) U WT,1 WT,1 xu, + 18m1 x E|
(94)
PROOF OF THEOREM 3
The proof of the minimax error bound of the low-tubal-rank tensor recovery follows from the proof of the matrix case in (Candes & Plan 2011). We begin with standard lemma that characterizes the minimax risk for estimating a vector x E R" in the linear model
y Ax +
(95)
where A E R and the entries of independently and identically distributed according to Gaussian distribution (O, o²). For such a model, we have the following lemma that provides its minimax error bound.
Lemma 9. Let (AATT A) be the eigenvalues of the matrix A A. Then
o²
inf sup E i x o² trace ((ATA) A) - E EM (A(TTA)) mER"
(96)
In parficular, if one of the eigenvalues vanishex, then the minimax risk is unbounded.
Proof. We separate the argument into three parts: (A) lower bound via Bayes risk, (B) upper bound attained by the ordinary least squares estimator in the nonsingular case.
(A) Lower bound (Bayes argument) Fix > 0 and consider the Gaussian prior (N, 12),). Under this prior the posterior covari- ance matrix for æ given y is
( A A+
1
1 7z 4n
Σ post (o)
The Bayes risk (for the posterior-ment mean estimator) equals the trace of the posterior covariance:
Bayes (T) ;= En..yl E[x
yl tr (Epost (T))
(97)
Σ 01/02 1/72
>a + 02
where we denote ((AAA) as X; for convenience.
For any estimator & and any prior we have the standard minimax/Bayes inequality
inf sup El 2:12 inf Ran B[1 x0|3]
RBaaee (T):
x
because the supremum over x is at least the average under any prior म. Hence for every T > 0.
inf infsupEl 2 2
X 02/72
some X; = 0 then the hand side equals +00 as 7 > 3o (indeed the corresponding summand
is 2 02 2/22 ?2 oo), the minimax risk is infinite in that case. Otherwise, if all X; 0,
38

---

Published as a conference paper at ICLR 2026
send 7 oc. For each fixed i the function T o2/(2, + o2/ is monotone increasing in 7 and converges to o² d²/As as T - co. By monotone convergence (or by continuity of finite sums) we obtain
inf sup Elia x0| lim Bayees (T)
7-00
(B) Upper bound (least squares achieves the bound).
Assume X for all i, i.c. rank(A) n. Consider the ordinary least squares estimator
Ls (A A) AA y.
Substituting y = Ax + s gives
dts x = (A T A)-1AT
Since o2 the error Lts x is zero-mean Gaussian with covariance
B[(0Ls ( x)
(A (ATA)-AATA LA)
A)-1
Therefore the mean-square risk of 2t,s (for any fixed 2)) equals
El - æ=|² ttr:=trr2/00 ())
This shows
inf sup Blla x²1² S sup == 0² 1
A
m
Combining (A) and (B) yields the asserted identity.
Then we proceed prove the minimax error bound. Define the set of rank; r tensors
D, {x rank, (x) X E Rnxnxx],
and the set of tensors of the form X' y R as
Dy (x x
R. X Raxrxk y E Ruxrxk y + = I).
Note that set D, is much larger than set Dy. Therefore,
inf
sup (2))
E E| est
2 inf sup EI est x1
(98)
X
Xext X:X-y.R
For fixed orthogonal tensor V, define the orthogonal projection tensor Py = V T. which satisfies Piy Py, PJ. Py. Then fix the estimator Yest, for any X E Dy, we have:
||2 11 = |Py Xest X + (I - Py) * X Keseli
= I X xx + ||[I - -py) X 2e
(99)
+ 2( Xest X, (I Pp)) X est)
|py Xest
X1 + ||(I - -Py) Xest
where (a) the fact that the tensor column subspaces of Py X est X and (I Py) Xest are orthogonal, which implies that their inner product vanishes. Therefore, we can directly obtain
X est
x >
IPy
Nest
X 1
|1 y est y * R1
(100)
- * Xest R. R12
39

---

Published as a conference paper at ICLR 2026
Let Rest =V² est. then we have
inf sup Lent X
E| x1I 2 inf sup Bl RIP.
(101)
Rest R
Therefore, the minimax risk is lower bounded by that of estimating R from the data
My (vec R)) s,
(102)
where Wyy IRnn + R and vec denotes the vectorization operator. Then apply the result of Lemma 9to to show that the minimax risk is lower bounded by
inf Xaxt
sup (
Bl| est X1I
(103)
X (W Myy)
Then bound the term T03 by the following Lemma with t-RIP assumption.
Lemma 10. Let y be x orthonormal tensor, suppose that the linear map Mi(-) satisfies
the (r, 6) I-II, then all eigenvalues of My belong to the interval [m - 6), m(1 + 6)].
Proof. By definition, we have
Amiu (Wy'
|| vece (y))(R))
inf
(104)
Amax (ml
sup
|| [ec(R]]]
Note that
(R, 20, (R)(()))) = (ve) - R)11
then we can bound (20 12 2 by the (r, 5) t-RIP
m(1 - 5 * R -
/ * R S m(1 + 8)1 * R
Since |J R = R | 1, then the eigenvalues of D Myy is bounded by [m 8), m(1 (1+ 8)].
Combining the result of Lemma and Equation 103,, we have
1 nrko²
inf sup
E E| est X1
E My
(105)
X Xese
Krrank, (x)=r
X Dr
1+
which finishes the proof of the first inequality in Theorem
Then we proceed to prove the second inequality in Theorem firstly.
We introduce a technical Lemma
Lemma 11 (Lemma 3.14 in (Candes & Plan 2011 model 95 with 8 ~ ~N(00 o² I), then
Suppose that x, y, A, follow the linear
1 æ
inf sup IP ||0 mER*
no0²
> 1 - 1 n/16
(106)
21 A
With the result of Lemmas I1 10 and the linear model
y My (vy(vec(R)) + R E paxrxk
E R
we can obtain
nrko²
sup X. rrakk (5)
||x - -x,11
2 -nrk/16
(107)
2m(1 + 8)
which completes the proof of the second inequality.
40

---

Published as a conference paper at ICLR 2026
G PROOF OF THEOREM
Lemma 12. Suppose that each entry in the validation measurements A., i Ival is sampled from independent identically sub- Sab-Gaassian distribution with zero mean and variance 1, and each is zero-mean Gaussian distribution with variance o², where 01, 02 2 are some absolute constants. And we also assume that tensors D1, Di,,... Dr independent of Vaal and eaal Then for any Seal 0.given moval
2 vall (Di)) + elle
Ci log T, with probability least 1 - 2T exp -o2 Du
maaa( + + S vall (I) D + Vo
(108)
where C1, C2 2 are constants that may depend on e1 and cg.
Proof. The proof of this lemma follows directly from Lemma D.1 in (Ding et al. 2025 since
(A., D) +e is a sub-Gaussian random variable with zero mean and variance (D) f + o² regardless of whether A; and D are matrices tensors. Therefore, the conclusion of Lemma D.I applies directly to this lemma.
Lemma 13. Lett arg minisisT (Da + elle and f arg min | l. under the assumptions in Lemmal 12 we have
+ Sval
28 0². Sval
[Pil -
(D 2 +
(109)
dval
Proof. Under the assumptions of Lemma 12
we have
(I-
<
(1+b |
Ma +el tel I
Vt = =:::;,,,,; I,..., (110)
myal
from the result of Lemma 12
Then have
1
|0 o x
1M (D;)) + ell?
Mval (1 oval)
(111)
1
+ 8val
|ilt (D;) + eel <
(1 + +0?),
mval (1 8val)
dval
which indicates
Oval
28 8val
P
[Dill? 1
0².
(112)
vval
Therefore, complete the proof of Lemma
With these two Lemmas, together with Theorem 2 we proceed to prove Theorem
Replacing the
result of Lemma 13 with D; Ui U1 - X, and D; = U; U1 X., we have
1 1 &val
28
1 * u X 113 < 1 8yal
11; U x X111 + 1 5val"
(113)
To achieve the error Cukkropn" x m
we need the bound
1-8 02 which requires 5 S nkrw" 3mauiin
Taking
nkrk" 3marinn
then we can verify that 1+5mal 1-5.al
< 2
1 8val
+
nkrn"
37Aarain + nkrk
2nkrk4
3maraai
1 8yal
akrk" Breeraan
3mtrain - nkrk
3mtrain
nkrk
(114)
(0)
2nkrÆ4
<
nkr (3rkn
where (a) uses the assumptions that m 2 x Therefore, combining the results of Theorem 2 we have
1 xU; x.11 < C n
Mirain
Moreover, combining
nkrd 3meestn with the assumption myal 2 C
log 32
we have myal 2 C1 m log T
(rnkic4)
Therefore, the proof of Theorem 4 completed.
41

---

Published as a conference paper at ICLR 2026
H TECHNIQUE LEMMAS
Lemma 14. Suppose the linear map Wt BRxxx* - R satisfies satisiiss (1+1, I-RIP with 01 (0, 1),
then Di also salisfies (r, vkrd,) S2S-1-RIP.
Proof. The proof of this lemma can be adapted from that of [(Karnik et al. 2025). Lemma G.2] by introducing the inequalities || F S vil
||| and
|| = /1/k F.
Lemma 15. Suppose the linear map W1 R"xax + R satisfies 22) I-RIP with 82 E (0, 1), then M also satisfies vkōz-S2N--RRIP.
Proof. The proof of this lemma can be adapted from that of [[Karnik et al. 2025). Lemma G.3] by and
introducing the inequalities | S
Z
F v1/k| Z
Lemma 16. For tensor y Raxaxk with tubal-rank r, then we have
||||| S /nall ||X |r I vr||x1|,
|| r||
(115)
I EXTENSION TO THE GENERAL TENSOR
In this section, we provide a brief analysis for the extension to the asymmetric case by formulating the asymmetric model into a symmetric model. We first present the asymmetric tensor sensing model:
== (X) +
(116)
where X. K (X) ( X (B X .). X.Y] Under this asymmetric
model, we take asymmetric factorization X L * R L L Ruixek, R Re2xxxk, Then we define the symmetric measurement tensors C; E ( by:
0 B
C
(117)
2 B
and the corresponding linear map C: (( - R via
(C(2)); (C,, X).
Define
X
(x)
x
0
and
1
C,
3.
and E, = V2
22
R.
-R.
With these definitions, we then transfer the asymmetric sensing model into symmetric model:
22 ((sym( = (X)) and
1 C(2 2 - 2,) 27, (C, R.)).
22
With this model, we have the following objective function:
h(C, R.) = IX L: R. s11
(118)
Then we define the corresponding symmetric loss function:
hymm 2,, 2,, = [(((sy((X.)) Z, * 2, + 2, 2,) + V2sl?.
42

---

Published as a conference paper at ICLR 2026
Test ecror, small ini
Test spectaal ini
Train erzoc, small iui T Train emmos spectral ini Optimal
10a
Relalo Erour
10r2
10
200
400
2000
4000
6000
3000
Ierationns
Itamitoos
Figure 6: Comparison of training and testing errors for Problem (18 using FGD with spectral small initialization. The ground-truth tensor has tubal-rank 2. overestimated rank R 4, size n n2 = 20, & 3, m = 5kr(2n; r) measurements, and noise a = 10-3 Spectral initialization follows Liu al. (2024b), while small initialization uses a near-zero starting point. Training error is 211y-= Dt( C R I[ and testing error is C X 1/ x| x "Baseline" denotes recovery under exact rank R = r. Insets show early (first 500 iterations) vs. full error curves.
The gradient update of hym (Z,, 2,) is
2,+1 Z, n (sym (X.) Z, 2 2 2 e 2, x 2, 2,) + E* (v2x)) 2.
(119)
= 2. 2. n (
This formulation allows us to leverage some proof techniques from the symmetric case. However, handling the imbalance introduced by the two factor tensors poses significant challenge, and we are actively investigating this issue. Encouragingly, our experimental result Figure shows that the phenomenon described in this paper also persists in the asymmetric setting.
J ADDITIONAL EXPERIMENTS
J.1 SIMULATIONS ON DIFFERENT NOISE DISTRIBUTION
We conduct simulation experiments verify that our theoretical results remain valid under vari- ous noise distributions, not limited to Gaussian noise. The experimental setup is identical to that in Section 6, except that we replace the Gaussian noise with two types of sub-exponential noise: Laplace noise and exponential noise. We briefly introduce the two noise models considered in our experiments:
Laplace noise: The noise vector follows a Laplace distribution,
1
8:
Laplace(Jı, b), f(x:)
25 exp
which is symmetric sub-exponential distribution with mean ft and variance 262.
Exponential noise:
The noise vector follows an exponential distribution,
8 Exp(A), f(x) A Aeex(-As;), .s; 2 0,
which is an asymmetric sub-exponential distribution with mean 1/A and variance 1/X².
The results, shown in Figures and g demonstrate that under both noise types, FGD with small initialization achieves the same recovery error as in the exact tubal-rank case, even in the over- parameterized regime. This confirms that the guarantee provided by Theorem 2 extends beyond
43

---

Published as a conference paper at ICLR 2026
Gaussian distributions. Moreover, FGD with validation and early stopping yields errors that are very close to those in the exact tubal-rank setting, further validating the effectiveness of this approach and suggesting that the result in Theorem 3 can also be extended to sub-exponential noise.
10P
Baseline
Spectral ini
Large random ini
10
Small rundom (Sest))
Small
1/
Relatre Square Eroo
Ralative Error
10
10
10
Baseline
Spectral ini
madom
Small rundom (ES)
10a
10
15
20
25 30
30
10
(a)
(b)
Figure 7: Performance comparison under varying R, b with Laplace noise with μ = O. Subfigure (a) illustrates the recovery error of all methods under different over-rank values R, with parameters set as m = 5kr (2n r). n = 30, b 10-3, = 0.1, and = 5000. Subfigure (b) illustrates the error under varying noise levels b, with m 5kr(2n- r), 30. R 3r, 7) 0.1, and T 5000.
J.2 REAL-DATA EXPERIMENTS
In this section, we provide additional experimental details and results. We first present the algorithm used for the tensor completion task, as shown Algorithm 3 evaluation metrics, PSNR and relative eπrоr:
We then give the definitions of the
X
11 X X.
X X.IIF
PSNR 10 log10
RE
Xx111
where X, is the ground truth and X is the estimated tensor. Next, we briefly introduce the baseline methods used for comparison:
TNN (Lu et al.) 2018): classical convex method based on tubal tensor nuclear norm minimization proposed by O, widely used in tensor completion.
TCTF ZZou al. 2017): tensor factorization-basse method with tubal-rank estimation, designed to reduce computational cost.
UTF (Du et al., 2021): another tensor factorization method that replaces the tubal tensor
nuclear norm constraint with Frobenius-norm constraints on two factor tensors.
TC-RE (Shi et al. (02T): rank-estimation-basee method that first estimates the tubal rank and then performs tensor completion using truncated t-SVD.
GTNN-HOP, (Wang al. 2024): method that replaces the traditional TNN soft thresh- olding with a hybrid ordinary-I, Ip penalty for improved performance.
We conduct experiments both color image completion and video completion tasks, and compare our method with the above approaches.
J.2.1 COLOR IMAGE COMPLETION EXPERIMENTS
We perform color image completion experiments on the Berkeley Segmentation Dataset (Martin
al. 2001). We randomly select 50 color images of size 481 321 x 3 and the sampling
44

---

Published as a conference paper at ICLR 2026
10"
Baseline
Spectral in!
Small aidoo (best)
Large mindor inl
10"
nundor
10
Relalive Square Broze
Relittve Square Eator
10'0
10
10
10a
Baseline
Spectral Lis
Large randoms
Small random in (best)
Small random in (ES)
10a2
10
15 over
10
(a)
(b)
Figure 8: Performance comparison under varying R, À with exponential noise. Subfigure (a) illus- trates the recovery m 5kr r), n = 30, b = 10 0.1, À = 1000 and T 5000. Subfigure (b) illustrates the error under varying noise levels with m 5kr(2n r). 30, R T = 5000.
of all methods under different over-rank values R, with parameters set as
0.1, and
Algorithm Solving tensor completion by FGD with early stopping
Input:
Train data P (x, + Sa), validation data P (X, Sn), initialization scale a, step size estimated tubal-rank R, iteration number T
Initialization: Initialize Co, Ro. where each entry of Lo, Ro are i...d. from
(O, o²
1: for 1-=----00 = to T do
2:
C = C, 73 n
tain (C, R2 - X, -x, R,
3: RG+1 -R, 2 (L, # R
-n) C.
4: Validation loss: Gt = 2p
Bnn (L, * R.. X. Sm)
5: end for
6: Output: C; R. where i = arg min 1SST Ct-
45

---

Published as a conference paper at ICLR 2026
Table 3: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels. A higher PSNR and smaller RE indicates better reconstruction quality. "FGD-ES" denotes FGD with early stopping, while "FGD-best" refers to the minimum error achieved by FGD over all iterations.
0.3
p = 0.4
Methods
0.03
0.05
0.03
0.05
PSNR 1
RSE
PSNR f
RSE 4
PSNR 1
RSE +
PSNR 1
RSE +
UTF
7.8242
0.276
7.3535
0.2884
6.8286
0.3112
5.5376
0.3559
TNN
20.211
0.0659
17.2288
0.0934
20.4965
0.0639
17.1281
0.0947
TC-RE
19.7102
0.0698
16.9971
0.096
19.7435
0.0698
16.4039
0.1029
GTNN-HOP, p. 0.3
19.6553
0.0706
16.1069
0.107
20.0091
0.068
16.268
0.1051
GTNN-HOP... D.6
20.2583
0.0659
16.8056
0.0987
20.5764
0.0636
16.8933
0.0978
FGD-ES
22.083
0.0529
21.02
0.0597
22.2876
0.0517
21.5831
0.0559
FGD-best
22.1411
0.0525
21.1517
0.0588
22.3001
0.0516
21.7213
0.0551
rate as and add Gaussian noise .V(0,, a²). For TNN, UTF, TCTF, and GTNN-HOP, we adopt the initialization schemes and hyperparameter settings described in their original papers. The entry "FGD-best" refers to the highest PSNR obtained by FGD with small initialization, while "FGD-ES" corresponds to the PSNR achieved using early stopping based on validation. For both settings, the initialization scale is set to FGD-ES, FGD-best and UTF are set to 100 for all images. The max iteration number 2000. We present in Figures 9 12 the PSNR and RE values of different methods on each image under various model parameters (p, o).. )) In addition, Figure 13 shows the visual reconstruction results.
10-5 and the step size is set to = le - 3. The tubal-ranke of
We observe that FGD-best and FGD-ES achieve the best recovery performance in most cases. More- over, when the noise level increases, the performance of other algorithms degrades significantly, whereas FGD with small initialization is much less affected, highlighting the benefit of small initial- ization.
J.2.2 VIDEO COMPLETION EXPERIMENTS
Beyond image completion, we also performed video completion experiments with Gaussian noise. We randomly selected four videos from the YUV Video Sequences dataset extracted the first 30 frames of each to form tensors of size 176 x 144 x 30, added Gaussian noise drawn from (00, o²). and again applied sampling rate p. Since TCTF performs bad in the low sampling rate case of video completion, we replace it with GTNN-HOPo.s. a non-convex method with a sparsity-induccii inducing regularizer. For FGD-ES and FGD-best, the initialization scale set to 10-5 and the step size is set to 2e-4. 4. The tubal-ranks of FGD-ES, FGD-best and UTF are set to 50 for all images. The max iteration number is 4000. Tables 3 report the PSNR and RE values of all methods on the four videos, and Figure 14 shows the reconstruction results of the first frame of the akiyo video for each method. As can be seen, our method achieves the smallest relative recovery eиror and the highest PSNR values. In addition, we evaluated the robustness of FGD-best and FGD-ES with respect to the choice of the tubal rank The results, shown the Figure 15 demonstrate that both methods are highly robust to the selection of R across all four videos.
One potential issue that gradient- based methods are sensitive to the condition number of the underlying matrix tensor, leading to slower convergence when the condition number is large. Thus, developing methods that accelerate FGD while controlling the amplification noise remains an interesting direction for future research.
46

---

Published as a conference paper at ICLR 2026
FGDEES
FGD-best
TYN
GTNN
TCTF
UTF
TC-RE
0.20,
30
25
PSNR (d8)
204
15
+
30
Image Index
(a)
0.20 0.07
0.4
Relative Eror (RE)
0.3
0.2
2
D
Image index
(b)
Figure 9: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate p = 0.2 and noise standard deviation = 0.07.
Table 4: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels. higher PSNR and smaller RE indicates better reconstruction quality. "FGD-ES""" ES" denotes FGD with early stopping, while "FGD-best" refers to the minimum error achieved by FGD over all iterations.
0.3
p 0.4
Methods
0 0.03
0.05
σ 0.03
σ 0.05
PSNR 1
RSE L
PSNR 1
RSE
PSNR
RSE 1
PSNR
RSE |
TNN
20.7258
0.0613
17.4371
0.0895
21.0157
0.0592
17.3267
0.0906
TC-RE
19.928
0.0671
17.1895
0.0920
20.2059
0.0650
16.5464
0.0991
UTF
6.3467
0.3207
6.4038
0.3186
5.9414
0.3360
4.7523
0.3853
GTNN-HOP
19.9438
0.0670
16.1328
0.1039
20.2975
0.0643
16.2845
0.1021
GTNN-HOP
20.5461
0.0625
16.8126
0.0961
20.8648
0.0603
16.9083
0.0951
FGD-ES
23.2899
0.0456
21.6321
0,0552
23.8244
0.0429
22.3928
0.0501
FGD-best
23.4511
0.0448
21.8002
0.0541
23.8539
0.0427
22.5611
0.0496
47

---

Published as a conference paper at ICLR 2026
FGDIES
FGD-best
TCTF
RE
p 0.20, 0.10
25
PSNR (d8)
20
15
10
Image Index
FGD-ES
FGD-best
TNN
GTNN
0.20,
0.10
10a
Relatve Erro (RE)
10a
Image index (b)
Figure 10: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate p 0.2 and noise standard deviation 0.1.
Table 5: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels for the "highway" video. A higher PSNR and smaller RE indicates better reconstruction quality. "FGD-ES" denotes FGD with early stopping, while "FGD-best" refers to the minimum error achieved by FGD over all iterations.
p = 0.3
p=
0.4
Methods
0.03
0.05
0.03
0.05
PSNR 1
RSE 1
PSNR 1
RSE
PSNR 1
RSE 1
PSNR 1
RSE 1
TNN
19.4802
0.0474
16.9433
0.0635
19.8369
0.0455
16.8423
0.0642
TC-RE
19.0227
0.0499
16.6549
0.0656
19.1568
0.0492
16.1336
0.0697
UTF
4.0060
0.2814
3.7117
0.2911
1.1904
0.3891
0.7714
0.4084
GTNN-HOP
19.3115
0.0483
16.1687
0.0694
19.7269
0.0461
16.3390
0.0680
GTNN-HOP p.6
19.8894
0.0452
16.8541
0.0641
20.2802
0.0432
16.9568
0.0634
FGD-ES
20.6667
0.0413
20.0041
0.0446
20.7364
0.0410
20.3462
0.0429
FGD-best
20.7000
0.0412
20.1063
0.0441
20.7278
0.0410
20.4994
0.0421
48

---

Published as a conference paper at ICLR 2026
FGDIES FGD-best
TCTF
0.30,
0.07
PSNR (GB)
25
15
Image Index
FGD-ES
FGD-best
TNN
GTNN
0.30, 0.07
109
Relativ Emor (RE)
10a
Image index (b)
Figure 11: Comparison of PSNR values and Relative Error across 50 images for different methods,
with sampling rate p 0.3 and noise standard deviation 0.07.
Table 6: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels for the "suzie" video. higher PSNR and smaller RE indicates better reconstruction quality. "FGD-ES" denotes FGD with early stopping, while "FGD-best" refers the minimum error achieved by FGD over all itera-
tions.
p = 0.3
p
0.4
Methods
0.03
0.05
0.03
0.05
PSNR 1
RSE 1
PSNR 1
RSE
PSNR 1
RSE 1
PSNR 1
RSE 1
TNN
19.3458
0.0717
16.6844
0.0974
19.8125
0.0679
16.7441
0.0967
TC-RE
19.2177
0.0728
16.5983
0.0984
19.2186
0.0728
16.0643
0.1046
UTF
11.4879
0.1772
10.2100
0.2053
10.8456
0.1908
8.6211
0.2465
GTNN-HOP
19.0898
0.0738
15.7370
0.1086
19.5613
0.0699
15.9544
0.1059
GTNN-HOP p.6
19.6531
0.0692
16.4167
0.1005
20.0997
0.0657
16.5620
0.0988
FGD-ES
20.5670
0.0623
19.4874
0.0705
20.7175
0.0612
20.1540
0.0653
FGD-best
20.5947
0.0621
19.6263
0.0694
20.7445
0.0610
20.2629
0.0645
49

---

Published as a conference paper at ICLR 2026
FEDIES
FGD-best
TYN
GTMN
TCTF
UTF
TC-RE
p
30
25
PSNR (88)
20
15
39
Image Index
(a)
0.30, 0.10
0.4
Relative Emor (RE)
0.3
0.2
0.1
Image index (b)
Figure 12: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate p = 0.3 and noise standard deviation 0.1.
Ground Truth
TMN
GTNN
TCTF
UTF
TC-RE
CD-E8
GD-beel
RBE 600e de
RBE 6480 62
RSS 6:00
RSE 6:60
RBE 1.00 dn
RBE 7 77
RBS 7.4t
PSkit 25
PSNR
PSKR 21
PSkR 24
PSWR
PSKR
rsc + 7.30 03
RSS + 7.37--0
rSSe 11576-911
FSE 20w--
r1c + 6.100 10u-22
RSE 00e-52
nise + 3.00
11.00
PSWR 28 10
PSLR- 52
PSNR 24 RSF
PSKR 18-88
PokR 24
PSHR- 28
PONR 29
79%
RSF 07wes
000
RSF 6777-
Figure 13: Comparison of the image recovery performance of different methods under varying sampling rate p. The noise standard deviation 0.05. And 5% of the observed entries are used for validation.
50

---

Published as a conference paper at ICLR 2026
Table 7: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels for the "miss-america" video. A higher PSNR and smaller RE indicates better reconstruction quality. "FGD-ES" denotes FGD with early stopping, while "FGD-best" refers to the minimum error achieved by FGD over all iterations.
p 0.3
p
0.4
Methods
0 = 0.03
0
0.05
0 = 0.03
a 0.05
PSNR
RSE $
PSNR 1
RSE
PSNR 1
RSE 4
PSNR f
RSE $
TNN
21.2922
0.0831
17,8503
0.1235
21.3210
0.0828
17.5991
0.1271
TC-RE
20.6724
0.0892
17.5455
0.1279
20.3926
0.0921
16.8711
0.1382
UTF
9.4560
0.3245
9.0886
0.3386
9.3371
0.3290
8.0055
0.3835
GTNN-HOPo..
20.2760
0.0934
16.3891
0.1461
20.4505
0.0915
16.4938
0.1443
GTNN-HOPo..
20.9446
0.0865
17.1388
0.1340
21.0611
0.0853
17.1462
0.1339
FGD-ES
23,8085
0.0622
22.9563
0.0686
23.8721
0.0617
23.4395
0.0649
FGD-best
23.8186
0.0621
23.0738
0.0677
23.8743
0.0617
23.5618
0.0640
Original
Observed
UTF
TNN
GTNN HOP,
GTNN-HOP. HOP.
TC-RE
FGD-ES
RGD: best
0 0.003
pm 0.3
0.05
p- 0.4
0.03
0=44 0.4
0.05
Figure 14: Comparison of the video recovery performance of different methods under varying sam- pling rate and noise standard deviation for video "akiyo". For FGD-ES, 5% of the observed entries are used for validation.
51

---

Published as a conference paper at ICLR 2026
FGD-bes best:: PSNR
FGD best:
23
0.07
22.5
0.065
Relabre enor 1log scale)
PSNR (dB)
21.5
0.05
0.05
20.5
6
50
19.5
0.04
Video index (a)
Video index
(b)
FGD-ES: PSNR
FGD-ES: RE
23
0.075
22.5
Relatve eiror (loq scale)
0.065
PSNR (d8)
21
0.059
20.5
20
50
0.045
60
70
8 80
19
0.04
Video index
Video index
(C)
(d)
Figure 15: Evaluate the effect of different tubal-rank I on the performance of video completion. Subfigure (a) shows the PSNR values FGD-best on the four videos, and subfigure (b) shows corresponding RE values. Subfigure (c) reports the PSNR values of FGD-ES on the four videos, while subfigure (d) presents the associated RE values.
52


Reviews:
[{"review_id": "KTtam0RrgL", "reviewer": "Reviewer_Zuao", "summary": "This paper studies the problem of recovering a low-tubal rank tensor $X_*$ from its noisy linear measurements, $y = M (X_*) + s$. Focusing on the commonly used Burer-Monteiro factorization framework, it assumes that $X_*$ can be decomposed as $U * U^\\top$, and aims to minimize the quadratic loss function to recover $U$. The authors consider the fractorized gradient descent (FGD) method and attempts to derive upper bounds for the estimator error. A key challenge here is that the true tubal rank of $X_*$, denoted as $r$, is typically unknown, and error bounds in past work often depends on the over-estimated tubal-rank $R$.\n\nThe main contribution of this paper is to show that, both theoretically and empirically, using a small random initialization for FGD achieves a nearly minimax optimal estimation error, which only relies on the true tubal rank $r$, not the over-estimated tubal-rank $R$. To be specific: (i) Theorem 2 establishes estimator error bounds for early stopped FGD, under three different regimes of $r$ and $R$; (ii) Theorem 3 shows that the error bound of Theorem 2 is minimax optimal in the case of Gaussian noise; (iii) Finally, Theorem 4 shows that the early stopping time $t$ can be reliably chosen using sample spitting, thus giving a practical algorithm based on the theoretical results in Theorem 2 and 3.", "questions": "A few minor comments/suggestions for the authors:\n(i) \"CONDECOMP\" should be \"CANDECOMP\" in line 051.\n(ii) What is $R_n$ in Theorem 2, is it just $R$? Is it possible to state the choices of $\\alpha$ and $t$ only in terms of $R$, since $r$ is unknown?\n(iii) In line 216, perhaps it is better to replace $s$ as some other notation since $s$ denotes the noise in $y$.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The key findings of this paper, that the estimation error of FGD only depends on the true tubal-rank $r$, and that small initialization overcomes the dependency on the estimated rank $R$, are definitely interesting. The authors also compare their work with earlier results on the same topic to highlight their contributions, and include a proof sketch section to illustrate why FGD with small initialization works, which I really appreciate.", "weaknesses": "(i) The entire analysis replies on the T-PSD assumption on $X_*$, i.e., $X_*$ has the decomposition $X_* = U * U_*$. This is a significant simplification. The authors also acknowledge this limitation in Remark 5 and discussed a bit about extensions to general asymmetric case in Appendix I.\n(ii) Although the error bounds in Theorem 2 does not depend on $R$, the initialization scale $\\alpha$ and early stopping time $t$ depends on $R$. Further, in case 3 it seems to me that we can take $R$ to be so large that $\\alpha$ and $t$ are close to $0$, which is quite counterintuitive. Could the authors clarify more on this? This is very important since the error bounds in this paper improves on previous results only in the case $R \\geq 3r$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nzfH05c4Y3", "reviewer": "Reviewer_wQhQ", "summary": "The paper analyzes the optimization dynamics of factorized gradient descent (FGD) for low tubal rank tensor recovery, which is based on the quite recent t-SVD for tensors.  The authors prove that using a small random initialization for FGD together with suitable early stopping of FGD leads to a minimax optimal estimator, under an RIP-type condition.  The authors include synthetic experiments that validate the theory.  Overall, this is a quality submission.  I would be open to *raising* my score if the authors addressed a couple of my concerns in the Weaknesses section below with their rebuttal.", "questions": "Line 60-61: The authors write \"Under the t-SVD framework, since problem (2) is NP-hard, a common approach is to relax the tubal-rank constraint to the tensor nuclear norm.\"  Is it actually known that the low tubal rank recovery problem (2) is NP-hard?  What is a reference?  This wouldn't be in Hillar-Lim's paper, for instance.  \n\nLine 60-61: The authors should perhaps also say \"tubal tensor nuclear norm\", and provide a reference for its definition.  My understanding is that the authors mean the sum of singular values from the t-SVD, rather than the tensor nuclear norm as related to the CP decomposition.  That latter tensor nuclear norm is NP-hard to compute.\n\nLines 70-72: Would using the ansatz $\\mathcal{A} = \\mathcal{U} \\ast \\mathcal{U}^{\\top}$ imply symmetry and/or some sort of positive semi-definiteness in $\\mathcal{A}$?  If so, the authors should be explicit about these assumptions on $\\mathcal{A}$.  To me the natural low-rank ansatz would be $\\mathcal{A} = \\mathcal{U} \\ast \\mathcal{V}^{\\top}$ where $\\mathcal{U}$ need not equal $\\mathcal{V}$.\n\nLine 131: In the caption of Table 1, start the second sentence as \"The noise vector...\", i.e. please drop the leading \"And\".\n\nLine 202: Explain better what the block diagonal matrix $\\bar{Y}$ is.\n\nLines 240-269: In Theorem 2, item 1, is this bound true for all $t \\geq t_1$?  If not, and the error can increase later on, how about formulating item 1 with $\\hat{t}$ as you do with items 2 and 3 in Theorem 2?\n\nSection 4: It would be appreciated if the authors included a real data experiment.\n\nGeneral question: How do the results in this work relate to results for factorized gradient descent with just matrices and matrix SVD, rather than with tensors and t-SVD?  Are there parallel results in the matrix case?  How do the results here compare?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The optimization dynamics are interesting and not so intuitive.  In particular, the authors find that small random initialization is better than smart spectral initialization for this problem.  Further, FGD exhibits non-monotonicity with respect to error with the ground-truth; therefore, early stopping is needed.\n\n- The technical strength of analysis in this paper seems impressive. \n\n- The authors confirm their results also through numerical simulations.  Random small initialization and early stopping indeed improve the estimated tensor in experiments.", "weaknesses": "- It is unclear whether the factored form of the tensor used by the authors imposes symmetry and/or psd constraints.  The authors use $\\mathcal{U} \\ast \\mathcal{U}^{\\top}$ as their ansatz for the low tubal rank tensor.\n\n- The relation to low rank matrix recovery (i.e., with matrices and matrix SVD, rather than with tensors and t-SVD) is not well-specified as far as I can tell.  The authors should comment on this.\n\n- There are no real data experiments.  Real data would be nice, because there are certain RIP assumptions in this work, and one wonders how well they capture real data situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "my7BgLdhH2", "reviewer": "Reviewer_svxt", "summary": "This paper investigates low-tubal-rank tensor recovery from noisy linear measurements using the t-product framework and analyzes the behavior of factorized gradient descent (FGD) under over-parameterization. The authors show that small initialization and early stopping can significantly reduce recovery error independent of the over-estimated tubal rank, with both theoretical guarantees and empirical validation.", "questions": "See the Weaknesses.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The main contribution of this paper lies in providing an error bound for low-tubal-rank tensor recovery when the tubal rank is overestimated in noisy settings, showing that FGD can still achieve reliable recovery.", "weaknesses": "1. The contribution of this work is incremental. Factorized Gradient Descent (FGD) is not an original contribution of this work (see [1]). Similarly, the use of early stopping to avoid overfitting is a standard practice and cannot be regarded as an innovation here. \n[1] Z. Liu, Z. Han, Y. Tang, X. -L. Zhao and Y. Wang, \"Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent,\" in IEEE Transactions on Signal Processing, vol. 72, pp. 5470-5483, 2024\n\n2. The relationship with [1] should be discussed in detail rather than mentioned only briefly.\n\n3. Please provide a careful comparison with `Implicit Regularization for Tubal Tensors via GD' and A Validation Approach to Over-parameterized Matrix and Image Recovery'', particularly focusing on the technical tools employed in the proofs.\n\n4. The main motivation of this work is that traditional algorithms often use a higher rank than the true rank. However, in most practical applications (e.g., image and video recovery), the true rank is unknown. What really matters is which estimated rank leads to better recovery performance—and in many cases, such rank estimates are not unique. A thorough discussion and empirical comparison in real-world scenarios are therefore necessary. At present, the paper includes only one example on a single color image and lacks broader discussion of practical implications.\n\n5.Over the past five years, many tensor decomposition methods with rank estimation strategies have been proposed. Since this work is motivated by the problem of overestimated rank, it should include comparisons and discussion of rank-estimation-based approaches, such as the following:\n\n[2] Q. Shi, Y.-M. Cheung, and J. Lou, “Robust tensor svd and recovery with rank estimation,” IEEE Transactions on Cybernetics, 2021.\n\n[3] Zheng, J., Wang, W., Zhang, X., & Jiang, X. (2023). A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation. arXiv preprint arXiv:2305.11458.\n\n[4] Zhu Q, Wu S, Fang S, et al. Fast tensor robust principal component analysis with estimated multi-rank and Riemannian optimization[J]. Applied Intelligence, 2025, 55(1): 52.\n\n6. Beyond Implicit Regularization for Tubal Tensors via GD, no other recent tensor decomposition methods (from the last five years) are compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wZHv4Qzf0y", "reviewer": "Reviewer_SVNR", "summary": "This paper investigates the problem of recovering a noisy low-tubal-rank tensor model. Specifically, it studies the theoretical guarantees of the gradient descent method with small initialization for solving a low-rank recovery problem formulated via the Burer–Monteiro factorization under the t-product framework. The authors prove that when the dimensions of the optimization variables match the ground-truth rank, the algorithm enjoys a linear convergence rate. They further provide error estimates under different levels of over-parameterization, showing that the final recovery error depends only on the noise scale as the iteration proceeds. Furthermore, the paper proposes a practical stopping criterion and establishes the corresponding recovery error bound under this termination condition. Numerical experiments demonstrate that the small-initialization gradient descent method achieves superior recovery performance compared with those initialized randomly or by spectral methods.", "questions": "- In the matrix case, the model obtained via the Burer–Monteiro (BM) factorization is nonconvex and may contain spurious local minima. For the tensor case studied in this paper, do similar spurious local minima exist? If so, what guarantees that the proposed gradient descent iterates will not converge to such undesirable local minima?\n\n- In the proof sketch of Theorem 2, the authors mention that the iterates undergo four different stages, during which the singular values of the iterates exhibit distinct behaviors. It would be interesting and instructive to design numerical experiments that illustrate these four phases and verify their correspondence with the theoretical analysis.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well structured and clearly written, particularly on the mathematical side. The main results are rigorously proved and thoughtfully discussed. The authors also provide useful comparisons with existing works, which helps position their contributions within the current literature. The topic—low-tubal-rank tensor recovery—is timely and important, as tensor models have recently attracted significant attention due to their complex structures and broad applications. Moreover, the analysis of over-parameterization is of great interest, and the finding that the recovery error depends only on the noise scale is both elegant and encouraging.", "weaknesses": "Although this paper studies the tensor case, the introduction and background on tensor are relatively limited, which reduces the readability for a broader audience. To improve accessibility, it would be helpful to include more definitions and explanations—such as the t-product and the corresponding notion of tensor rank—in the appendix, given the space limitations of the main text.\n\nAnother concern is that, as mentioned in Remark 7, the results of this paper can be viewed as a direct extension of the matrix case studied in [Ding et.al., 2025]. If one interprets the tensor in this paper as a matrix and the t-product as standard matrix multiplication, it is not immediately clear how the theoretical analysis differs from the matrix setting. The paper would benefit from a more explicit discussion highlighting the distinctive challenges or techniques specific to tensors, which would not only improve readability but also strengthen the contribution of the work.\n\nFinally, Remark 7 might be placed earlier in the text, since both Theorem 2 and its proof sketch are quite similar to those in [Ding et.al., 2025], not only the proposed stopping strategy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)