Implicit Regularization for Tubal Tensor Factorizations via Gradient Descent
Authors: Santhosh Karnik
Anna Veselovska
Mark Iwen
Felix Krahmer
Venue: ICML 2025 oral (2025)
Keywords: overparameterization
implicit regularization
tensor factorization
Primary area: theory->learning_theory
TL;DR: We provide a rigorous analysis of implicit regularization in an overparametrized tensor factorization problem beyond the lazy training regime.

Abstract: We provide a rigorous analysis of implicit regularization in an overparametrized tensor factorization problem beyond the lazy training regime. For matrix factorization problems, this phenomenon has been studied in a number of works. A particular challenge has been to design universal initialization strategies which provably lead to implicit regularization in gradient-descent methods. At the same time, it has been argued by Cohen et. al. 2016 that more general classes of neural networks can be captured by considering tensor factorizations. However, in the tensor case, implicit regularization has only been rigorously established for gradient flow or in the lazy training regime. In this paper, we prove the first tensor result of its kind for gradient descent rather than gradient flow. We focus on the tubal tensor product and the associated notion of low tubal rank, encouraged by the relevance of this model for image data.  We establish that gradient descent in an overparametrized tensor factorization model with a small random initialization exhibits an implicit bias towards solutions of low tubal rank.  Our theoretical findings are illustrated in an extensive set of numerical simulations show-casing the dynamics predicted by our theory as well as the crucial role of using a small random initialization.

Implicit Regularization for Tubal Tensor Factorizations via Gradient Descent
Santhosh Karnik
Anna Veselovska
23
Mark Iwen 45 Felix Krahmer 2.3
Abstract
overparametrization can give rise to superior generalization capability and lead to strong overall NN performance. Con- sequently, there has been a recent surge in research aimed explaining how gradient-based methods interact with over- parameterized models under nonconvex losses (see, e.g., (Ma et al. 2018 Ling & Strohmer, 2019)). Notably, re- cent empirical and theoretical studies have suggested that gradient- based methods with small random initializations exhibit a bias towards low-rank solutions in a variety of models.
We provide a rigorous analysis of implicit regu- larization in an overparametrized tensor factoriza- tion problem beyond the lazy training regime. For matrix factorization problems, this phenomenon has been studied in number of works. A par- ticular challenge has been to design universal ini- tialization strategies which provably lead to im- plicit regularization in gradient-descent methods. At the same time, it has been argued by (Cohen ct al.) 2016) that more general classes of neural networks can be captured by considering tensor factorizations. However, in the tensor case, im- plicit regularization has only been rigorously es- tablished for gradient flow or in the lazy training regime. In this paper, we prove the first tensor result of its kind for gradient descent rather than gradient flow. We focus on the tubal tensor prod- uct and the associated notion of low tubal rank, encouraged by the relevance of this model for im- age data. We establish that gradient descent in an overparametrized tensor factorization model with small random initialization exhibits an implicit bias towards solutions of low tubal rank. Our the- oretical findings are illustrated in an extensive set of numerical simulations show-casing the dynam- ies predicted by our theory as well as the crucial role of using small random initialization.
For matrix factorization models which represent linear neu- ral networks, rigorous analysis of implicit bias is available for both gradient descent (Gunasekar et al. 2018 Stöger & Soltanolkotabi (222]) and gradient flow (its asymptotic limit for small step size) (Bah et al.] 2022 Chou et al. 2024). In contrast, for neural networks with nonlinear activation, there has been a good deal of work done showing that fully connected layers can be represented by, e-g., tensor train fac- torizations in (Novikov et al. 2015 Razin et al. 2021). As consequence, it has been argued that tensor factorizations should be considered instead of matrix factorizations (see, e.g., CChhe et al. 2016)). For tensor factorization models, however, results predating 2024 were only available for the asymptotic regime, i.e., gradient flow. This perhaps due to the many additional complications in the tensor setting be- yond those in the matrix setting including, e.g, that there many different valid notions of tensor rank, each of which motivates its own equally valid class of tensor factorizations. For gradient descent applied to the tensor recovery problem, only a very recent partial analysis by (Liu et al. 2024) cur- rently exists for the tubal factorization model. This analysis requires that the initialization already well approximates the solution, only after which the convergence of gradient descent toward a low tubal-rank solution is shown. Herein we also focus the tubal factorization, but establish the corresponding implicit regularization result without needing such a strong initialization assumption.
1. Introduction
Analyzing implicit regularization during Neural Network (NN) training is considered crucial for understanding why
'Equal contribution 'Department of Mathematics. Northeast- em University. Boston, USA 'Department of Mathematics and Munich Data Science Institute, Technical University of Munich, Munich, Germany MMnich Center for Machine Learning, Mu- nich. Germany "Department of Mathematics, Michigan State University, East Lansing, USA 'epaarmennt of Computational Mathematics Science and Engineering, Michigan State Univer- sity, East Lansing, USA. Correspondence to: Anna Vesclovska <anna. weselovska@ttum...c
Our work is motivated by recent research showing that the way neural networks are trained, especially with gradient de- scent, can lead to solutions with useful structure, even with- out adding explicit regularization terms. This phenomenon, known as implicit regularization, has been studied in con- texts such as sparse recovery (Vaskevicius et al. 2019) and low-rank matrix completion (Li ct al. 2020), where specific
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Implicit Regularization for Tubal Tensors via GD
network architectures are designed to encourage certain types of structure in the solutions. However, for tensor re- covery problems, most existing work either focuses only on gradient flow or provides only partial analysis. To the best of our knowledge, our paper is the first to analyze implicit bias under gradient descent with small random initialization for a tensor recovery problem. We focus on the tubal rank model, which particularly relevant for applications like video representation. This opens the door broader in- vestigation into how implicit regularization can be used for structured tensor recovery, how network architectures influ- ence this bias, and what conditions ensure convergence. We see this work as a starting point for a larger line of research on implicit regularization in tensor problems.
Strohmer, 2019 Candes et al. 2013); and landscape anal- ysis paired with saddle-sscaping algorithms which show, e.g., that all local minima are global and that saddle points exhibit strict negative curvature so that (stochastic) gradient- based methods can effectively escape saddles and ensure convergence to global minimizers (Jin et al. 2017: Ge et al. 2015 Raginsky et al. 2017).
Notably, several studies (Woodworth et al. 2020 Ghorbani et al. 2020 have highlighted the importance of the scale of the training initialization for the generalization and test performance of modern machine learning architectures. In fact, a small random initialization followed by (stochastic) gradient descent is arguably the most widely used train- ing algorithm in contemporary machine learning. And, stronger generalization performance is typically observed with smaller-scal initializations. Implicit bias for low-rank matrix recovery with small random initializations has been extensively studied in this setting as result by, e.g.. (Stöger & Soltanolkotabi, 22221 Soltanolkotabi et al. [2023 Wind 2023 Kim & Chung 2024). These studies have shown that
Related work: In deep learning it is common to use more network parameters than training points. In such overpa- rameterized scenarios there are usually many networks that achieve zero training error so that the training algorithm effectively imposes an implicit regularization (bias) on the solution it computes. In practice. training networks with gra- dient descent is both common and tends to favor solutions that generalize well, offering the exploration of how gradient descent implicitly regularlizes in overparameterized regimes as one avenue for better understanding the success of deep learning more widely. As a result, a lot of recent work has been focussed on understanding the implicit regularization phenomena of gradient descent in multiple settings. The first theoretical works in this direction (Gunasekar et al. Geyer et al., 2020 Arora et al. 2019 (Soudry jct al. 2018 concentrated on training linear networks and suggested that during training (stochastic) gradient descent implicitly converges to linear network (i.e., a linear func- tion described by a matrix) that's low rank. Motivated by specific deep learning tasks, multiple works also investi- gated implicit bias phenomena in the special cases of sparse vector and low-rank matrix recovery from underdetermined measurements via an overparameterized square loss func- tional, where the vectors and matrices to be reconstructed were deeply factorized into several vector/matrix factors. In this setting, these works then showed that the dynamics of vanilla gradient descent are biased towards sparse/low-rank
small random Gaussian initialization behaves similarly to spectral initialization in overparameterized settings, Fur- thermore, they have shown that gradient descent algorithms with this initialization tend to converge towards low-rank so- lutions (i.e., that they demonstrate an implicit regularization towards low-rank solutions).
Recently, numerous connections between tensor decompo- sitions and training neural networks have also been estab- lished by, e.g., (Novikov et al., 2015 Razin et al. 2021 2022 These studies argue that low-rank tensor factoriza- tion helps explain implicit regularization in deep learning, as well as how properties of real-world data translate this regularization to generalization. Similar to how matrix fac- torization can be viewed as a linear neural network (i.e., a fully connected network with linear activation), tensor fac- torizations correspond to a specific type of shallow (depth- two) nonlinear convolutional neural network (Cohen et al.) 2016 Razin et al.] (021). Additionally, (Novikov et al. 2015) demonstrated that the dense weight matrices of fully connected layers can be converted to tensor trains while preserving the layer's 's expressive power. These findings have positioned low-rank tensor factorizations as theoreti- cal surrogates for various neural network learning settings, thereby enhancing our understanding of implicit regulariza- tion and overparameterizztioo, and so further motivating investigation in this area.
2017:
2018
solutions, respectively (Chou et al., 2024 2023 Li et al. 2022 Kolb et al. 2023).
In the realm of optimization, a substantial body of work has also emerged that provides guarantees for gradient descent's convergence in the nonconvex setting for different problems such phase retrieval, matrix completion, and blind decon- volution. Broadly, these findings can be categorized into two main approaches: smart initialization coupled with lo- cal convergence (demonstrating, e.g., local convergence of descent techniques starting from carefully designed spectral
Since no unique definition of tensor rank is available, related literature concerning implicit bias has naturally split with respect to the notion of tensor rank being considered: CP- rank, Tucker-rank, and tubal-rank, in analogy to the analysis of algorithms specifically designed for tensor recovery and
completion by, e.g., (Zhang et al.) 2019 Hou et al. 2021
initializations) (Ma et al. 2018 Tu et al.) 2016 Ling &
2

---

Implicit Regularization for Tubal Tensors via GD
specifically, we consider tensors of the form X'Xx'' and em- ploy a non-convex method based on the tensor factorization, minimizing the loss function using gradient descent with a small random initialization. To the best of our knowledge, we are the first to investigate the implicit bias phenomenon for gradient descent with a small random initialization ap- plied to a tensor factorization. Namely, we demonstrate that, irrespective of the degree of overparameterization. vanilla gradient descent with a small random initialization applied to a tubal tensor factorization will consistently converge to low tubal-rank solution.
m
m
m
Figure I: A low tubal-rank factorization of a three- dimensional tensor. Using the (reduced) tubal-SVD, each three-dimensional tensor T E Rnxmxx can be decomposed into a tubal product of three tensors T V * Σ> + W with W E mxxx and the frontal slice diago- nal tensor Σ E Rnxmxk Here, the tubal rank of tensor is the number of non-zero singular tubes in Σ E m For example, in the figure, the tubal rank of the tensor is equal to six.
Inspired by recent results for the low-rank matrix sensing problem by (Stöger & Soltanolkotabi 2021), ) we establish that gradient descent iterates with small random initializa- tions can be closely approximated by power method itera- tions in (Gleich et al., 2013 Kilmer et al.] 2013) modulo normalization, and deduce that after sufficient time the iter- ates approach a commonly used spectral initialization from the tubal-rank literature in (Liu et al. 2024). Along the way we must also overcome, e.g., a challenging intersection be- tween the tensor slices during each gradient descent iterate which forces a non-trivial convergence analysis.
V E Raxaxk,
Kong et al. 2018 Ahmed et al. 2020 Liu et al. 2019: 2020
Haselby et al. 2024). For the CP-tenso factorization, sev- eral results are available for gradient-based methods (Wang iet al. 2020; Ge & Ma (017). The first theoretical analysis of implicit regularization towards low tensor rank under arbitrarily small initialization was provided considering gra- dient flow in (Razin et al. 202T). In (Ge et al. 2015). it has been shown for the orthogonal tensor decomposition prob- lem a simple variant of the stochastic gradient algorithm is able to leverage a low-rank structure from an arbitrary starting point. In addition, (Wang et al. (222) shows that using gradient descent on an over- wver-parametrized objective for the CP-rank tensor decomposition problem one could go beyond the lazy training regime and utilize certain low-rank structures.
In Section 2 we define our notation and present a few basic facts regarding tubal tensors. In Sec- tion we state our problem and our main result. In Sec- tion we outline the steps of the proof in order to provide intuition. In Section [ we show numerical experiments which demonstrate our theoretical findings. We conclude the paper in Section 6 The proof of our main result is bro- ken up into several lemmas, which are stated and proven in the appendix.
Organization:
2. Notation and Preliminaries
Perhaps most closely related to this paper, very recently (Liu et al., 2024) analyzed the convergence of factorized gradient descent for the low-tubal-rank sensing problem, showing that with carefully designed spectral initialization the gradient iterates converge
Every tensor in this paper will be an order-3 tensor whose third mode is length &. For such a tensor T E mxxx, we define diogo-aa Fourier domain representation by
T = blockdiaggT (T()
(()) Cmkxnk
low-tubal rank tensor. Although the authors in (Liu et al., 2024) allow for over- parametrization, they argue the minimal recovery error can be achieved when knowing the true rank. thereby leaving questions concerning the advantages of overparametrizztion and small random initializations open.
where the j-th block 7(1) E C is defined by 700) (t, = Et other words, we take the FFT of each tube, and then arrange the resulting frontal slices into block-diagonal matrix.
In
The tubal product (or t-product) of two tubal tensors A Rmxqxk and B E Roxaxk is a tubal tensor A * B E Ruxnxk whose tubes are given by
Our contribution: Motivated by connections between tensor rank and non-linear neural network representations, herein we study the implicit regularization phenomenon for low tubal-rank tensor recovery. Namely, our objective is to analyze the recovery process of a tensor with a low tubal- rank factorization (Kilmer& & Martin [011] (see Fig 1) from a limited number of random linear measurements. More
(A, A(bp.) LAB B(p, p=1
Here, denotes the cireular convolution operation, i.e., (a:
3

---

Implicit Regularization for Tubal Tensors via GD
y): Σラ= Wigli-g (mod k)- One can check that A B AB
measurements of X' X² that is
y/s y= (A, A x
for i= 1, 1=.....,
(3.1)
For any tubal tensor T E Rmxnxk its tubal transpose I E Ruxmxk is given by (T (1, = T and (T),), = ((',, T i, + -
where each A, E 5nxnxk is a tubal-symmetric tensor. We can write this compactly as y = A(X X where A Suxnxk + R the linear measurement operator. We aim to recover X' X from our measurements y by using gradient descent to learn an overparameterized factorization. Specifically, we fix an R 2 and try to find all E IR" fx such that U * 2 = X * X by using gradient descent to minimize the loss function
i.e,, take the transpose of each face, and then reverse the order of frontal slices 2..... TT=T!
...., k. This ensures that
For any n, the n x n x & identity tensor E Raxxxk defined by I(: Laxn (identity matrix), and It: )i Onxn (zero matrix). An orthogonal tensor Q E Ruxxxk satisfies @* 2
@T=Q 2 I. An orthonormal tensor W E Rmmxnx with m 2 n satisfies W * W =
((U) : = A (u (u= - -0112
(3.2)
m
Σ (A xuT) -1)) i=1
The tubal-SVD (Kilmer & Martin 2011) (or t-SVD) of a tubal tensor T E [mxxx is a factorization the form
(3.3)
T= +* V
(2.1)
We will start with a small random initialization Uo RexRxk where each entry is i...d. (N % for some small
where 44 E mmmxx and V E Ruxxxk are orthogonal, and each frontal slice of E E m is diagonal. The t-SVD of tensor E Rmxnxx can be computed as follows: (1) compute the FFT of each tube of T to get the frontal slices 7(), .j = I,...kk k. (2) compute the SVD of each resulting frontal slice TÚ) TOT matrices
a > 0. Then, the gradient descent iterations are given by
U U, - vV((()))
U, + HAA -0- - A (u, (u,+ xtl,
= | A) (x
(x+x² x - -U, (44= Ur
(3) concatenate the ) j==1 into a tubal tensor i E Cmxmxk and take the inverse FFT along mode-3 to obtain UE E |Ruxmxk (and similarly to obtain Σ E Rmxxxk and V E R=xaxk). The tubal rank of a tensor T E mmxxx is the number of non-zero diagonal tubes in the Σ tensor of its t-SVD, i.e.,
(3.4)
for some suitably small stepsize 1 > 0. Here A' RT + Snxxxk denotes the adjoint of A which given by A²= = - A,A.
Moreover, we say that measurement operator A Smxaxk + R satisfies the Restricted Isometry Property (RIP) of rank-r with constant 5 > 0 (abbreviated RIP(r, 5)), if we have
rank(T (T) = # :)) A 0}. For illustration of the t-SVD decomposition, see Figure We also define the
condition number x(T) of the tubal tensor T E m
by
- 1-)0 S I1A S (1 1)
<< <TT) =
Omin(m,n) 3 ( (T)
for all 2 E Suxnxk with tubal-rank RIP condition is standard condition in the literature, and is used in similar works such as (Li et al. 2018 Stöger & Soltanolkotabi 2021). This condition is necessary to ensure that there is only one low tubal rank tensor for which the loss function is zero, and that this tensor could be recovered stably in the presence of noise.
We note that an
Finally, for tubal tensors T E Rmxaxk we define the tensor spectral norm |T| := IT| and the tensor nuclear norm IT : TI. as the spectral and nu- clear norm respectively of the block-diagonal Fourier do- main representation T, and the tensor Frobenius norm [T Em === Σt= [(,,j, 2)2 = I as a scaled version of the Frobenius norm of the block-diagonal Fourier domain representation T.
We have analyzed the convergence process of the gradient descent iterates (3.4) in the scenario of small ran- dom initialization and overparametrization. Namely, with the ground truth tensor X' E R we assume the ini- tialization Uo E xx is such that each entry is i.i.d. (0, a² R with small scaling parameter a > 0 and the sec- ond dimension R exceeding three timesthe ground truth dimension r. Below, we present the direct results of our analysis.
Results
3. Main Results
Problem Formulation Let X E Ruxrxk have tubal rank r < n so that X T E STxnnk is a tubal positive semidefinite tensor with tubal rank r. Let x = xxx) be the condition number of X. Suppose we observe m linear
4

---

Implicit Regularization for Tubal Tensors via GD
Theorem 3.1. Suppose we have m linear measurements y A(X' X of a tubal positive semideftnite tensor
constant of d = 0(x--111/2) one needs m 2 ( random
measurements.
X * X E STxuxk where X E Rnxxxx has tubal rank
Additionally, we acknowledge that the parameter depen- dence in Theorem 3.1 may initially seem unfamiliar. How- ever, it aligns well with intuition and prior work: when the tensor is ill-conditioned i.e., possesses a small tubal singu- lar value gradient descent without regularization naturally struggles recover the rank-one component unless the ini- tialization is sufficiently small. While our bound exhibits exponential dependence on the condition number, this is consistent with known results in the matrix setting (c.g., see Lemma 8.6 in (Stöger & Soltanolkotabi] 202I)).Althoul .Although the necessity of exponential dependence remains an open question, it presents a compelling direction for future re- search. Moreover, our numerical experiments (see Figure 4 support a polynomial relationship between the test error and the initialization parameter o, and while the empirical de- gree may differ slightly, our theoretical exponent 21 to closely approximate the observed behavior.
r W n. We assume A satisfies (2P + +16) with ó ex 1--1/_ Suppose we fit a model X X = U + 24 where U E RuxRxk with R 2 3r and obtain LA by running the gradient descent iterations
U++1 = =I++ xx* X u, x + +
with stepsize μ S cV/kx 11 starting from the initial- o²)
ization Us E guxRxx where each entry is i.i.d. NO, R Then, if the scale of the initialization satisfies
- 16x.
min (X) x2 min n, R) VK
Can²² In (minnnn, R}}
a
then after
16 appears
T p In Cn min (n, Ry
kr k(min n. R2 -r)
|| lcee
4. Proof Outline
iterations, we have that
In this section, we turn our attention to giving an overview of the key ideas of the proof.
1 U Xx*2 X"
||
In our analysis, we demonstrate that the trajectory of gradi- ent descent iterations can be approximately divided into two distinct stages: (I) a spectral stage and (II) a convergence stage described below.
21x²
21
L 3 32 16 (min (n, R} -))
Can² yn (miinnn.R)
a [|
T6
holds with probability at least 1 Cke ER. C, C2 > 0 are fixed numerical constants.
Here,
(I) The spectral stage. In the spectral stage, where show that the gradient descent starting from random initialization behaves similarly to spectral initialization, enabling to prove that by the end of this stage, the column spaces of the tensor iterates 24, (3.4) and the ground truth matrix X are sufficiently aligned. Namely, we show that the first few iterations of the gradient descent algorithm Ud can be approximated by the iteration of the tensor power method modulo normalization (see, e.g. (Gleich et al. 2013)) defined as
Intuitively, this means that if the initialization is sufficiently small, gradient descent will approximately recover the low tubal rank tensor X X after È iterations. Note that the reconstruction error can be made arbitrarily small by making the size of the random initialization a arbitrarily small. This comes at the expense of requiring more iterations. However, this impact is mild as the number of iterations grows only logarithmically with respect to a.
(I+ (I+ at * Uo E n
Although the above theorem holds for any R 2 3r, it is perhaps most interesting in the case where R 2 n as then every X x k tubal positive semidefinite tensor can be expressed as l * 24" T for some 24 E Rx Hence, the learner model does not assume that the ground truth tensor has low tubal rank, yet gradient descent is able to recover the ground truth tensor instead of any of the infinitely many high tubal rank tensors whose measurements match that of the ground truth tensor.
We call this part of the evolution of the gradient descent iteration the "spectral stage" since, due to its similarity to the power method, at the end of this stage the iterates Ui; will be closely aligned with the classical t-SVD spectral initialization of (Liu et al. 2024).
(II) The convergence stage. In the convergence stage, the gradient iterates converge approximately to the underlying low tubal-rank tensor X' X' at a geometric rate until reaching a certain error floor which is dependent on the initialization scale.
We note that (Zhang et al. 2019) shows that a random sub- Gaussian measurement operator A Raxnn - TM will satisfy the RIP for tubal rank-r tensors with RIP constant with high probability if m 2 O(rnk/83) To obtain an RIP
The cornerstone of the analysis of this stage is the de-
5

---

Implicit Regularization for Tubal Tensors via GD
denote by W E RRX( tensor whose tensor-
column subspace is orthogonal to those of Wt, that is IW w,ll = 0 and its projection operator Pw... is defined as Pw.. = W * W., = I W, * W.
IV & Vi,1l 11/TUy -x+X 1r
0.8
X+x"
We then decompose the gradient descent iterates 3.4 as follows
|o.1(1)-- (8ill
0.7
(X,,(X)ll
e(U,)
0.6
U, Ue * W. * W. + U₁ * Wi.1 * W
(4.1)
0.5
referring to the tensors U, * W. * W. as the signal term of the gradient descent iterates, and to the tensors U4 * W... W.,, as the noise term. The advantage of such a decomposition is that the tensor-column space of the noise term U; Wt,1 W is orthogonal to the tensor-column subspace of the ground truth X' allowing for rigorous analysis of the convergence process of the two components separately.
0.2
0.1
0
2000
6000 Number of Iterations (1)
4000
8000
10000
At the convergence stage, we show that symmetric tensor U.* * W; =u, built from the signal term converges to- wards the ground truth tensor X X whereas the spectral norm of the noise term 1 * We,i Il. stays small.
VV * Vz,l
VE,l
* V
0.7
Additional challenges in the tensor setting vs. matrix setting When coming from the matrix case to the tensor setting com, there are several important differences and challenges, which need to be carefully considered and are described below.
0.6
0.5
0.2
In contrast to the matrix case, the range and kernel of a third-order tubal tensor can include overlapping generator elements (we refrain from using the term basis, in the sense that knowledge of the multirank and complimentary tubal scalar of a tensor must be included to describe the range). Namely, if in the t-SV 2 of a symmetric tensor X the tensor Σ contains @ non-invertible tubes - tubes that have zero elements in the Fourier domain -, then there are q common generators for the range and the kernel of X. please see (Kilmer et al.) 2013) for more details. With this phenomenon, the decomposition (C.I) of the gradient iterates into signal and noise term is not available for non-invertible tubes, which is why we need to work with a more intricate notion of condition number.
0.1
2000
4000
6000
8000
10000
Number Iterations (1)
Figure 2: Illustration of (top figure) the two stages of gra- dient descent algorithm: the spectral alignment stage for 1 1 t H 3000 and the convergence stage 3000 $ and (bottom figure) more details on the alignment phase for the gradient descent progress. In the ground truth tensor X E Baxxxk, we set = 10, k 4,r=3 3.
composition of the tensor gradient iterates Ue into two components, the so-called "signal" and "noise" terms. This is done by adapting similar decomposition methods used in recent works analyzing implicit bias phenomenon for gradient descent in the matrix setting (see (Stöger & Sootanolkooabi 2021] Li et al.) 2018)) to tensor set- ting. Accordingly, let the tensor-column subspace of the ground truth tensor X E Raxrxk be denoted by Vx with the corresponding basis Vx E Raxrxk Consider the ten- sor Vx * Uú E grxxRx with its t-SVD decomposition Vx U, = V.- E. W.T For W. E Rxrxk we
As stated in (Gleich et al., 2013), running the power method for tubal tensors of dimensions n x n is equivalent to running in parallel k independent matrix power methods in Fourier domain. However, running gradient descent in the tubal tensor setting is not equivalent to running k gradient descent algorithms independently in Fourier space. This can be easily seen when transforming the measure- ment operator part of the gradient descent iterates.
6

---

Implicit Regularization for Tubal Tensors via GD
Namely, let as before
y A(X xx) E ER'
10
R-
I-10 10
with Y/ A X
x
A2, X' x
-XXXX |r
Rt100
R-200
EØ=1
A 11) X X
j = 1,...m .. then
[ XX-X² 1
R=000
210
A * x) Suxaxk and the for j-th slice in the Fourier domain, we get A-A(X xT) Σ EE T, ( X This means that in each Fourier slice U, of the gradient descent iterates (3.4) we have the full information about the ground truth tensor X * X and not only about its j-th slice. In the spectral stage, this fact does not cause significant difficulties. However, in the convergence stage, in order get the global estimates, it requires thorough and vigilant analysis of intersections between the slices in the Fourier domain.
Ay(y) = Σ VAA, E
10% 1/0
1.7
1.4
1440
1460
1480
1500
10-
500
1000
1500
Number of Iterations
R-10
R-50
R-100
R 200
R=100
E(U
1
10
In particular, this required nontrivial estimations, such those presented in Lemmas E.4 and E.5, to control these interactions and provide the respective bounds, which require control of proximity of the auxiliary parameter (A* (A-A(XX' * x
6.5
10-3
1440
1450
1450
1500
500
1000
1000
Number of iterations
U, * U, (i) to the cor- responding jth Fourier slice of X * X -U,*U, via the RIP property of the measurement operator A and aligned matrix subspaces. Another important point is that one need to choose the learning rate μ and the initialization scale a carefully for the noise term U, WI. L. to grow slowly enough in each of the ten- sor slices in order to not allow overtaking the signal term U W, in the norm, see, e.g., Theorem E.1 and the usage of Lemma E.3 in its proof.
0.82
It-10
R-50
R-100
R-200
0.78
R 400
0.78
0.79
0.7
500
1000
1600
Number of Iterstions (1)
R-10
5. Numerical Experiments
R-50
R-100
[G 10.---.33 -x/3]] 2
R 200
To verify our theoretical findings, we set multiple numerical tests: from showing two phases of the gradient descent algo- rithm to demonstrating the advantages of overparametriza- tion. These experimental results showcase not only the implicit regularization for the gradient descent algorithm toward www-tubalranne tensors but also demonstrate the firm- ness of our theoretical findings.
10
R=000
[,
10
1440
1480
1450
1500
10"
600
1000
1000
Number of Iterations
Our experiments were conducted on MacBook Pro equipped with an Apple MI processor and 16GB of memory, using MATLAB 2023a software. The cor- responding code is available in our GitHub reposi- tory, htaps://giuub.co//Annaaaa http:/AAmmeeeeloaaaaAAAtaaaaaaa implicit-reg-GD.ee
Figure 3: Outcomes of employing gradient descent to mini- mize the loss function (3.2 with different overparametriza- tion rates. We set n = 10, k = 4, r = 3 in the ground truth tensor X E Raxrx and for initialization Uu E R.* Rxck we set the over-rank to R = 10, 50, 100, 400, 400. For each R. we plot the average over twenty experiments. The
We generate the ground truth tensor T E Raxnx with tubal rank by T X' * X where the entries of X' E R2xrxk are i.i.d. sampled from a Gaussian distri- bution (01 1), and then X' is normalized. The entries of measurement tensor A, are i.i.d. sampled from a Gaussian distribution N(0, 4.). In the following, we describe dif-
plots for [[4,, -x-X Ile E(U,) and [0..04.)--- are [x.(2))
xx*xx lle
semi-log plots.
7

---

Implicit Regularization for Tubal Tensors via GD
ferent testing scenarios for recovery of T via the gradient descent algorithm and their outcome. For all the experi- ments, we set the dimensions to = 10, k = 4, 3, the learning rate P = 10-5, and the number of measurements m = 254.
the ground truth tensor X' X T, and learning more about X' X leads to larger error in terms of principal angles of the two.
Depiction of the alignment stage. In this experiment, we illustrate that gradient descent with small initialization behaves similarly to the powwrr method modulo nor- malization in the first few iterations, bringing the gradient iterates close to the spectral tubal initialization, used, e.g., in (Liu et al.) (024). Here, as before L denote the tensor sub- space spanned by the tensor-columns corresponding to the first r singular-tubes of tensor A A X and L; is the tensor-columm subspace corresponding to the first r singular tubes U, *tt," Additionally, C. denotes the tensor-column subspace spanned by the first r singular-tuber of the ten- *f * Mo.
Illustration of the two convergence stages. To illustrate the convergence process of the gradient iterates, for the ground truth tensor X' * X Ruxnxk and its counter- part U4, U E R being learned by the gradient descent, we consider the training error E(U,), the test error [,, -x+ Ir_ and the test error for their rth singular |x
tubes (24),, (,))),,(()))) (X) E R [o-(M,)-a,xx(]l: Moreover, [|,,(X)
we also take into consideration the tensor subspace L spanned by the tensor-colume corresponding to the first and denote by C, the tensor-column subspace spanned by the tensor- columns corresponding to the first r singular tubes U4 =2t We note that although Theorem 3.1 bounded relative error with || 2 in the denominator, we use || X' || in the denominator of the relative error for our experiments as it is more natural relative error to consider. Furthermore, since | X' || 2 | and || X T || could be much larger than || in cases where the singular values of X * X² vary drastically, the result of Theorem 3.1 is stronger than if we bounded the more natural Frobenius norm error. Besides, the qualitative behavior in the numeri- cal simulation will be the same for the two error measures as generically they will just differ by a dimensional factor.
sor U, ū, where U, = A x)))
r singular-tubes of the tensor A'A((X' X
In Figure ] (bottom), we see that Ur and ú, learn the subspace L almost at the same rate in the first iterations, S t S 3000. In the same figure, we observe that also the angle between Vx x and L,, respectively L., decreases monotonically in the spectral stage. Then at the beginning of the convergence stage, 3000 S t, the angle between Vx and L, starts decreasing gradually and converges to zero, as expected since Ut * UU converges to X * X Whereas the principal angle between L and L, growths until it reaches a certain plateau.
10
train-error test-error .c- 21/11
5
Figures 2 demonstrates that the convergence analysis can be divided into two stages: the spectral and the convergence stage. We see that in the first stage (1 < t S 3000), the first r' tensor- consoos of U, U, learn the tensor column subspace corresponding to the first singular-tubes of the tensor A A(X' X ), i.e. the principal angle between the tensor column subspaces L, and L becomes small. Namely, as one can observe in Figure 2 (bottom), the principal angle between the two subspaces, || c * VVc,ll. Il. decreases where as the principal angle between X' and C, reaches certain plateau, see the behavior of V V., ll. At the same time, test errors ||U,= -x lee and (o.124,)---(x))) [o.1(2)]2
0-
-10
-15 10
10a4
10
10
Q'
X-X*I ||r
stay large. In the second stage, we see that the test error X.x starts decreasing, meaning that the gra- a4 Xx+X ||
Figure 4: Impact of different initialization scales on the test and the training error. The data are represented in the log-log plot. We set n = 10, k = 4. = 3 in the ground truth tensor X' E xx and for initialization Ut = atl E IRn Rxk with R = 200 and different scales of a. The plot depicts the averaged value for five runs and the bars represent the devi- ations from the mean value. For illustration, we also depict the theoretical test emrrr bound obtained in Theorem 3.1 As one can see, the numerical error resembles the theoretical behavior of Cr a at.
dient descent iterates Ui * UT, start converging to X x T by learning more about the tensor-column subspace of the ground truth tensor. At the same time, the test error over rth singular tube [|o- (2)ila starts decreasing too and (X))l as a result converges to zero. We also see that in this stage the principal angle between L, and C grows, which is also intuitive as the tensor-column subspace L does not have the full information about the tensor-column subspace of
8

---

Implicit Regularization for Tubal Tensors via GD
Test and train error under different scales of initializa- tion. In this experiment,
DMS 2108479 and NSF EDU DGE 2152014.
explore the influence of the initialization scale, denoted by a, on the training and the test error. With R = 200, we apply gradient descent for various values of a halting the iterations at / = 3500 in each run. The results, presented in Figure demonstrate a reduction test error as a decreases. Notably, the figure indicates that the test error follows an almost polynomial relationship with the initialization scale a. This observation is consistent with our theoretical predictions, which also forecast decrease in test error at a rate of (x, see Theorem 3.1.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning, and more specifically, the theoretical understanding of implicit regularization as a tool for struc- tured recovery problems. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Impact of different levels of overparameterization the convergence. In this numerical analysis, we set a = 10-7 and examined the convergence speed of gradient descent to the ground truth tensor for various overparameterization rates R. We run the experiment twenty times for each value of R. and plot the averaged values per each iteration. The results, shown in Figure 3] reveal that increasing the number of tensor columns Rt that is, overparameterizing, accelerates the convergence rate, resulting in fewer iterations to reach the desired error level. Additionally, overparameterization reduces the test error and the training error by affecting the spectral stages.
Ahmed, T., Raja, H., and Bajwa, W. U. Tensor regression using low-rank and sparse tucker decompositions. SIAM Journal on Mathematics of Data Science, 2(4):944-966 2020.
Arora, S., Cohen, N., Hu, W., and Luo, Y. Implicit regular- ization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Bah, B., Rauhut, H., Terstiege, U., and Westdickenberg, M. Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. Information and Inference: A Journal of the IMA, 11(1): 307-353, 2022.
6. Conclusion and Outlook
In this paper, we focused on studying the implicit regular- ization of tubal tensor factorizations via gradient descent by showing that with small random initialization and over- parametrization, the gradient descent algorithm is biased towards a low-tubal-raak solution. We have shown that the first iterations of gradient descent with small random initial- ization behave similarly to the tensor power method, which leads to learning in these first iterations the tensor-column spaces close to the tensor-colume space of the ground truth. We also demonstrate that the implicit regularization from small random initialization guides the gradient descent it- erations toward low-tubal rank solutions that are not only globally optimal but also generalize well.
Candes, E. J., Li, X., and Soltanolkotabi, M. Phase re- trieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 1085) 2015.
Chou, H.-H., Maly, J., and Rauhut, H. More is less: induc- ing sparsity via overparameterization. Information and Inference: A Journal of the IMA, 12(3):1437-1460, 2023.
Chou, H.-H., Gieshoff, C., Maly, J., and Rauhut, H. Gradi- ent descent for deep matrix factorization: Dynamies and implicit bias towards low rank. Applied and Computa- tional Harmonic Analysis, 68: 18:101195,, 2024.
Cohen, N., Sharir, O., and Shashua, A. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory, pp. 698-728. PMLR, 2016.
Acknowledgments
AV and FK acknowledge support by the German Science Foundation (DFG) in the context of the collaborative re- search center TR-109, the Emmy Noether junior research group KR 4512/1-1 and the Bavarian Funding Program for Initiating International Research Cooperation, as well as by the Munich Data Science Institute and Munich Cen- ter for Machine Learning. SK acknowledges support by the United States National Science Foundation in the con- text of the Foundations of Data Science Institute funded by grant NSF DMS 2022205. MI acknowledges support by the United States National Science Foundation grants NSF
Ge, R. and Ma, T. On the optimization landscape of tensor decompositions. Advances in neural information process- ing systems, 30, 2017.
Ge, R., Huang, F., Jin, C., and Yuan, Y. Escaping from sad- dle points- polits-online stochastic gradient for tensor decom- position. In Conference learning theory, pp. 797-842. PMLR, 2015.
Geyer, K., Kyrillidis, A., and Kalev, A. Low-rank regu- larization and solution uniqueness in werrpparameterized

---

Implicit Regularization for Tubal Tensors via GD
matrix sensing. In International Conference on Artificial Intelligence and Statistics, pp. 930-940. PMLR, 2020.
Li, Y., Ma, T., and Zhang, H. Algorithmic regularization in over-parameterizee matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pp. 2-47. PMLR, 2018.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33: 14820-14830, 2020.
Li, Z.,, Luo, Y., and Lyu, K. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint wrXiv:201.009839 2020.
Gleich, D. F., Greif, C., and Varah, J. M. The power and armldi methods in an algebra of circulants. Numerical Linear Algebra with Applications, 20(5):809-83) 2013.
Li, Z., You, C., Bhojanappalli, S., Li, D., Rawat, A. S., Reddi, S. J., Ye, K., Chern, F., Yu, F., Guo, R., et al. The lazy neuron phenomenon: On emergence of activation sparsity in transforerrs. arXiv preprint arXiv:2210.06313. 2022.
Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix factorization. Advances in neural information processing systems, 30, 2017.
Ling, S. and Strohmer, T. Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing. Information and Inference: A Journal of the IMA, 8(1):1-49,201
Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Im- plicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems, 31, 2018.
Liu, X.- Y., Aeron, S., Aggarwal, V., and Wang, X. Low- tubal-rank tensor completion using alternating minimiza- tion. IEEE Transactions on Information Theory, 66(3);
Haselby, C., Iwen, M., Karnik, S., and Wang, R. Tensor deli: Tensor completion for low ep-rank tensors via random sampling, 2024.
1714,773,, 2019.
Hou, J., Zhang, F., Qiu, H., Wang, J., Wang, Y., and Meng, D. Robust low-tubal-ree tensor recovery from binary measurements. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(8):4355 4373, 2021.
Liu, X.-Y., Aeron, S., Aggarwal, V., and Wang, X. Low- tubal-rank tensor completion using altemattng minimiza- tion. IEEE Transactions on Information Theory, 66(3): 1734-1737, 2020. doi: 10. 10.1109/TT1201992599998
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. How to escape saddle points efficiently. In Interna- tional conference on machine learning. pp. 1724-1732. PMLR, 2017.
Liu, Z., Han, Z., Tang, Y., Zhao, X.-L., and Wang, Y. Low- tubal-rank tensor recovery via factorized gradient descent. arXiv preprint arXiv:2401.
2024.
Ma, C., Wang. K., Chi, Y., and Chen, Y. Implicit regulariza- tion in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix comple- tion. In International Conference on Machine Learning, pp. 3345 3354.. PMLR, 2018
Kilmer, M. and Martin, D. Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):641166) 2011.
Kilmer, M. E., Braman, K., Hao, N., and Hoover, R. C. Third-order tensors as operators on matrices: A theoret- ical and computational framework with applications in imaging. SIAM Journal on Matrix Analysis and Applica- tions, 34(1):148-172, 2013.
Novikov, A., Podoprikhin, D., Osokin, A., and Vetrov, D. P. Tensorizing neural networks. Advances in neural infor- mation processing systems, 28, 2015.
Raginsky, M., Rakhlin, A., and Telgarsky, M. Non-convex
Kim, D. and Chung. H. W. Rank-1 matrix completion with gradient descent and small random initialization. Advances in Neural Information Processing Systems, 36, 2024.
learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning The- ory, pp. 1674-1703. PMLR, 2017.
Kolb, C., Müller, L., Bischl, B.. and Rügamer, D. Smooth- ing the edges: A general framework for smooth opti- mization in sparse regularization using hadamard over- parametrization. arXiv preprint urXiv:2307.03577 2023.
Razin, N., Maman, A., and Cohen, N. Implicit regulariza- tion in tensor factorization. In International Conference Machine Learning, pp.
PMLR, 2021.
Razin, N., Maman, A., and Cohen, N. Implicit regulariza- tion in hierarchical tensor factorization and deep convolu- tional neural networks. In International Conference on Machine Learning, pp. 18422-18466 PMLR, 2022.
Kong, H., Xie, X., and Lin, Z. t-schatten-p norm for low- rank tensor recovery. IEEE Journal of Selected Topics in Signal Processing, 12(6): 226):1405-1111 405-1419, 2018
10

---

Implicit Regularization for Tubal Tensors via GD
Rudelson, M. and Vershynin, R. Smallest singular value of random rectangular matrix. Communications Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739, 2009.
Zhang, F,, Wang, W., Hou, J., Wang, J., and Huang, J. Tensor restricted isometry property analysis for large class of random measurement ensembles, arXiv preprint WrXi::996600199, 2019.
Soltanolkotabi, M., Stöger, D., and Xie, C. Implicit bal- ancing and regularization: Generalization and conver- gence guarantees for overparameterized asymmetric ma- trix sensing. In The Thirty Sixth Annual Conference on Learning Theory, pp. 5140-5142. PMLR, 2023.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on sep- arable data. Journal of Machine Learning Research, 19 170):1-57, 2018.
Stöger, D. and Soltanolkotabi, M. Small random initializa- tion is akin to spectral learning: Optimization and gen- eralization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information
Processing Systems, 34:23831-23844 2021.
Tao, T. and Vu, V. Random matrices: The distribution of the smallest singular values. Geometric And Functional Analysis, 20:260-297, 2010.
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., and Recht, B. Low-rank solutions of linear matrix equa- tions via procrustes flow. In International Conference Machine Learning, pp. 964-973. PMLR, 2016.
Vaskevicius, T., Kanade, V., and Rebeschini, P. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32, 2019.
Vershynin, R. High-ddmensional probability: An introduc- fion with applications in data science, volume 47. Cam- bridge university press, 2018.
Wang, X.,
Wu, C., Lee, J. D., Ma. T., and Ge, R. Beyond lazy training for over-parametent perameeaeetee tensor decomposi- tion. Advances in Neural Information Processing Systems, 33:21934-21944 2020.
Wedin, P.-.. Perturbation bounds connection with sin- gular value decomposition. BIT Numerical Mathematics, 12:99 111, 1972.
Wind, J. S. Asymmetric matrix sensing by gradient de- scent with small random initialization. arXiv preprint UrXiv:2309.01796. 2023.
Woodworth, B., Gunasekar, S., Lee, J. D., Moroshko, E., Savarese, P., Golan, I., Soudry, D., and Srebro, N. Ker- nel and rich regimes in overparametrized models. Conference on Learning Theory, pp. 3635-3673, PMLR, 2020.

---

Implicit Regularization for Tubal Tensors via GD
Supplementary Material
A. Outline of Appendices
For ease of organization, we divide the supplementary material into appendices follows. In Appendix B we define some additional notation, including the angles between two tensor-column subspaces, In Appendix C we decompose the gradient descent iterates into a "signal" term and a "noise" term, which will aid us our analysis. In Appendices analyze the spectral and convergence stages, respectively, of the gradient descent iterations. In Appendix we prove our main result.
D
and E we
To avoid breaking up the flow of analysis, we put technical lemmas in the last few appendices instead of in the previously mentioned appendices. In Appendix G prove some properties of measurement operators which satisfy the restricted isometry property. In Appendix H we prove some properties of matrices and their subspaces. Finally, in Appendix[[ we prove some properties of random Gaussian tubal tensors.
B. Additional Notation
For tensor Y Rexrxk, we denote its t-SVD by y Vy * Ey * Wy with the orthogonal tensor Vy. Wy R=xrxa, and the f-diagonal tensor Σy E Rrxrxk We will refer to Vy as the tensor-column subspace of y and by Vy- R==((=r)xx we denote the tensor-column subspace orthogonal to Vy with its projection operator Vy V =I Vy V3-
We measure the angles between two tensor-column subspaces V and V2 by the tensor-spectral norm V Vyyll which according to (Liu et al. 2019 Gleich et al. 2013) Kilmer & Martin 2011) is equal to
|3 Vy.1l = 11 * Vy.ll = V Vy
which means that the largest principal angle between V and 22 equals to that of these two subspaces represented in the Fourier domain. In the Fourier domain, since VJJ ((n-r))xnk and Vy, E Cnkxnk are block diagonal matrices, it holds that
V
(1)
Vy, (1)
V
T
(2)
Vy (2)
| Vyl
y
| (1) Vy, |
max 18JSk
V (k)
Dー (K)
C. Signal Decomposition
Recall that the gradient descent iterates defined in 3.4
U4+1 Ui ((())
-U++IA (y A (ui uu.) xl
U, [I [I++(AAAA A) - -U: Ut
For the ground truth tensor X' E Ruxrxk consider its tensor-column subspace Vx with the corresponding basis v Rexrxk Consider the tensor Vx U2 E RexRxk with its t-SVD decomposition Vx U, = V, E, W.T. For
W. E Rxxxk we denote by WT,1 E ( a tensor whose tensor-column subspace is orthogonal to those of W., 6
that is I W.l and its projection operator Pw... defined as Pw.. W., W. We W. We then decompose the gradient descent iterates U, follows
u: U1 W, W + U4 W. W
(C.1)
We will refer to the tensors U * W ! as the signal term of the gradient descent iterates, and the tensors U4 W W
will be named as the noise term.
12

---

Implicit Regularization for Tubal Tensors via GD
Lemma C.1. The lensor-column space of the noise term U, L. T W.,1 W. 1 is orthogonal to the tensor-column subspace of the X, namely V x * U Wt,1 * W.,, O. Moreover, if Vx x Ut is full tubal-rank with all invertible singular tubes, then the signal term
U. W * W
has tubal-rank with all invertible singular tubes and the noise term has tubal rank most R
Proof. Vx U WT,1 W.,, -VX U1 (I W W!) V * +u, V UN We W, 0 e Rxx The second part follows fact that Vx * 2 is full tubal rank with all invertible singular tubes then all the slices in the Fourier have full rank.
D. Analysis of the Spectral Stage
The goal of this section is to show that the first few iterations of the gradient descent algorithm can be approximated by the iteration of the tensor power method modulo normalization defined as
Ü: - [ A(X xT)) +lo E, Uo E Bxx
Ruxnnk Moreover, this will result in the feature that after the first few iterations, the tensor-column span of the signal term U, W, W. becomes aligned with the tensor-column span of X, and that the noise term Ut Wi,1 is relatively small compared to signal term in terms of the norm, indicating that the signal term dominates the noise term.
with the tensor power method iteration Z, (I + A(X X
For this, let denote the difference between the power method and the gradient descent iterations by
ε :; - -U,-
(D.I)
For convenience, throughout this section, we will denote by M the tensor M A*A((X xT) U: (I + pM)*t Uo and Z. (I + pM)
Baxxxk so that
In the first result of this section, the following lemma, show that & can be made small via appropriate initialization scale.
Lemma D.1. Suppose that A: Suxaxk
+ Imm satisfies RIP(2, 61) and let t be defined as
min {i E N: 11,--1 U; [2, [11-1113
(D.2)
Then for all integers I such that < < t* it holds that
a
||&||| |14, ü.ll < 8(1 8, klvK) min {n, R}
| 1 + m||M
(D.3)
Proof. Similarly to the matrix case in Stöger & Soltanolkotabi 2021), b. in the tubal tensor case it can be shown that for I 2 1, the difference tensor E, = 21, Ui can be represented as
ε, U: ----
ú
Σ I (M
(D.4)
with غ, pA* A 1004,-111,11 U * + To estimate ||Ex|], we will first estimate each summand in (D.4) separately. First, we can proceed with the following simple estimation
II (M) < II #MMI|( E s (1 ml|M 1
Now, for |, using the fact that the spectral norm of tubal tensors sub- sub-multiplicative, we get that
| = AIlAAA UT_1) U, S A - 114--
13

---

Implicit Regularization for Tubal Tensors via GD
Since operator A satisfies RIP(2,61), by Lemma G.3 A also satisfies S2NRIP V), which provides the following estimate
|| * J-11) (1 ( ( (1)
All this together leads to
|& = 1i4, - -uell u (1 1,
(D.5)
From here, we want to bound ||E,|| in terms of the initialization scale and the data-related norm || For this, we first use the fact that the tensor Frobenius norm above can be bounded as [1 S v min {n, [t} 21 Then since for
all 1 j j S ta have [[t 1- || v
[2, -
Il, the spectral norm of uf j-1 can be bounded as
U 1 ا U ا - 2
This gives us the following upper bound
| < 8p(1 + 61 Vb) min (n, R
(1 + A M|| M
(D.6)
1=1
As for iterations the tensor power method, it holds that
| = (I + (M)) Holl < [ + pM) s (1++ [+++|||)>>>-11 1241l =01 + -||-M))2-11144)
can proceed with D.6 follows
1.
| s 8p(1 V.VE) kmin {n, RJa "124
" + 11
1=1
Now, the sum the right-hand side can be estimated
ul| 2 2
E (1+ M|)) = +1+ MIIMI 2a (1 + ( (1+p||M)))*
(1 44 M 2
==1
(2 ml|l)) S (1+ [1+M)
(1 + 21
(1 +IIM
MMlM
which gives us the final estimation for the norm of E, follows
3 ||&||| s 8(1 + + 11 / kin (n, R]
1 + ml
|M
and finishes the proof.
The following lemma provides a lower bound for t", indicating the duration for which the approximation in Lemma D.I remains valid.
E &Raxnxk and (I +-+ t Up. Let M E Cukxnk be the corresponding block diagonal form of the tensor M with the leading eigenvector Un E Cnk then
Lemma D.2. Consider tensors M :==Ab A'X x
M 1124g
In
8 8(1+81V R3) k min (n. [211
(D.7)
2 (1 + ml
14

---

Implicit Regularization for Tubal Tensors via GD
Proof. Let E CCuxx fik be the corresponding block diagonal form of tensor Ü. By the definition of the spectral tensor
norm, we have || = | and the definition of the matrix norm gives | 2 [ vn ville. For the block diagonal
version of Ut the following properties (see, e.g., <Liu et al. 2019) holds
u, [I + PM) U (I + pM) Un (I + pM) Un
(D.8)
This allows us to proceed as follows
U
u1 11 ((I + WM) Uo) v1 Uuu [I HMM) 21 (1 MIl "00
where for the last equality we used the fact that block-diagonal matrix (I (M) has the same set of eigenvectors matrix H
μM)
H vn ville. Then, applying Lemma D.I the relative error in 2o M. From here, we get |iZZ||| 2 [4 vn ville, = (1 + w||
the spectral norm between U. and 24, can be estimated as
ú Uell 611+8
min {n, RJcss
11 pl| ||))
|24|||
[MM]] 1140 un lllee
Setting the bound above to be smaller than I and solving for 6, we get
| v. Il,
In
t 8(1+6) vk) / min (n,
2 In (1 + M|]
Since t N with t S t* 'should be such that | || 1e- 1, we can choose t" as the floor-value of the right-hand side above.
|144-111
To show that the tensor column subspaces of the tensor power method iterates and the gradient descent iterates are aligned after the alignment phase, we use the largest principal angle between two tensor-column subspaces as the potential function for analysis. Borrowing the idea from (Gleich et al. 2013), we will show that the power method iteration in the tensor domain can be transformed to the classical subspace iteration in the frequency domain.
For this, consider the power method iterates ú, (I - WM)" Uu, the iterates Z, (I + μM) and the gradient descent iterates U, represented as U, ú, E, 2, Uo + &,. All these tensors have their counterparts in the Fourier domain, which will denote respectively as Ui, Z, and Ut
As before, consider M A'A((X * x E Raxnnk with its I-SVD M VM ΣM W and its Fourier domain representative M E Chkxnk We denote by L E Raxrxk the tensor column subspace spanned by the tensor columns corresponding to the first r singular tubes, that is L = VM( 1 r.:) E Rexrxk Note that L is also the subspace spanned by the tensor columns corresponding to the first singular tubes of the tensor Z, E Rnxxxk
By L. E Raxaxk we will donate the tensor-column subspace spanned by the tensor columns correspond- ing to the first r singular tubes of the gradient descent iterates Ur Z, Uto + E.. More concretely, for U. = -E Vu, (i,s, Ex, (s, s) Wu, (i,8,;) and the corresponding Fourier domain representation U,
diag (T,(),) (2))),))) ...,, (7),,, where U.G)- = E, (1) E ol)) "y wf) = Ub - "(( we define the corresponding new ten-
sors L. = Vu, (s, :r;:) E Raxrxk and their Fourier domain representations
E, = =diag( T, (1) L (2)
T, (x))
(D.9)
Lemma D.3. Consider the tensor iterates Z, = (I + n with its block mattixx representation
E. = bdiaa( Z.) = diag( 7, (2) ,....
..... 7,, ()).
(D.10)
and the tensors
E, = U, - -u, RunRxx
Uo all Rax a>0.
15

---

Implicit Regularization for Tubal Tensors via GD
Assume that for each 1 S S k, it holds that
|
0r+1(Z, 24
+
<
(Z, (V * U))
(D.11)
a
Then for each 1 j k; the following two inequalities hold
miin (V/ or (T, o, T, + Eg ( 2 ao, Jmmin
= U -
(D.12)
r++1 (U, (Z, E, )) S (Z, + ||Elll
(D.13)
Moreover, the principal angle between the tensor-column subspaces L and Lt is bounded as follows
a0,+1 (Z, 5)) 4 |
Ve * Vc. S
max ISisk 0r or (07 (Ve U - a0 ( ||E,|
(D.14)
Proof. For some E N, consider tensor 3, (I + MM with its block-matrix representation
Z
Z, (2)
3, = bdiag(Z)) = diag((,") 22, .....
Z, (k)
As we assume the symmetric tensor case scenario, the block-diagone matrix representation Z, consists of symmetric matrices O) C_*"", At the same time, according to (Gleich et al. 2013),, the gradient descent tensors Ue Z, + have their block-diagonal matrix representation
Z ())
E,(1)
Z ())) (2)
(2(2)
u. 2, 11 EE, + 2,
(T() (R)
E, (k) (D.15)
Using Weyl's inequality in each block, we have
or (Z + +E0)) 2 or (Z7 -IE o, (V2'))=00T6)) (V2 -1E,
Now, for the singular value above we get the following estimation
(V = mmin
Vi
(1) M Z (1)
Ve V) 2, (.vve (1)
Imin Ve (V6
> Umnn
o, Zz 63) (m)
(Ve)) (0 > ao, (z, (Z) Jmii
Ve (e()) (6))
V (VE 2 ao, (Z, mmi
= ao, oo)
V/[ +1
where in the last line we used that for each tensor holds Fourier domain Vcc G VT
To show inequality (.13).
Weyl's bounds and then the Courant-Fishhe Fisher theorem, which leads
7, OT + F,))) s ar+1 7 (, (1) + F, W | S art1 (o.0111,,000 (7,00 + |E,||
S 0r+1 ( + | < a0 (7, [Z)1) + |E+|]-
Now, for estimation of V Vc, ||. let us recall that C is the tensor column subspace spanned by the tensor columns corresponding to the first r singular tubes of tensor Z, = (I nM) Roxaxk and L, is the tensor-column subspace
16

---

Implicit Regularization for Tubal Tensors via GD
spanned by the tensor-columns corresponding to the first r singular tubes of the gradient descent iterates 4, 2, + E and consider Fourier-domain representation (D.15) of Uz Here, for each S j ki the matrices (,)) F,, (1) can be represented as
70 + 1000-Z(-00
V Uo 00
Z
Z0V
Uo E.u.
(D.16)
A57
A
C
As the tensor-column space V is r-dimensional, each of matrices V2 has rank r, see Gleich et al. 2013). Since the matrices Z, can be decomposed as
Z Vc (1)) Vc (1)
-o- V G)
+
we have that
Z, V. Vc
( ()) 00 V0
Vc ()) (
(D.17)
As 0) E Crx has rank r, Ve 6) TT,)) has rank r, which means that the product above has rank too. Due (D.17) we see that
Z, 7 Z VV (1) b = V2 0 V U
which makes V) to the column subspace of Z VV (1) U) Considering the gap between the singular values of for matrices A0) and Ali (D.16), namely 86) = (,())) 1 (A0)), and using Wedin's sin theorem (Wedin 1972), for each S j S we get
())
|CO||
I|Ve- ()) Vc. (1)
86)
To conduct further estimation of numerator above. We start with the denominator first
[VV (1) Vc, 111|, we analyze lower and upper bounds for the denominator and the
أهل = (,(A)) 0r41 (ĀO))
E,)
Using properties of singular values of the matrix product for the first term above and Weyl's bound for the second term, we get
815) 2 (7) minnn
Vi Ve(i T6()) - o (00-(Z7(0000 (7) (o-(7)))))))66)) | |
-
2 or (5) Jiin oo)
V/c +14 -r++1 1 (2, -1E11.
(D.18)
For the norm of (()), the following upper bound can be established
|| < |7,
1 | |
< 1 V V 6) 1110 1 + |
-0 (7 (5) ||
||E||
(D.19)
Now, combining bounds (D.18) and D.19) one obtains that
00 20,41( [4] E
[ Vc.l max
V
Vc.
0I
max JS
1sisk
o, (Z,())
Ve= - o -0, (2,000))) - ||&
Using in the denominator the fact that 0 of this lemma.
(2) s ao -0,+1((,00)) (Z,6) < ao [ finishes the proof
17

---

Implicit Regularization for Tubal Tensors via GD
Further, consider the gradient descent iterates with its t-SVD
R
Ui = Σ
(;,,)) (8,8,)) * Wil, (3,
a=1
and (,0) = >i of
the
corresponding
Fourier domain
representation WiSH and its signal-noise term decomposition
U, = Liing(U,"), (..),,.,..... (,((),,
where
- -
W
u, - U W, W. + +u We.1 W._
We also define the corresponding tensors
C. Vu, (1,8,)) Exe, (8,8,;) * W (1;8;;)
(D.20)
N Σ
Vu, Es, Wi, (;)
(D.21)
and their Fourier domain representations
C. diag (), I () ..... )
Iτ6)
oi
(
w =VC W((
(D.22)
R
N, diag(N (1) N₂ ,,..,,,((R)) ())
N₂U) =
Σ
ot 2t wi
(1) 10,
( (
= >
_i: wit
(D.23)
b=++
Lemma D.4. Assume V Vc.ll S 1. Then it holds that
(,6)
0r+11
WW Well 2 max
IIV x V2,ll-
(D.24)
18iSk
(7,6)
Tr
Proof. Consider IW W.ll maxisjck
() 10 For each S k; we can now exploit the results of
Lemma A.1 in Stöger Soltanolkotabi) 2021). to get that
|
6) VX
11
2 Omin [ (1)
1|
<
and miin (Vx (1),),1)
>
Vx (.T,61)
2
mmin
From here, can proceed follows
(1
I1I N.
Vx
I ct * W.ll = max 1sick
IH
2
max 15ISA
Omin (T)
Tr+1 (U,
61
(U,()))
2 max 1Sisk
2 max 1Sisk or (U,(0)
1V
Vxll
(U,(0)
T (U,(1)
= 2 max ISiSk
I * =Ve.ll
of (U,(1))
which concludes the proof.
Lemma D.5. Assume that V
x Vc, < for some 2 1, N. Then for each 1 S j S k, it holds that
or (u: w. 6) 2 の, (u:0) 0i, W..1 (1)) S (U,
(D.25)
(D.26)
18

---

Implicit Regularization for Tubal Tensors via GD
Moreover, the principal angles between the tensor-column subspaces spanned by X and We can be estimated as follows
x| Vu.w.l S x * V.cll
(D.27)
[1 W 2 max 0++1 (T) 15isk
(D.28)
Proof. We assume that | * cc S 5. then due to Lemma D.4
we obtain that
0r+1
I c. W.ll 2 max
1V
Vc.ll 4
(D.29)
ISJSk
or (
Now, to estimate of U, W( we see that for each 1 2 S k, it holds that
or U1 * (,, ) or (u, * W, U, (. = -o ","
(D.30)
Since T, 0,0) I,,i 1, N,O N, get that
or U1 (u:
(u:+ ))
*
W. G00 T, (,,01 or - )))
2 2a (w, H1 W ) ) (L, U)) 2 (1 WW w ),,
where in the last line used the definition of the principal angle between tensor column subspaces and the corresponding properties in their Fourier domain slices, namcly
o, (W (W,
W W =1 1 | W
O 12 2 1 - max Sicc
W
W =
W IT
Due to our assumption VV x- Ve. J. we can see that in the Fourier domain, the subspaces spanned by v x! and
(t)) E. = VVr are close enough. Then, decomposing U,() into two different ways, namely as
R
()) Eo
U ()
I,,. + N,
We
t=1
and
U. - -,0 (
J, W W 6)
according to Lemma H.I obtains for each 1 1 k that
[ H X Vo |1 s $7] (v2) X
| (0 20,+1
where the last inequality is equivalent to o (U, W., () < 20, 20, ()) According the definition of principal angles between tensor subspaces, this implies that
I Vu,.w, = max
[0) x
Vi & 7 max [ V = 7 * Vc. ||-
In the same way, I1 Wt,ill = max, |U, W.,, (1 s 2 max, a (U, (i)), which finishes the proof.
Lemma D.6. Consider a tensor T = X T E gmxnxk with rubal rank r & n. Assume that measurement operator A such that
== A T E S Snxnxk
19

---

Implicit Regularization for Tubal Tensors via GD
and for for each 1 S S io one has || S (T() with ö S 3. VM* * IM* WJ. let L E Ruxxxk denote the tensor column subspace spanned by the tensor-columns corresponding to the first r singular tubes, that is C := VMl(..:r, Rxxxx
For the same M with its i-SVD M
Then, in each Fourier slice j. S j S k. it holds that
(1 - )) (M (1 (8)))(6()))
(D.31)
Ar+1 (MU)) & (A
(D.32)
X, (M (1 (T
(D.33)
and
(1-8)ITTI & |MM|| & (1+ 8
(D.34)
Moreover, the tensor-column subspaces of X and C are aligned, namely
1 Vcll S 26
(D.35)
Proof. Consider tensor T == X' T E Suxaxk Due to the definition of tensor transpose and conjugate symmetry of
Fourier coefficients (Kilmer& & Martin 2011), the Fourier slices of T are defined as T = x()) That is, each face of T is Hermitian and at least positive semidefinite. As we assume that for each j. 1 S k, one has |E || s 8A, (T()) using Weyl's inequality in each of the Fourier slices, we obtain the first three inequalities.
To show that the tensor subspace Vx and Vc aligned, use first the definition
VV Vcll
max Isisk
x1 V
E
(D.36)
For the estimation of || V
|(ii in each of the Fourier slices, we apply Wedin's sin theorem. For this, denote _ x and let (i4) denote the corresponding Fourier slices of L E Brxxx Since in the Fourier
C : VM 1: r,: space, it holds that MD) T() + EUU and (i encompasses the first eigenvectors of MG) from Wedin's sin O theorem, we obtain
|
|V x1
{(]
with g0i (T(T)) A (M))). Using estimate D.32 {(U) can be lower-bounded
{(U) == Xr (T()) A++1(10)) Xo (T()) (X,(T (11 1-))
Using the bound the the assumptions that FE || || S 5x, ( (T)) and 8 < 1. we get
11
6
1-6 < 25.
Coming back to equality (D.36), we obtain the stated bound for the principal angle between the two tensor column subspaces.
Lemma D.7. Consider a tensor X * X E S saxaxk with tubal rank n. Assume that measurement operator A is such that
M = A' + x = X X 3
and for each, j, S < k one has | < (X, with 8 < c1. Moreover, assume that for difference tensor E, =u - Ut it holds that
a max 0,+1 (Z, (1) [|] 15i5k
(Z)
|
1
S C2R -2
(D.37)
min o, (Z,
@o (V( mominVV +4)
20

---

Implicit Regularization for Tubal Tensors via GD
where C1, C2 > O are sufficiently small absolute constants. Then for the signal and noise term of the gradient descent
have
V * Vu...wll - 14 +7)
(D.38)
x=
[1 Wt,
S
a min or Jo
(omi (V/c * (
(D.39)
8
15JSk
and for each j.1$ S k, it holds that
Miin (U, * W. ()) 2 a min or (Z,
(omin m (V = u4)
(D.40)
4 1sisk
σ1 (u, * WT.1 (1) S
K
min or (Z 10 1sisk
0 min (Vc = U)
(D.41)
Proof. To prove the above-stated properties, will use Lemma D.3 Therefore, we start by checking the conditions of this
lemma. Sufficiently small 0o and the assumption 7 S c2x-² 2 allows for y S 2.2 This means that
44 + ||E,|| a max 0 (7 1SiSk
$ 2
min or (7) 1SJSk
min (V * U
and in each of the Fourier slices we have
1
0r+1 ())
U +
or (Z. min (V2 U)
2
a
fulfilling the assumption of Lemma D.3 Hence, from Lemma
D.3 we conclude that
a0 (Z,41(Z,0))) [1| + ||E
2 * V.,
max ISiSk
(D.42)
av, (Z, o Umin (V-- 2) - -00+1 [1] ||E,||
max o (Z, ||1 + ||E,1| 1SiSk
(D.43)
a min or ZZ (1) J
(V * U) - a max 0,+1 ( - |,,1| 15JSk
13jsk
and, moreover, together with Lemma D.5 and the assumption 7 S we get
min or oU 2 min or oz (5)) Jmmn (Vc * U) ||,11 >
min or (1) )o (V/ * U) 1siSk
(D.44)
1sisk
15isk
max 0 (0, ()) <a min o, (Z, [1 + |E,|l S an min or (Z, (1)
mmin (V U)
(D.45)
ISiSA
19i
The last two inequalities, allow extend bound (D.2 as follows
7 2 Ve. ll 5 1-
(D.46)
Now, consider the principal angle between X and L, using its definition
DVT
* Vc.
max
(i)
max
x
H
H
2.
1Sisk
isisk
siick
max
x
x
C.
C.
max
X
76) -
xー
+
2272""
b H マリV
max 1sick
15t5k
1 c1 = Vell
Ve.l
21

---

Implicit Regularization for Tubal Tensors via GD
Using the last line above, and inequalities (D.35) and D.46), obtain
IV x- Vc.ll f 2(6++))
From here, allowing 8 and y to be such that x Vc.ll - 5.
Lemma D.5 to get
x Vu.w ll S V
Vc.ll S 14(6 7).
Furthermore, Lemma
D.5 together with inequality (D.55) also results in
01 uu WT,1 ) s 20 20,+1 (U,
- 2 max T (U, 1 sjsk
v 2
min or (Z, (Z, ) mi ( * U)) 1si
S xー a min or (Z, min ( * U
8
and for the spectral norm of uf WT,1 we get
x- I
[ * W. <
max 18isk
0 (U,
a min o, (Z, mi (V2 * U).
8
15j5k
To conclude the proof, we see that Lemma D.5 lower bound
together with inequality (.44 provides for each j, S j S k, the following
1 or uu (u
2 o
(4, 2 4 (Z)) min ( u) 2
mmi
min or oZ m (V * U).
18jsk
The following lemma shows that for an appropriately chosen initialization, in the first new iteration, the tensor column subspaces between the signal term U W. and the ground truth tensor X' become aligned. Moreover, for each S there is solid gap between the smallest singular values of the signal term and the largest singular values of the noise term. Lemma D.8. Assume A : Suxaxk Rm satisfies the S2NRIP(6:) for some constant
Also, assume that
= A(X x X X EE
with | S (XOXR))) for each 1 S S l and 8 S -1
Denote by C the tensor-columns corresponding to the first r singular tubes in the t-VD of M. that is, L VM(; Raxrxk and define the initialization Uu all with the coefficient a such that
18A
cl c|2
2x 12
a² < 12k min (n, RJ 2/13 man (VL 21)
min famin (Ve 21), Uo lel
(D.47)
where U1 E Cnk is the leading eigenvector matrix M E Cakxnk
Assume that learning rate fulfils μ S CyK 22| || then after t, iterations with
2xx [
4 X pminggise or (X0)} In
(D.48)
C30 (V x2)
holds that
[ || S 33
(D.49)
Vx xT Vu. w.. || S ox
(D.50)
22

---

Implicit Regularization for Tubal Tensors via GD
and each 1 S j S k, have
or (u., +W,, (1)
2
1
(D.51)
4
x-2
01 Ur, W. WW...- (1)
-
8 0
(D.52)
(D.53)
16k²
where 3 satisfies mmin (Vc * u) S S min (V-c 21)
2x
cadmin (V2)
Proof. For the proof of this lemma, want to apply Lemma D.7
The first condition of Lemma D.7 is the following
a max 0 7+ (Ze (1)
|411 24|1 + ||E||
=
1S/Sk
S C2R
min or (, 1StSk
min (V zU)
By the definition of 7, it sufficient show that
max SySk
r++1 [Z ()) |1
-
C3
min or (Z) Jmin (e +l))
(D.54)
2x²
isisk
and
| S
C3
a min or (Z, )o ( * U).
(D.55)
2x
Since for 2:= (I + pM) the transformation in the Fourier domain leads to the blocks
z = (Id + 1M
this means that inequality (D.54) is equivalent to which can be further modified as
1 + min o.(M ISiSk
2x:3|
C3 (VC +l))
1 + / max
(++(MM
15jsk
1 min or (77(
2x
In
tt
122+20
1 1+
max T (M Isjsk
0 min
Hence, we take 4, as follows
1 1 min or (M))) 15ic
2x² |24||
In
In
(D.56)
Tmin
(VL
24)
1 P max 0,+1 (M))
then condition (D54 will be satisfied in each block in the Fourier domain. For convenience, we will further denote
2x [|24|]
In
(D.57)
( * U))
Tmin
For the second part of Lemma D.7 s condition, inequality (D.55)
we will use Lemma D.1 To apply this Lemma, the
condition t, S needs to be satisfied. According to Lemma D.2
1124 " "ile
In
8 8(1+8 K) /k min (n. [
(D.58)
(1 + m|
23

---

Implicit Regularization for Tubal Tensors via GD
For 1, 1a hold, it will be sufficient to check, e.g., the following condition
[|M La oxlle
In
8(1+61/k) / min (n, [alss
In
Hp min a, (MM))
2
2 (1 + mM]
1+ maximaxiissss Cr+1 (MI
1+ mim of first. Using
To check this condition let us first analyze the expression In (1+ M l)/In
max (r116111))
Itr < In(1 + x) S can upper bound the above expression
In (1 M|
(D.59)
Htrmiingssse (MO)
0, - maxisisk 0++1 (MU)
In
1+pmaxiggg* or
From here, applying the PSD of the tensor representatives in the Fourier domain and the assumptions d 1/ and μ S CyK'" 2 || and Lemma D.6 get
[M]] minngjs4 (M(U))
(1 T1
(1+c3(L+0)
(NIT)())
xi||8||
(M))) maxisisk 0+1 (MG))
(1 - 20)A,
x² (1 + 8)
(1 ca(1 8)) 8n²,
(1 26)
in the last line, used the bound on å and that eg be taken small enough. This means
In (1 M|
8x
(D.60)
1+ min o, (MO)
In
+ d (M61)
Thus, to show that t, S t", it is sufficient to tune the initialization factor a so that
| 1 H 01 villes
32k2 S In
8(1 + 61 / min (n, R]a 11 1
or using the notation for o, this is equivalent to
32N²
2x -
[M] Uo ville, + 8 / min (n, R) 3
Tmin (VC 24)
Since 1 H en ville./a = 11tttt Un llle. The last incquality is implied if
32nx2
2x² 1|21
IM valles
a² -
Mmin (VL * 21)
8(1 + k /min in, R
or if we set even smaller using the fact that (1 (hVV)VK < (1
V < 2h and [MMI| 2 11 and set the
parameter a so that
32Nx2
2x 2x
X
1| 11 Iles
a²
minn (V2 +u)
24k min (n, R. [4
Hence 4, < 1* is satisfied and applying Lemma D.7 we get
a
| < 8(1 + 8, kk) k min (n, R8}
| (1 31)
(D.61)
[M
24

---

Implicit Regularization for Tubal Tensors via GD
Moreover, using ||M]] 2 || from Lemma D.6 with 1/3 and (1 81 VbVE 2k, get
a
||E,, - / min (n, R
(1+
Hence, using that Z, (Id + pM ()) inequality (D.55
will be implied if
min (n, R}
4 [1 + 11 ml)
min or 15i5k
o- (Id uM/ Jomin ( x(1)
x
2x
which is equivalent
|x män (Vc U)
(1+ (M
a² S C3
(D.62)
12k min {n, R2 [u]ls (1+ ml)
for all j. To proceed further, let us analyze the last factor from above using the definition of t. Note that
(1 + pd, (M = exp t. In
1+ pA, (17O)) ))
2 exp (-3t, In ((1 + μ (M))))
(1 + M|]
(|
Now, using the definition of l., that is 44 = w//l In
14y (M(M
)
and inequality (.60) we get
1+ymaxx 0641 (MT(T)
48kx
exp (-3t. 3t. In (1+ m1(())))3)
exp (-48
2x² [1])
(D.63)
C3O min (V) +2t
Inserting this into inequality D.62.. we get
- 18x2
X 2o min (Vc * 21)
2x² 2x²
a² < C3
(D.64)
k min {n, [
mnn (V * +Z))
For such a, we have shown that inequality (.55) holds, and the condition Lemma D.7 is fulfilled, which gives us
x Vu.ww S 14(6+07) cx
(D.65)
where the last inequality follows from our assumption that S c and S C3K 2| -2 and from setting the constants C1 and C3 small enough.
Moreover, for each S S k, from Lemma D.7 it follows that
1
0 Mii (1, * W. ()) 2 a
(D.66)
4
o (1: We.1 (1) < 2
-a3.
8 aB.
(D.67)
Jiin (VC * U). where 3 == min or )om
In the remaining part, we will show that t., 3 and [ have the properties stated in the lemma.
Let us start with 4, Using the same inequalities for In(1 + æ) as above and Lemma D.6 one can show
1 min (M(() 1SSS
a min or (M() 15yS
In
2 / max 0 (M7
> 3 15
min (X00)2
(M+1 1+ 15i5k
1+ 1 min or (MM() 15isk
1515k
and at the same time
1 + μ min or (M)
ln
15iSk
S In (1+ u min or (M(M))
<
min or (M()) 1515k
1 + μ max o (M)))
15jSk
1SJŠk
25

---

Implicit Regularization for Tubal Tensors via GD
S p11 + +)
min isisk (x(( s 4/3 min ox(X)))² 1515
which shows that, on the one hand,
2 max
1
1+ min (M(M)))
3/ isisk 0, (x
3uminı Sjs o, (X6))2
In
maxissg (141()
and on the other hand
3
1+ (M)) Ltp 0rl (MMG))
4p mpminggssk o (X
which shows the desired properties 4..
Now, we consider B == millisjs o, (Z, (1) Jmin (Ve * U). By the definition of Z and inequality (D600p we get
[1+ (T( exp (. [n[n + no, (M s exp (4, (n1[11++]|| =I|MM)))
16x²
In (1 + (l(
2x 2x2211411
S exp
2xp max 1Sysk
S exxp(16<bx
=
(D.68)
In
(M
C30 min (V/ U
1+po.+1(M10))
Since this holds for all j. we have
16A²
2x |1|||
B S o min (V2 xl)
C30 (V 41)
Finally, we come to the properties of U,. By the representation U, = Zr. * Uo + E,,, we get
[ S a ||| ||E,
From (D55). we get
|E,|| -
C3 2x²
al 12.l/ominn (vc
-
C3 2x
all 12el|
VVe H mmna (T) S [
which allows us to proceed as follows
Mee- |1 S 2a| ee. |||2|||| S 22(111111 + ([[+++IIMM)) M|)* ||
16x²
2x 2x21|21||
= In [t+(1 + m||MM)) |,||| S 20 (11
C30 (V 21)
-8w2
mnn V + +l)
2x |
s <21|X1|
<3||111
12k min (n. R) R> man (VC U))
where for the second inequality above we used (D688 and in the last one upper bound on from D.64 has been applied.
The results in Lemma D.8 hold for any initialization 2. Below, we will use the fact that 24 is tensor with Gaussian entries. This yields the following lemma, which shows that with initialization scale > 0 chosen sufficiently small, the properties stated in Lemma D.8 hold with high probability.
Lemma D.9. Fix a sufficiently small constant c > O. Let E RRxRRx be a random lubal tensor with i...d. NO, + entries, and let e E (0, 1). Assume that A: guxnxk
+ m.mh satisfies the S2NRIP (81) for some constant 8n O. Also, assume that
M = A * x
X + x + +
26

---

Implicit Regularization for Tubal Tensors via GD
with |F & 5d, (P6 ) for each 1 Sj S k. where & S c1152 Lettl = all where
-24k²
mmnnnn, 211
kn2
if 2 3r
12223/2222
C3 Sgminnp n, R233/2e
a² x
<l 111
kn2
3/2
-20
if < 3r
k/2n3/2p2
1/2
Assume the step size satisfies μ 02k" f=,-~2|100 || Then, with probability at least
p where
M(Ce)R-r41 + ke-öR
if R 2 2r
p
KE² + ke
if R < 2r
the following statement holds. After
2n² Vn
if 2 3r
t. S
# mmin Sisk or (X(1)22
C3E
min(n; (m; R}
22 22*
In
if < 3r
pminigosk (8
ngf
iterations, it holds that and for each j & k, we have
[e |l S 23121
(D.69)
V Vu. w., |l S cx
(D.70)
or U1 *W,," 01
2 a3
1
(D.71)
4
1 -
Ur *W.,
(1)
8 a8
(D.72)
(D.73)
where
16x²
2xd Vn
if 2 3r
Oze c miviminne.. RJ
B
<V
2n² /rn
16k?
if <
Cse
and
CVk
if 2 3r
32
EVI
if 3r
kmax n, R.
kn with probability at least
Proof. By Lemma I.3 we have that |4| 5
R
minfn; R}
(( Also, by Lemma L.4 we have that ||ZZ " villez 1 * Ville Vi with probability at least
1 CRR) Since u E Rax Rxc has i..dd No0,, 1) entries and V Ve I, by rotational invariance,
V * U E Rxxxi also has i.i.d. NOO,, +)) entries. Hence, the lower bound on aiin ( U) in Lemma 1.2 applies. If
r < R < 2r, we have
EVK evk
min (VT 22)
VrR
27

---

Implicit Regularization for Tubal Tensors via GD
with probability at least ke? 2r < R 3r, have
min (V cVk(VR 22 cvi(R - (2r-1)) -1)
vr(vR + 2r 11 2 cVk
VR
with probability at least x(CE)) ke clt -elt 1R 3r, we have
ook min (V) x2) WVl(VR -2r =ovk ( (1-1 2r-1
2 LEVE
VR
with probability at least - B-Ce) ke cR
Therefore, the above bounds on ||24|,, 120 vi lllez and min (V/ * ()) all hold simultaneously with probability at least 1 p where
R(CC))-r4t1 ke-öR
if R 2 2r
p
ke² + ke-èR
if < 2r
Provided that all three of these bounds hold, one can substitute these into Lemma D.8 to obtain the desired result.
E. Analysis of Convergence Stage
In this section, we will prove that after passing the spectral stage, U, 24 goes into the convergence process towards the ground truth tensor X' X in the Frobenius norm. For this, we will first show that in each of the tensor slices minn (V> mmin
* U4+1 (i) grows exponentially, see Lemma E.1 whereas the noise terms [ie+1 * W 1 S j S k. grow slower, see Lemma E.3 Moreover, in Lemma B.5 we show that the tensor column spaces of the signal term U4 * W, and
the ground truth X stay aligned. With this, and several auxiliary lemmas in place, we show that
Lemma E.1. Assume that the following conditions hold
P S X 2x
Well S 3||
V Vu.ww,ll S cx
and
A I) X U, * U4 Ill S ca min (2).
(F.1)
Moreover, assume that V Ui has full tubal rank with all invertible -VDD-iingular lubes. Then, for each j. 1.15 S holds that
Mmin (V x 01) 2 Jmin (V) mmnnnV
U2+1
W) o mén (V> + U, (0) mi uoo min (V * u1 (.) ()))
Proof. Consider the tensor V + +l+t1 W. Using the definition of uf in terms of we can rewrite it
V U441 W: V *
X -1, * u(?)) U. Wt.
This representation leads to the following representation of the RHS above in the Fourier domain
V H (Id (Idd+ (AAAAA(X X -u, * 1)= ( = H
Note that here (At A(X X - U4 )) can not be represented as an independent slice of measurements of - 7(1 as it involved the information about all the slices 1 S < k.
Due to our assumptions on [ and the tensor spectral norm property, we get
( S | < |4, s X|
28

---

Implicit Regularization for Tubal Tensors via GD
This in turn is leading
/ S c|| 2x =
- x
This property of y together with the nature of W and [ coming along from the signal-noise-tern decomposition leads to the fulfilled conditions of Lemma H.2 Applying Lemma H.2 to the matrix H(),, the smallest singular value of matrix HD) can be estimated as
C.1
(H())) mmin(H 2 (1 (1+ po min (1 ul|
mmin
P( - 11lp
-
( min (V T no min (V
(E.2)
with
|| <410 12 x V 7
|| || S 4 (4 A(X x - U, u, - tff
|| s 2| 1 w
Further, will make the above bounds for (2(0) ||, E (1, more precise using information about the tensor setting.
First of all since |0 W || & 11 < [4 || - 3 |||, we get |P(\) || S 36
x wo 1|2. Moreover,
Vu..w.ll S cn due to the assumption, it follows that for each 1, 1 S j < k, it holds that 11 x1 V aot cx_ 1 This allows for the following estimation
since [() X (op = V Vu..w. ( and I x-
|PP|l s 36 S
1 0 min (x),
4
where the last inequality follows from the fact that c >> 0 is small enough.
Before proceeding with | I].
consider
(A'A-I)(X* * x U,
x - Uz u,) - x =U,
The RHS from above has the following slices in the Fourier domain
(A~A)(X x U, * u,,) S
the norm of which (due to assumption E. and the definition of the tensor spectral norm) can be bounded as
(A+ * X - U, U, -
IAA'AA U1 U, I| S co2 mnn (x).
This leads to the following estimation
| || I 4co min (X)
To further assess ||P(6)]| |]. we take into account that matrix W(1) is orthogonal matrix and the assumption |14,11 $ 3/xxl, which allows for the next bound
| s 2 w < 2 "" < 2 11 z 18
Inserting the newly obtained estimates for [IP(S) | (1,2,3} into we get
Omin (H) 2 (1 + f min (X()
4 miin (X) 4 2
2
min (x) 18p2 |111
Tmin (()))((())) (1 i (VL) HT(()))
X
2 (1 + no main
2
X
4 min (X)
2
4uco min
(x) - 18p² | minn (v H ((()))
uo (V H (((1))
Now, according to the assumption on μ. we get
(x)
21 < pcx
min
[ |
cuo (x)
pc
|
29

---

Implicit Regularization for Tubal Tensors via GD
Taking e small enough allows for the following estimation
Omin (HO1) 2 min! (2) (1 +
2 mii (2) po min (
1
=V (V (1 (1 2
(1 po (V HT()))
no min ( (2tTT(1))
=mia
uu min
Now, since minn (22T((1 S min (T( S [1el|| - 3 x| || we have that
m ( ) - و4 x 1| < 9Ck -2 S 2
1
due to the fact that c c> O can be chosen small enough. The last part of Lemma's proof follows from
mmin 2 Uu41 (1)) 2 mmin ( U4+1 W) and min (Vx * U+1 * W,ú1) = mmin(111)) which completes the argument.
The next two lemmas will allow us to show that in each of the Fourier slices the noise term part of the gradient descent iterates is growing slower than its signal term part.
Lemma E.2. Assume that μ S mmmn {
|| II(AAAAI X -i u |111 } and |uell - 3| Moreover, suppose that Vx x * U2 has full tubal rank with all invertible 1-SVD-tubes and 11 * Vuu,w.l S cn- with a sufficiently
small contact >> O. Then, the principal angle between V x= and Vul,i can be bounded as follows
I Wuinw. S 2
Vu.+w.ll A)( x - -U, U1 .1l
In particular, it holds that x VVuen.W.ll S 1/50.
Proof. By the definition of U2+1, we have
U1t1 W: = (I PA X -u, -ux)(,) * xl4 * We
E @Raxr
which allows for the following representation in the Fourier domain
U W, [Td A(*A(XX X U. * 24, )00) U. W,
E ECTT 15isk.
Consider the SVD decomposition U1 W. (1) Vu..w, E U. WH W,o and denote by ZO) the matrix
z0) == (Id + nA~ A(X X - U, -u, x u. )())
E Caxr
Since by assumption U, WW (3) has full rank (due to full-rankness of x * Ur see Lemma C.I matrix Z has the same column space as U(+1 * W and the principal angle between tensor subspaces xx+ and Vu can be computed via Z(i as
IV = Vult
max 1sick
|l = max 1sick
u.
max | isisk
V2ūill-
Now, we will consider each of the terms
H) x=
2
separately and bound them follows
| || m (G4)
x1 こ
| I x
V
200
S
200
Ez
z0:
WH O
[| WH )
-
(E.3)
x
Using the definition of Z the norm in the numerator above can be estimated as
| H
( || <
20
H on + + x A A(X - U, u,)001
x
X w.
(OU X-
u. + +1| x -U: u1,1 )01
x- Vv..w, || vu..w.ll+ A" A(X
T -u, xu )11
30

---

Implicit Regularization for Tubal Tensors via GD
Using again the definition of Z and Weyl's inequality, the denominator in can be estimated from below follows
Mmin (2()) 2 min (V (w - ull A A(X X U, x u, )on) ww
2 1 - A|X * X -u, u, |60 2 1 -IIAA* A(X xx - -1 *4
21 - (II((AA A (I) x -u, * xx + 11(X xx - -u, II)
2 - / (I(A4AA- - ()x+** -U x2 + || + |121 1P)
2 1 /0 (I(4''A- (X x U * u )| |||+101144 |0 x2| N 1
2'
where the last inequality follows from the assumption on μ. Now, we can come back to the estimation of IV x which due to the combination of the above-carried estimated reads as
* Wull
x Vul II S I * Vw, ll + 2n|| X -U * U1
providing the first result from the Lemma. The second bound stated in the Lemma follows from our assumption on > Vu,.w,ll |l and a and the fact that the constant e is chosen small enough to make [ -Vufi-.,,ll S 50
Lemma E.3. Assume that μ C1 min {
X -U, = (x= and || S 23( More-
over, suppose that tensor V * -U++1 * We has all invertible 1-SVD-tubes and that IIV * Vu.-w.ll S Scn with absolute constant 0₁ > 0 chosen small enough. Then, it holds that
U2+1 W1+1.1 11 s (1-
L U1, W., 11 9 * >Vu... (5) 101112211 2
(d'AA x *1, )1l) 11t, W., 1I
for each j. with 1 S j S k.
Proof. First, we will consider tensor U4+1 W++1,1 splitting it into two different parts, and then will conduct the corresponding norm estimations of each Fourier slices.
To begin with, note that for the tensor-con consor-column space of X. that is Vx. it holds that Vx * V + Vx= * V = I Iseee for example, (Liu et al. 2019)). Using this, we can represent U4+1 * W as follows
U4+1 * W = Vx * V U * W V U W1+1,1 = Vx V x4 +l * W1+1,1 (E.4)
where the last equality follows from Lemma C.1 due to the property Vx x * Ul+11 W1+1,1 =0.
Now, we split the term Vx VI- = xl141 1 into two parts using W; W. WT,1 WTT, I. which leads
to
V +V x-
= Vx
+V x- U * W. * W -xx+ V x1 *M141 W..
WT 1.1
W
(E.5)
To estimate the norm of Vx V * =u * W1+1. in each slice in the Fourier domain, we will use the above-given representation and estimate each of the summands individually. Let us start with the second one. Its jth slice in the Fourier domain reads as
(Vx Vx U441 W., * W.T. W 0 D DU
1111
(4) Due to the orthogonality of the columns of xL it holds that |
( x
x
f.1
W x 00) wb)
W W().. m7)) al In the Fourier domain, this allows us to focus on jth slices of the last one Wil
W +11. = cl"
x 41
31

---

Implicit Regularization for Tubal Tensors via GD
Due to the definition of the gradient descent iterates U1++, we have the following representation for its blocks U41 in the Fourier domain
U = Id + (AAAAAAA + x - -U,+ + + ) )) D
To upper bound the norm of GL", we want to apply Lemma H.3 Due to the assumptions this lemma that V + + 1 * W; has full tubal rank with all invertible t-SVD-tubes and [I x- * Vu.-w, ll I cx in addition to the conditions on μ and the decomposition of gradient descent iterates into the signal and noise term, the conditions of Lemma H.3 are satisfied
for the choice Y1 = 0/41 and Y = D and Z as Z = (A* X U, * )), norm of Gl as follows
( This allows to upper- upper-bound the
| S WLL (1-21 Whl ul AA *x - -u u, ( (X - (1-
+ (I0 + A(A x U₁ =,+ (0 -(X (XO 10 ll
Using now the fact that for each j it holds that
|| AA* X U x(,) (1)
(X(X) - 1 S A
x U, +1
and that |لااا| || - | s 3|| ||. we can proceed with the bound for the norm of GV-² as below
| || S |10
( w! (1- -1- u/u If + IIA I) X T - U1 * u4 31)
+ n² +0(()1²7| 2 + I * T - U₁ =u 11) W (111 1|
Further, using the assumption μ S c1 min { [111 -2, 211( xxxxxx -U, * U, ||| ) }. we get
|G S |00 [ 1.1 - -1 1( (1
1.1 A-
x)x* x -u. * u4 x4,1I) + 110
-|o|" w! || (1 "10!" 1 (AAA - - * TT -u, * u,! (l)..
Now, let us return to the first summand in
E..5 that is Vx U444 w, W. W.+111 Using again the fact that
Vx U1+1* * W1+1,1 = 0 allows us to rewrite as
V * U1+1* * Wi W. W = - * U4i * W.,1 * W. * W4411
(E.6)
Moreover, for the same summand, the corresponding jth slice in the Fourier domain reads as
T(iHT
x W!
G
+1,1
Due to relation (E.6) in the tensor domain, in the Fourier domain it holds that
F
1111 = -
X
(+1
41.1
which allows to represent W
W-( (i)
++1,1
WV) ()
111,1 = - (V !(
T() w
W W
x
1+1
1
11
Note that the matrix on the RHS above invertible due to the assumption that V Us+1 * W. has full tubal rank with all invertible t-SVD-tubes. From here, of can be represented as
c = X (41, (VL"
-(1H o() w!!) ( (1) w!!
W
x
(41
11.1
32

---

Implicit Regularization for Tubal Tensors via GD
According to Lemma
H.3
the norm of GfD can be bounded from above as
|| S 2p
|100 + IIAA'A(X** x -U,+ (1)+
(XO) - -
x=
() will |I
x-
(IV
1") 12 + -I) xx -u, * x1, )1) -11 |1
x= 00 w !
- 2p
x
1,
(1
|0 12 + 1144-11--))))- (x * x - -U, * u, )l) 11 * Vu 0 W (1)
< 2p
x=
Due to > * Vuu 1- S
50 from Lemma E.2 the fact that ||0|00| - [ell, and our assumption that | s 331 x|)
the norm of Gi can be further bounded as
| 1 S 1 (9 V
6L0 Yow 111211 + A * x -u * xx (1) |n!l II
x1
= 1 (91()) * 10 + IIAAAA - xx * x - -u 21 (l 10 wi
Since due to representation E..4, it holds that [1 * W |1
| = 11 x2 * U4+1 * W W |1 ||, combining the
inequalities for ||G|"| ||
and | together with T. (() 1,1 = (u, * W.,1) (6) leads to the final result
[11+1 W 10 S (1 2 [I((: * (.l1++WW.))) )11 + Qull(V )0) |1
u, (11) [ * W.W, + 2 I) T =u
|. )
The next lemma shows that the tensors We and W411 span approximately the same tensor column space.
Lemma F.4. Assune that the following conditions hold
U S 3||x||
(E.7)
/ 5 c|| ||
2x
(E.8)
1 Vu..w. S ck
(E.9)
11 * W.,j 61| < 20 Uu * WP (1),
(E.10)
A x -U,
* U1 \1| S co comn (x).
(E.11)
Then it holds that
[TT, *W411 S
11 1800 min'
(x)+ WW1 w - -
and mine (W,
21 isisk
Proof. To bound the norm of W.T. T We+1, we will rewrite W.,1 W.+1 in the Fourier domain with the help of Fourier
slices of Vx * Ut. First, note that due to the decomposition of the gradient iterates into the noise and signal term, it holds
D + = V = * W++1* WTT
1++ This allows us to represent the corresponding jth Fourier slices of V U as
VX T() F
c+1
++1 W (
t+1 which means that for each j, the matrices X U++
7() and T (()) W W
t+1 t+1
have the same kernel, and therefore D62 (()
X spans the same subspace as W H
41 ++ p
Due to this and the X
following representation of the matrices
0 - + +!!
(F.
Uhi -U2h wiTH
6. + +00 12 HH
(E.13)
33

---

Implicit Regularization for Tubal Tensors via GD
H.4 to estimate the norm of WH W t.1 2+1 taking Yi =U(4 E+1 and Y 0.0) and Z as
we can apply Lemma
z = AA* X
U, * *xxx,11 )) 61
This gives us the following estimate
1 + μ || |2(0)1100 1
| Trr 41
())
| w 1.1 2
V Yoowoll
(E.14)
min (V G1H (
x 1+1)
+ | (2 - (X X XUIH 0 ( T(
10
min (V 11
(+1)
To proceed further with the upper bound above, we will first show that in each Fourier slice it holds that
O Min
V T
(+1)
2
1 (())
min (7
isisk. k.
(E.15)
2
First, note that
V (
2 min (VX (T(HT(L W()
min ( (Td + u 1
Umin
(41)
(V
(HH (Id + p2 of w(t
Vo
VH
Wl 2411
mmin
t+1
V x
(Id + uz 1z Vo
(V TO
U. (W!)
Mmin
Jmin
min
(
vow)) ) nll (
x
VoV 1) min
(V
7 ++1
41).
Due to our assumption
(E.9 on the principal angle > Vul and the properties of the tensor slices, we have that
2 3
Cmin VVx Vul.w...) -V V 1 * Vee
min
>
4'
where that last inequality can be guaranteed by choosing > 0 small enough. Thus, to show that relation 1E. holds we need to demonstrate that l||| V H
2 2 Won be bounded from above by 1. For this, we will proceed as follows
1H x
20)
S n|| |
S 14 220) - (XD) - 01 + xOmn 0 (E.16)
U mb)
By the definition of 76), for the first summand from above we have
(20) (X
(x xQmn - ||
AA* x -u. 24, 1)(00 (86)x6) -
(I - A-A)(( x -u; uu )01|
(I A" X -u. u1,
and for the second summand, it holds that
- < || * X U, u1, 11 S 111011 + 112.,112.
This allows us to proceed with inequality 16 as
a 1 x Z
S r||(2 (I - A" A) (X T -u, U4 )|| + M 11 + 1124.
< (I A) T -u, u&!) ||| + 10 x11 S uuoo (x) + 11 1
34

---

Implicit Regularization for Tubal Tensors via GD
where in the first line we used assumption (E.7), and in the second (.sumption(E.II) The third inequality above follows from assumption μ and sufficiently small constant >> 0. This, in turn, shows that relation (E.15) holds and can proceed with (E.14) in the following manner
11 W
Hill S M
1 1+ 2p
W! 111
w
H
0 II
mmin ( (
| (XQI X 0 T
+ 2/
min w(
Now, using assumption (0.10) and the definition of Z(i), we have
W
f.1 211l S vIlV X= 1p III w w
-U (3) ( - - )(")
+ 4u1l (A' A(X
4n² (A A(X * xx -u, x
( 12| 1
Voowooll
x=
$ ell v W
x= w w0:01110 1110!! w( w
Awl((A () X Ui +u |I
4p A( x U, u, ! x=
Wowwolll
In the last inequality, we used the tensor norm as the maximum norm in each Fourier slice. Note that, similarly to one of the estimates above, we get
A(x - U1 +2, )11 < X + x T - U, +4, || IKAAA - X U1 * 2T,))l
$ || + |2.,11 + co (X) 1|
(E.17)
where the last line holds due to the assumption
14, S | and that is small enough.
< |Ma||| < x| constant >> 0 can be chosen so that 4p || z 4800 min (X). together with E.17) and E. we can proceed with the estimation of
Now, since μ c|| -|| | W < [4 < x and ( ()
WH W ()) t,1 2+1
WW W0) e+1
S
4806 min (X) + 11)
( V 000 || + 4pcc min (x)
Using the assumption μ c<c|22 cc|211 and choosing 0 small enough, we obtain that || || ( will S 1.
Note that this
implies that miin !W. W ()) v
|| ||
W 11
2 which finishes the proof.
Lemma F.S. Assume that the following conditions hold
11, W.,, 11 < 20 (U (1),
(E.18)
[1, S 3/121111
(E.19)
| Vu..w.l. 11 S à
(E,20)
# S c|| x2
(E.21)
11 W || S cr |||
(E.22)
AA''AI)(XX X U, U || < 2o (x).
(E.23)
Then the angle between the column space of the signal term U, We and column space of X stays sufficiently small from one iteration to another, namely
V x= Vulu |1 I
4 mma (x)
1V | Vu..w.
+10mp|[(A'AA -X * XT u. * 247))1 500 x -U, x U,T11
35

---

Implicit Regularization for Tubal Tensors via GD
Proof. To estimate the principal angle II x Wun we first investigate the tensor-column subspace of u+1 We+1- By the definition u+1 and W. W. + Wi,1 * W., =I, we have
e+1
U++1 W (I + u(A A)( xx - U, u) U, W
+I++ (z) uu W.* W. We+1 + [I + n2) U: WT,1 W. W
where notation 2 == (A*A)(X x x This allows to represent jth slice of u Wi+1 in the Fourier domain as
U
( 141 (Id + mz (2) w ()) 1O W + (Id + u w ( W 6 (
411
with Z6) = () x -1, + U, )6) Because of this representation and decomposition E. 12, to bound the principal angle between Us+1* W441 and X, we want to apply inequality (H.5) from Lemma need check whether for
E.12).
H.4 but for this we first
pb) = 0 W W ()) (v 0h W W
i+1 (HOmOo
the following applies
(1 + pú) + uz 5)) p( 1 For convenience, we denote B6) := μz + p() + μz pli), Using the triangular inequality and submultiplicatiiity of the norm, bet the first simple bound on the norm of B()
|| S u + (1 + all 111
(E.24)
Note that P() can be rewritten as
pú) D GJ
W U (1)
-1 ((
which allows for the following estimate of its norm
| s |
1.1 (2 H) (
f,1 22
(W.
" Go w
"1
|
|
1
641
|10
W
min (D)
min
From here, using assumption
E. and lower bound on miin
(W! Hj) w 1+1
()
from Lemma E.4 get
| W +1ll.
(E.25)
Using this and the definition of 2(), we have
|| | S (I((AA x 24 U1 )0,)0011 + 4 A)](AAA))2X TT U1 * 24,
(F.26)
Due to the assumption on we can bound p1| ()) * X -u * u, )001| follows
A)(x * x - -u, x u, |0)
< (I)(AAA)( * x -U, =l1 |00
< #I[[I A) x U, U, IlI x X U, +
< 2 min (X) 10 x xI 1
where in the two last inequalities we use assumptions e > O can be chosen sufficiently small.
E.23
191
and E.21
with the fact for the learning rate constant
36

---

Implicit Regularization for Tubal Tensors via GD
This, in tunn allows to proceed with inequality (E.26)
| S A)((A=A)( X'
U, + 5001 + 8| s)]
www.w.lwW000 w ++1ll-
(E.27)
Now, applying the bound on |
w f || = IW!, W from Lemma E.4 and similar transformation for
(((A))(( * x U, * U )6> as above, we come the following result (E27))
|| S u|| X x U, * 21 + 14 600 min (x)² + 8l|u, * W.lllu * Worll)) b * w.l.
+ 33 || A - * xx
U₁ * u!
To show that this bound above can be made smaller than one, we use assumptions [|]||| s ||, which leads to
E.22p. E.23) and that U * Well V
|| || S |||| || X
U, + U1 || +
600 min (x)2 + 8c
1
Mmin (xt R²2
-31211 1V * Vu,.w. |l + 33pco min (x)
10 112
+ p.c.
300 min (x) + 33ucc min (x) S 1,
with the last inequality following from the assumption on μ.. In such a way, we check the conditions of Lemma H.4 to be able to apply inequality (H.5). This gives
G)H MV
H V
(1-12 1 2 2 (X(1)) m
S
x
641
2 (H W2 t
+ = - (8OXXU) T( || + (1 (1+ =112211)))
() (W
Jiin (T!'
Mmin
2+1
W
2
+ 57 | + (1 + =
min (W
W ( 4+1 min (U
W!!!!!
Applying again assumption E8. and a lower bound on min 1
()) 1+1) ) from Lemma E.4 as for (.25 in addition to
E.22
we get
s I 1 x
T wy || (1 (1-5 3 oi (xx)) + +11100) (XO) XOOI 0 ,
x-
00 why
+ 8(1 + 1
|| + 57 (n12 + +1(1 + 11 121)
Now, making (1 + 1 11) < 3 by choosing c > 0 small enough and using the properties of the terms involved, the above
inequality gets the following view
|| S | x+
V Yommolll |l (1 -
3 -m (x)) + uI|(I - A'" A' * X - U2 u,=u;)11
x-
1 |l + 57 [1| + 12 w()) 11] 2
b + 32
(E.28)
To proceed further with E.28 we will first do several auxiliary estimates. We start by bounding the norm | w
#1
Since it holds that ||
ITT Wet1ll. from Lemma E.4 one gets
H
S 1
4800 min x
+
12 We 14, * W..
IIV x-= Vu.-w.ll
4u
(A'AA (X x
Ui 24,)
< 1 4800 min (x) + 300 min
(x)) x [V x- * >Vu, + 4p * xx - U, xu I
< य س mmn (x) (x)) x Vu.-w.ll ||||+/10t
I) -2,,
(E.29)
37

---

Implicit Regularization for Tubal Tensors via GD
where we use in the second inequality that |i Will < [1 < 3|| and 1 We.ill S ok [|| by assumption,
and in the last line that 0 can be chosen small enough. Using this estimate, let us bound from above the squared term in .E.28 follows
A | + 12
E | + 1
0
mnn
Vx * Vueaa.
+ 48 (2 x - U1 * xu
200
-. T( || + /r 0 m
(x)
11 x= Vu..w.ll
200
+ 49p (A" A - [) * x -1 * (, )1
From here, using Jensen's 's inequality, we obtain
XX TO 12 +3,²² I x
[1llz/0||+ 12 W 2) ()
11 13
min
1 x- * Vu.-w,
T +1
2002
49 yr (IA" (X x U2 21 )|(
Now, we can come back to bounding
(E.88)
proceeding as follows
G
S 11 x- Vu.-w.ll
min (x) (1-50mm
4u
min (2)
win
300
+ 129 A (x X Ue * x2,,)1
+ +171,² | (1) X ( 112 + 11² 1710
min (X)
VV x-
Vu..m,11?
200
+ 171 49² n² (I A - Ix * xx -U,
T-u; * U, )11
$ V * Vu-.w (1 (1-1
11
F (x) + 4f 2
171
300 min (X)
+
fu.coo min (x))
3
2002
+ 171 X * x
-U, + +21 1|
+ (129 + 171 (1( A * x
U. * U |||
where for the last inequality we used assumptions (.23
F.20 and E.21 and the properties of the tubal tensor norm.
Now choosing constant e > 0 sufficiently small, we obtain that
V HH G
W
||
(1 >
1 - xx) | Vu..w. + 200p²|| * X UM * U 1|
+ 150 (A" A I) * T
U, * 21,1 )ll-
Since the right-hand side of the above inequality is independent of j, we obtain the lemma statement.
The following lemma shows that under mild condition the technical assumption
Mu+1l s x
needed in the lemmas above holds. Lemma E.6. Assume that || 3/
3/ ||. 1 1 | -2 and that linear measurement operator A is such that
II(A'A (x x U, u, \I| s 1
Then for the iteration t + 1, it also holds || S 3|
Proof. Consider the gradient iterate
Uk+1 = U1 + A(X * X² -U, x U.)) xl,
= =u: + -U X -U; * u,) +1 + IX x -u,+U + 2(, x Us
=(I - -illt u.)) U1 + 1x x Ue + p(A' I) x U, x U, ul.
38

---

Implicit Regularization for Tubal Tensors via GD
To estimate the norm of 1-1, we will bound each summand above separately. Due the assumption on μ and the norm of
4r we have μ S 27 X 2 [24 -2 This allows to estimate the tensor norm of (I ,1lt 21, ) * xt, via the norm
of matrix block representation in the Fourier domain. Namely, assume that matrix U, has the SVD = VEW". Then for
matrix (I pll, u1 2, we have
(I --dl * uu * uu VEW" WEEWWWWEVWWW VEW" VEW" WV V(Σ P(E-~E>)Wi W
From
here,
since
# 3
1 X 2 - 3/3 ||||||
and U = | ||.
it holds that
27
[[ - --l, * U, * u - |24 - 1 [4, 1 | |1 11 2. Besides, from the submultiplicatiity of the
tensor norm and the triangle inequality, we obtain that
|M++1 || - (1 1 12 + + + A
- I) * X - -U * U, MAll
(E.30)
$ (1 / 44 |2 + 2 [2]|
(E.31)
where in the last line used the assumption on || (AAAAA - I) X - -u xU ||| By combining inequality (E.31 with the assumption S 27 x S
1 | we obtain that [M++1 I x|| which finishes the proof.
The following lemma shows that U, W. W *tt converges towards X x², when projected onto the tensor column space of X. Lemma E.7. Assume that the following conditions hold
Uulll S x
(E.32)
1 S c.
Vnk x 11
(E.33)
mmin (U1 Wi) 2 V10 minn (2)
(E.34)
V
-Vu+w. S cx
(E.35)
and
max {11D ())-))(>))l IVu.... * A I)))))l ((4-A-I)(O))))) 2111111111=
with : x x+== x - U1 U, Then it holds that
x * UR U ||r S 33IVv= * (X * x U1 M1xx(,))1== + 1 WT,1 WT,, xu ||r
(E.36)
as well as
- -U, u || S <4/V>= (X x - U, * U, )|r + |1, * W., WT =u, ||F
(E.37)
and
IV x (X TT_ - U1 * u U142)ll < (1
p
22
(x)
|V * (X * T -Uu * =1,)1le
200 min
(X)
+ P
|
We,1 WT,, xu, ||.
(E.38)
100
Proof: We start by proving the first inequality (E.38). For this, let us decompose V +ld, * U as follows
v V U, * u = VI * U, + uU Vx * V + VI-- U, * U, * Vx1 *
then using the triangle inequality and submultiplicatiiity of the Frobenius and the spectral norm, obtain
|| I x= U1, * 24, ||| < | +1;
<VxlF + 1 * Ud * UT Vx l|F - VV x= * (X' * x T
-U, * U1 * VxIlF + II x * *U * U V
< VI x (X TT -U )((F IIV x1 U uT Vx ||f,
(E.39)
39

---

Implicit Regularization for Tubal Tensors via GD
where in the second line, we used the orthogonality of the decomposition. Now, we will work additionally on bounding the norm of VX =U U x obtain (E.38). Here, we will use the orthogonal decomposition with respect to Wr and We,1, which leads to
IV x- * U x U Vx
|F S V x zu, * W. W =u, * *xx 11l + II x- *U, * Wt,1 * W.,1 * uu
Vx UI
$ V x= U, * W: W. uU *Vx || + 1 WT,1 W., * uu ||
Now, for the first term above, we get
x= +U+ We + W.T. xU, Vx+11== 1x * Vu.... Vuow U₁ We * W. xu, * >x=11ø
Σ
1 * VVu. * Vuew uu * W,+ W. uu *xx 1
1=1
Σ
x V... uio, w. (
HOTH
||
x
Σ
W ( u.o. ( (V@)HV ). 1=1
x2 w. u. u w ((
v
x ||F
< max
18isk u.
max 1sisk
x v..
.)
u. u.
Up W www. u
lF
1 Vu..w.ll
| X. Vu k.
Vu.. w (i 1 v
x ||
Omin (Vx1 x1 V)l...))
11 -Vu...ll
( U x-
66 v(
||F
x=
Omin (Vx1= & V))..))
j=1
11
-Vu..w.ll
1V +le W. * W * zu; * Vx=1IF
Jmin (V * &Vu....)
-Vu..w.ll |I
112 +U, + Vx=
mmin (V
x= +Vu...
VV x * -vu.w.ll
1| (X * x -1 * u, * V Vx-ll |FF
mmin (Vx
x *Vu....)
V
Vu.ew.ll
11 (X' * x UU x u F||F s 2 * *X* -U, * u )ll
Omin Xx1+ ).....))
where in the last line we used the assumption
EE.5 Them, using just established bound together with (E.39), we get
I *ld * u, || < 3 (X T Ui * =1,,)lr + [i * WT,1 * W.,, * u Ir..
To get inequality leads to
E.37 we use the orthogonal decomposition of X * X U, x U, with respect to Vx and Vx+, which
|X T U. * u, || VIV (X + x UU x U }|| + V +X + X
U1 * U1, ||
= | (X = x - -u, [ )l|r | + | * =l, * U 1|
< I (X X -U, +1, )|[F + IM W., W., * u, ||F.
Inequality (E38)) follows from the two inequalities proved here and Lemma 9.5 in Stöger & Soltanolkotabi] 2021). The building stones for this are the properties of the tubal tensor Frobenius norm. Namely, the Frobenius norm of any tubal
40

---

Implicit Regularization for Tubal Tensors via GD
tensor T can be represented as the of Frobenius norms of each slice in the domain, that is
IT P
|
and ||] S Vn-kk/T T| Besides, the Frobenius norm of the product of two tensors T and P can be bounded as below
k
[T P|F 1 (10)pp0111 S
|T
p
1| S |T||
max 1sisk
Now, have collected all the necessary ingredients to prove the main result of this section, which shows that after sufficient number of interactions, the relative enror between U, U and X X becomes small.
Theorem E.1. Suppose that the stepsize satisfies S Ci satisfies RIP(2r 1,6) for some constant < S VF
Vks
*|| -2 for some small ei > O, and A: Suxxxk + Rmm Ser & (0, 2) and choose a number of iterations t.
C1
1²
min and min(n, Rj'
such that miia (Ur W..) 2 y. Also, assume that 1 W...I || I 2%, 1 |l 3||21,, x
V x= Vu,, aW.. 11 S C2k" 2 for some small 02 > O. Then, after
i 1. mina (2² In (inn {1,
{1,
KT
} ||
k(min (n, R} 7
additional iterations, we have
1 * U
Xx X ||
S // 3/16 (min RR}
-211111/116
21/16
|2
Proof. First, we set
f min {t2 t, Jmin (V U.) vio min {
and then aim to prove that over the iterations t, s ti, the following hold:
Tmin ( x1)) 2 1 (1 (1+5
(2))2 (x)))
|14 * We.lll 2 80pc2y S00pcyyTommmlee (x)))()))) inc.
IIV Vu..w.ll S -2
Intuitively, this means that over the range f,, < f E f1, the smallest singular value of the signal term V U2 grows at faster rate than the largest singular value of the noise term Ut * W..L.
For = t., these incqualities hold due to the assumptions of this theorem. Now, suppose they hold for some between. t, and f,. Wl show they also hold for +

---

Implicit Regularization for Tubal Tensors via GD
First, note that we have:
- X -U + UIl
= - xx -u, W. W xu -u, We,1 WT_. u4
A - (I) * x -U, W. * W. *4I)1 + A - [[( W W..1 * u1!i! I
(a)
<övkr |x x xx -u, W. W. uu I +| W..1 +Wa1 xU,
<ōvkr
kr (1 x x
x1 *1 [2, W.* W. 4I,1 + +oVEliu, W. * W..1 u1 11.
=5vkr (12112 11, w.ll3) + +oVElU WIL WT, +U 11-
<ōvkr [1x81]+ + (?2) + 5vkl * W * Wi. uu Il- 5v (min R Ur WA,1 Wt,1 U, 11 * 1|,
(
<ōv Kr
<100 1 + 6V
1108vKrk' min x ( R} - r) * We,1 1
(c) < 10cg Vhx min| x)² + 48 46 R] - -r)? (1 + 00 (x) (2)))2((-1))
(d)
? <10c; Vkr o min ) 2 88 / 86vk(min/nn, R) r)7 mmina (x))// (2)
(e)
<40c Vkr 2 minl 2)
In inequality (a), used the fact that A satisfies RIP(2r + 1,5) (and hence, RIP(r + 1.6) and 82)(2,8)), and thus, by
Lemmas G.2 and G.3, also satisfies S2SRIP(r, 5v kkr and S2NRIP(8 (OvR) kk). Inequality (b) uses the assumption [[ee| x|| and the fact that U₁ WT,1 WT, * has tubal rank at most min (n. R} r. In inequality (c), we used the assumption
6 < along with the second bulleted inequality assumed by the inductive step. Inequality (d) holds due to the
definitions of l and to and the fact that 4, S S t,. Finally, inequality (e) holds due to the assumption y
C2d7 (2())
K min(n, [7
If C1 is chosen small enough, the above bound is less than | ||. Then, along with our other assumptions, we can use Lemma E.6 to obtain || || <
X||
Next, we can use Lemma E.1 along with the bound min (V* * Ut) S 1 Tmin mmin (X) to obtain
v10
miin ( ++++1) 2 min ( + U1,11 *W++)
1
> min (V> 11))
[+
Po (2)²
-uo mia (V * u2))2)
4
mia ( * (t))
[++
((0min())
10 u (x))
4
1
miaa ( ( * xli)
1+
@in (x))2
7 1+
1
(1
guo (2)²
1
1
= "
| 8
u (2)²
Since mmin (V U441 * Wi41) = Ominl ( * M(41), which is positive by the above bound, all the singular tubes of V U441 Wen Ve are invertible. Hence, we can apply Lemma E.3 to obtain
42

---

Implicit Regularization for Tubal Tensors via GD
1. U241 W1+1.1 01|l S (1-5)
U W.,1 01122 + - * Vui... (1) 1|
+ +2ull(A'A I) X -u, #1 }11 |14,, We, 6i
(1 $
47² 1 80pc2 ho (2) 2(1-10)
+9pcz1 -apko=-11 11
2
+ 2p 40c vkn 20 min (2))²
1 W. |
$
<11
P 472 1 + 80pc2 V min (2))) 2(t-2.)
+ +9uc2omia min (x)
2
+ 80ciuViks /n (x))
[1, W 1)
1 + 80c Te -2 omnnn m2)) (2)) Uu, * Wi ||
+ S0capukoonaa (2))
[1 W.,i |
S 27 + 80cs j00m 1-tot1
where we have used the inductive assumption that the inequalities hold for t along with the fact that x Next, we will bound the term using Lemma E.5
|| 0 2 1.
| x-
-VuIi-Wee ||
11 402
4 minn (2)
| * Vu..w. || + (A A - (X * X -U, * u, ||| + 500p² 1 x - 24 ul 1|?
1
oiin (2))
02 + 150 40c1 - mmin
20 (x)) + 500 (1|21 + (12,,1])
4
1 1
omin (X)
C2R + 6000μcc V KR -2 2mmin (x)) 500μ²
2 + (||x||
1|
4
min (x)
02N + 6000 V /kk" min (x)² 50000μ ||
4
min (X)
02K + 6000 V Rom 2 a min ))² + 50000/z . c | -2, ||
4
H
Omin (2)
C2k + 6000 VRR -2 o ) + -41 2|
=
4
M o (2)
O2n 2 + 6000μcc V Ten - o (x) + 50000μ - - 2x2 o (2)²
4
H min (x))
O2R + 56000 Vin-2 mmin (x)
4
Here, we have again used the inductive assumptions along with the fact that π || (2/iiin(22)) If we choose e₁ sufficiently small, we will have V
W S c2x-2
Therefore, the four bullet points hold for t + 1, and thus, the induction is complete. With the above bullet points mind, we note that
V0 min (x) 2 m (V> * (1,,) 5"
1
1 g uo min min (20)2
41-4.
and so,
2
log
mmin (2)
70
16
2
mmin (x))
t1 to <
<
log
ma (x)
rv10
log
1
[rTmin (2))2
43

---

Implicit Regularization for Tubal Tensors via GD
where have used the inequality (x) iteration 1 by
for 0 <x < 1. Furthermore, we bound the norm of the signal term
11-1.
Ur * We.1 |1 S 27 + 80pc2 Ro (2))²
Omin (2()
1280cz
S 2%
v10
7
miin (2)
1/64
24
V10
7
- 3y 63/04 mmin (x) 1/64
3/ min (2) 1/8. x
where we have used the previous bound on $ - tw, the fact that > 0 can be chosen to be sufficiently small, and the fact that minn (2) 2: 7.
Next, we set
300
In x/4
||/////4
t2 11
[1..min [
18
h(min(n, R} -r) 77/4
13 min finf124:
(V -))
uu We, W U 10 2 || x -U, 21,1 [1]]
i ts)
We now aim to show that over the range 1 < < f, the following inequalities hold:
1
Tmin (ld, * Wi) 2 min m * u1)
2
min (2)
v10
liee, Wr, S (1 80pc2 mimmmm((X))) 1-61
11,, Way1 ||
|14,11 s 3||
I * Vu..w.ll S 22
II x -u, u1 S 10 (1 L min (x)))==6
||
For = 1,, the first four bullet points follow from what we previously proved via induction. The last one holds since we trivially have
V x (X * X -U,, *UI))lE < V x (X* * x - -Mi, xU II
I Vkrll X x -M,, * *1,771
5 Vkrll X x xT| |1 /rrrllle * -,
S x 2+ V 1|
- 10vkr|x*1
Now suppose all the bullet points hold for some integer E [t, f- 1). Again, we aim to show they all hold for t + 1. In
similar manner as done before, we can bound [1 - (X * X UI U1 )l < 106 Kr | + / R}
( * Wt,, 1| and then continue as follows
44

---

Implicit Regularization for Tubal Tensors via GD
[1A A A (2 * x² =u
$105 kr 121 +8vk(min R) - U We,1
$10
C1
vkr n² o (X)² + 8v (min (n, R3 r) (1 80pc, v min (2))2
2(1-61)
U We,,
N² V
$10c, vkr 3 min (x)² + 8v 8v (min n, Rt] - r) 80pcs v Ko min (2)²² 2(t 2(t-t1)
-//7/4
min (x)
80uce20 (2)2) 2(12-11)
$10g 2 amin ) + 98 10vk(mmnnf n, R3
73/4 Omin 1/4
5
18/1
O(oz)
<10c1 Vkk 2 min (x)² + 96 Vo0immn, R} - r)
1/4
77/4 J (x) 1/4
18
k(min(n, R2 r)
y7/4
<40c1 Vkk 2 omin (x)²
where have used the bounds 5 < "+/F' inductive assumptions and the definition tj.
||
KO (2), 11 We,, S 3-7/ m (x) along with the
Next, we note that min ( u2) S 1 o (X), then we can use Lemma E.1 along with the inductive assumptions to obtain
min (11+11 # We41) 2 min V +1++1)
min (V x Uu+1 W.)
min
V xl.)
1
4 1.7min (x) 2-- p (Vx 21,)
(1
min (V u1))
[
4 1 (x)2 3- 1 m (2)2
(2))
V *U,))
min
mmin (X)
V10
Alternatively, if min (V> m the fact that I c X 2 for sufficiently small e₁ to obtain
24,) 2 min (X), then we can again use Lemma F.1 along with the inductive assumptions and
miia (11+1 W441) 2 miin (V * U(+1)
min V 2 U4+1 * W.)
min V x1)
1
4 1. (x) (2))
-. (V 21.2
IV IV
2 0 min (X) (1 pa (2,)))
1
2 minn (2) (1 1=1(2(1113)
2 min (X) (1 - 11
2 F min (X) (1 - 901 2)
1
Fmin (X)
V10
In either case, we have miin (1141* W++1) 2 miin V +++ 2 1 miin (x))
45

---

Implicit Regularization for Tubal Tensors via GD
Again, since min (V> U4+ Wi) vTO min (X) 0, have that V x u+t11 W₂ has full tubal rank with all
invertible t-SVD singular tubes. Hence, by Lemma
E.3 we again can bound
M2+1 * W1 < (1 50pue2/kmmin(X7)) (+1-1
[1,,, W.,.
In the exact same way as before. we can use Lemma E.6 to establish [| S 3|| and use Lemma E.7 to establish
[V x
Vu,, ll I c2R=
To bound [V* (X * X Uu1+ * U4 (1)lll, we will aim to use Lemma
E.7 By the inductive assumptions, we already
have [ S 3||2||, mii (U1, W.) 2 vTo min (X), and V -u,-w.
S c2x=? To derive the remaining condition
of Lemma
E.7 we first split
V * (I -I- AIAAA))( * x -u+u )lr
VV * (I- (x * Xx
-U W.W. uu -U, + Wt,1 W. *1=
V * (I AAAA)(( x -U, W. W, * 1l IV (I - A-AA) W.,1 WT * +U
To bound the first term, we note that X * X - U W, W + +U, is tubal-symmetric with tubal rank at most 2r, so we can write it as the sum of two tubal-symmetric tensors 3, 22 E 5nxaxk with tubal rank at most r, and then apply Lemma to obtain
IV * (I A x - -U * W. W * uU
1V * (I- (I- + 2
S II (I-AtA)(Z Il + IV *I (I (2)))l
S +
S 2/
=8/2/x * x -U; We W, =u ||F
S <8V2|x x x xT- -u; xu! 11 ||F
For the second piece, we use the symmetric t-SVD to write U: We,1 W.T1 =u, = E, V: * * V.T Then, we can bound
VI (I - AA W. WT =1,))le= =
Vx Vx** (I- - A-AA (I-AA)
EVi*s V.T
Σ Vx (I- -AAA) (v:* 12
< Σ 8 1||1 * V.
Σ 8|lsill2
8 I|l, We.1 WT,1 =1, ||.
S 8 /k(min (n, R) - r) Ue WT,1 WT,, xt1
s x X T - U1 +2, ||r,
where we have used the fact that 24, WT,1 W.T. * ut has tubal rank S min(n, R} - r along with the definition of f3.
46

---

Implicit Regularization for Tubal Tensors via GD
Hence,
IV (I - A) * *X" -u=u") )ll
< (I -A'A)X * _x -U W, * W =11))+++112 * (I A)(U, We.1 * Wi =u!)l )l
<6v2 * X -U U 11 + 5112 * x - -U, * U, ||F
Sen 21| * X U, U F:
where we have used the assumption that 8 <
4 xtvF S cR-
Similarly, we can bound
Ii * (I- A) X - -U u1))IE S cR - * X Ui * xU1 le.,
and
-U-AAAI A * X -u, Ui]l cxx xx Ue 1E
Then, by Lemma E.7
we have
[x x U1++ * [1 S (1
p
o (x)
11 * (X' xx -U xu Ill
200
(x)
+
min
Ur Wv,1 WT, +t,, 1|
100
By the inductive assumption,
V (X x x -U, xU I
10 (1 14 min (x)3)
t-t 1|:0112.
Also, using the inductive assumption and the bound from the previous part, we can bound 1 * We,1 * W uu || S Vk(min (n, R} r)] * W., * WT,1 * u |I
Vk(min (n, R} r)], W.
S / Vk(min(n. R3 - r) (1 (1+ 80pc2 v To (x)²) 2(1 2(1-21) (o)
11 * We..l
S (k(min(n,R)) R) r) (1 80pc2 v ko (x)) 2(1-21) g7714 mmin (x)) 1/4
Since & S 12, we have
300
5
1|/0////1
t-t t1 S t2 t1 <
In
1/1
Hv Ro (2)
18
min(n, R} 7,14
and thus,
[M We * WT,1 =U, 1I S v /(min((n R} r)) (1 80pcce v Veoomina (x)²) 2(1-t1) 7/2 7/ omin (2) (2)
2 /kr (1
11
min (2))) 6-11 ||
400
Combining these inequalities yields
| - (X X -U441 * uu 11111 5 (1
1
2
min (x))
x (X x X -U, * u, Ull
)l
200
2
(x)
+ μ
min
11, * W * =W., * 21, 1|r
100
10v (1 400 u. (28)2 1-6s
11
(x))
||
min
200
+ μ
x2
min
(x)
5
Vkr (1
/ T (x))2
t-t1
|
100
2
400
1+1-4
10 kr
1
1
nn min (x))
||
400
47

---

Implicit Regularization for Tubal Tensors via GD
Hence, by induction, the five bullet points hold for L +
I = f2, then, we can use Lemma E.7 the previous bullet points, and the definition of t2 to bound
| x U, 2 1 S 4 V
x=
(X + x -U2 (xx,,)ll
+ +112, WE_1 W.J UT l|
2-11
8-h
$ 40vkr kr
1
400 min (2)²
||
++
5
Vkr
kr
(1- 400
1
40 min
mi)mmi)))) (2))2
||
2
8-61
85 Vkr
1
1
1o (2))2
||
2
400
2 v kr
18
5
K
1/4
V
k(min (n, R] - r)
r
|/117/4
77/4
-3/4
||
$ k5/4,1188 x 3/16
2111//12211111//11 (min((, R3 (5-))) 21)
11/16
If instead we have f = ts. then
11 x - U; U ||
<411V>> * (X* * x -U₃ * U; } + 1 * Wt * WTT F. * u 1
<4|X * xx - U || + 11 * Wi_ * T. *U; ||
< / k(min (n, (1, R] -r) + 1) Wi,1 W.T. f1 +4,11r+ 1|4, Wi,1 * W._ u 1|r
4(v k(min (n, -r) + 5) 1 Wr,1 * W.T. f. 11
< 4( k(min (n, [1 r) + / min R3- r U; Wi,1 * W u
< 4( k(min (n, R| r) + 5) min(n, R} - M W w.ll ||
[ + 80pc2 v Ko min (2)) 2(E-11)
V k(min (n, R - r) + / k(min (n. n, R3 r)
11 * 1i..ll
2((-11)
<4(y ((min(n,11) R} r) + 5) (((min(n, R2 r)
[ + 80 v Kkamin (2)²)
-9, 63/32 m (x) ) 1/32
Sk(min(n,R]- R3 -)
5
1/4
r k(min(n RR r)
|||| 7/4
((22)
63/32
minn (x))/32
18
7/44
||
7/4
O(ez)
|2111//12
Sk(min(n,1t] R3 - r)
1/4
F.
2 21/32
18
k(min(n, RD - r)) 77/4
16 k3//32
Sk(min(n, R3- r)
k
1/4
r
||/1///4
7/4
O(cz)
21/16
|| ||
21/32
||x]| 1/32
18
k(min R) -r)
77/4
min (m, R}
k//32
((min(n, R)
|//////4
O(oz)
1/4
21/16
R -11/21 || 11/16
18 k
min(re, R222/332
k(min (n, RR -r)
7/4
2 //4,1118 13/p333160 3/16 (min (n, R}-
r) 3/3888211 21/1611 11/16
So in either case, we have
| * X - -U,+ U1 || S 1//4,,1/8 3/16
(//04///s-///mmmmmnm) (minfn, R} - 2/8/8 X | 11/16
and thus,
18 x TT -1 * =1,11 ||F
2 2/8 k 3/16 (min (n, RR} 2/368,21/11611 -21/16
|
48

---

Implicit Regularization for Tubal Tensors via GD
Finally, by the definition of Z, we have that
to I t2 tx
$ (t2 11) + (t1 - ta)
300
In
5
4/44
|| |
16
log
2
min (x)
HV min (x))
18
V k(min (n. R. - r) 7714
p. (2)
\v11
hr
||2811
In min
110 min (2)
k(min ni, RJ - r)
7
F. Proof of Main Result
Now that our analyses of the spectral stage and the convergence stage complete, we ready combine these pieces obtain the proof of our main result. Since A satisfies RIP(2r 1,6), by Lemma G.2 A also satisfies S2SRIP(2r, v V2rr5).
Hence, & : (I A () X
satisfies
| || = II(I - A ( X xT) S 22kro X S 2kr ox 4 1/2 || cvto Torki=--onn 3mii
Then, by applying Lemma D.9
with E = _ we have that with probability at least 1 - k((6))t ke -ER
ke- 30(R-22+1) ke -eR 2 1 ke- 3R ke-
Okee-Ry after
2x² Vn
4.
1A07 minn ()) In
03v min(m; R$
iterations, we have
14 |l $ 23(21 V Vue, w. || S CK 2
(F.1)
(F.2)
and for each 1 S S k; we have
or U1 *W (1)
2 4 a8
1
(F.3)
σi Ur * *W..
(1)
8 0.
(F.4)
(F.5)
where (since R 2 3r and is constant),
16k²
2x² vn
Vk VkSBSVK
Ög //mn /aiminn
R}
By choosing
11xx
40romin (X) 22 min(n, n, RVVk
2x Vn
a S
03 23 En/minnn, n, R.
we have
1
C20min X
0 S
4
2
min {n, R)
Also, -
a=3 2
27 holds. Therefore, apply Theorem E.1
which gives that after
} ||
KT
- t. S
mim (2)² In min {1,
le k(min R) - -r)
49

---

Implicit Regularization for Tubal Tensors via GD
iterations beyond the first phase, we have
1 * U X X I| < /,5
(min R3 (//10/mmmmnnn
1))3/821/181111 ||| 211116
x11
The total amount of iterations is then bounded by
E= t. + ( - tx)
2^
p0 (x) In
2x Vn
+
min {
kr
) ||
C3 min (n, R8}
mo (x)
k(min [n, R} - r)
2x² Vn
kr
||-21|
min (2) In
min
03 min (n. R}
k(min/n, R2] - r)
2x vn
kr
4 4|1 II
22
x2) In
min
min
03 min R}
k(min Rt) -r)
o3
24
x2) In
Ci
KT
min R}
[nmin(n, R) -rr) r)
ka
where we have used the choice 7 1a and the fact that 3 2 Vk. Finally, the error is bounded by
1 11
X * x
x /555 3/16 (min n, R} 133/8222/111 ||
|
221116
x 1/44 -//6 (min n, R} r)33/ ( 21/16
X1|
21/16
21x²
2n²v
21/16
S 5/4 2/8 ///8 x///////////// 3/16 (min Ry // 21/32
23y Piy/min(rr R.
X
21x²
C2x²2 vn /iminnn (n, R2]
21/16
2 2611332 1/8 3/16 (min(n. R) - -//3/8
|||
desired.
Remark: One could obtain similar results for the cases where S R < 2r and 2r S R < 3r by choosing the parameter e (0, 1) appropriately.
G. Restricted Isometry Property
In this section, we show that measurement operator which satisfies the standard restricted isometry property also satisfies two other variants of the restricted isometry property fact which used in our analysis of the convergence stage.
We say that measurement operator A: 5mxnxk + R satisfies the spectral-tor ppectraltoo-spectral Restricted Isometry Property of
rank-r with constant > 0 (abbreviated S2SRIP(r, 5)) if for all tensors Z E Snxaxk with tubal-rank <
[|(T A () 2
We say that a measurement operator A: SnXnxk + mm satisfics the spectral-to pesctral-to-nucle to-nuclear Restricted Isometry Property with constant 8 (abbreviated S2NRIP(6)) if for all tensors E 5nxnxk with tubal-rank S r,
- - A A) Z - Z
Lemma G.1. Suppose that A: Srxnkk - Rmm satisfies RIP(r r', r', with 0 < 8 < Then, for any Z,Y Snxnxk with rank Z S and rank()) < r', we have
(((I A) 8
50

---

Implicit Regularization for Tubal Tensors via GD
Proof. Let y ||2 y so that | | | Note that Z + ++y E 5uxnxk and 2 y E Snxxxk both have tubal
rank < r'r Then, by using the identities ||a + bll2 |a - bl2 = 4 (a. b) and l| bll² + ||a bll² = 2||a|| + 2
(which both hold over any inner product space) along with the fact that A satisfies RIP(r + r', 6), we have:
(I--A- (I-1'A)(3),)) = (2,y" - (A'A(2))3")
(2,y" - (A(3), A()"))
7 1I(E + +>') + - 7 - 22)1
(2.y)
1
- -1-6)] +3 11 (1 8)| - 3
(2,3"
4
1
(1 + - - 2 2'1 + 1 (1 + y' + -1
(2,y"
4
6 (1
1 + 111))
2
8 2 || ||
In similar manner, (II A ())) since Y is scalar multiple of y", we have
-| Hence, K A-A),)))), S 6| |>||>>
Then,
|||| i
| I - A3))
1 >| 81 ||
Lemma G.2. Suppose that Snxnxk + Rn satisfies RIP(r + 1,))), where 0 < 81 < 1. Then, A also satisfies S2SRIP(r, vkrō1).
Proof. Suppose Z e 5axnxk has tubal-rank r. Since (I A AZ) is symmetric, its t-SVD is of the form
A)
((I-A-A) ((I-ArA)(Z))
Now, define (1 1,:) guxixk and let 1xxi be defined by s(1,
Vk ev 12mjt where
j arg maxy. y (1,)) With this definition, one can check that (I - At V***>>++> V
|[I (2))
Then, since satisfies R + 1, 11) and rank (3) S r and rank ( **** =1 by Lemma G.1
we have
[(I A A3))1
( A² V***VV* DTT
5 611 V * 8 V |
= 6 1|
< 61 kr 3||-
Since the bound II(Z - ()))I < ki S2SRIP Vkrō1).
E holds for any Z E Saxnxk with tubal rank < r, we have that A satisfies
Lemma G.3. Suppose that A : 5nxnxk Rm satisfies RIP(2, 52) where < 82 < 1. Then, A also satisfies S2NRIP(V (v.6.).
Proof. Since A satisfies RIP(2, by Lemma G.2 for r = 1, A satisfies S2SRIP(1, Vkōz). Now, suppose that E Suxnxk Since Z is symmetric, it has t-SVD in the form
Z - Σ V. 8 V.T.
iml
51

---

Implicit Regularization for Tubal Tensors via GD
Then, since each term Vj * 8, D is symmetric with tubal rank have
n
(I=)a))\3)| (I A)
Σ
V; 83 V.
R
(I-- A) (V: 8,
(I AAA (V: 8: *
Vioa | + 11
Σ Vida ||
S vko21 211.
Since the bound [I-- A) - vkō21
31. holds for any Z E Smxnxk, we have that A satisfies S2NRIP (ANRIP(Vko.)) Vk62).
Lemma G.4. Suppose : Smxaxk + Rm satisfies (2P 63), where O < < 1, and V E Rxxx satisfies V *V I. Then, for any Z E Snxnnk with rank 3) S r, we have
| * (I - ArA) 6a11
Proof. Let Z 5nxnxk and let y V.. V=(((-A'A\())
xxxxx Trivially, |>]]e 1, and so, IIV 211
VV )) (v. VT * V vV*y) y) (V.V) 1 = 1. Then, by using Lemma G.1 we have that
|TT I[I - (()))=)))) -(VT * *[II - (2A)) .1) )))
(I(I A2)) V 3)
S 3 | IV y
63 1 F
H. Properties of Aligned Matrix Subspaces
In this section, we collect some properties of matrices and their subspaces, useful for the proof of the results in the tensor Fourier domain.
Lemma H.1. (tööer & Soltanolkotabi 2021)) For some orthogonal matrix X Cuxr and some full-rank matrix Y E x R consider x VEW" and the following decomposition of Y
Y= Y=YWW"> +YWLWH
(H.I)
with its SVD decomposition Y = DR Runnh and the best rank-r approximation Y, E o.ue Then if the distance between the column subspace of Y, and the subspace spanned by the columns of X is small enough, that is X ll $ 8* then the decomposition (H.T) follows some low-rank approximation properties, namely
VyHv || S 7l.xHvy.ll
(H.2)
| < (Y).
(H.3)
52

---

Implicit Regularization for Tubal Tensors via GD
Lemma H.2. For matrix X Caxr, r S n, with its SVD-decomposition X Vx W and some a full-rank matrix Y E Cnx,, consider V VEWH, and the following decomposition Y
Y = V=WW + YWIWI.
(H.4)
Let matrix H E C be defined as
H = x (Id + PZ)YW
with some Z Cax", parameter 1s S /3 | and |VFVrwll C2 with sufficiently small constants cı C2 0.
Then H can be represented as follows
H (Id n uPI #B
with matrices P2, P3 E Cr such that
Pi =
P2 V Xxx# + VW (VIVyw)- htwp://wwwlaaawww:hthhu. #//YWW*y*
P3 < -
with
||ll S /||/W// Vrwl?
|| S 41|2 -xx= + +r
||l|| & 2/]x1/
Moreover, it holds that
Omin (H)= 2 (1
po man (X)
P P2| p²((Psll) min (V (1-oo (VHY)).
Proof. The proof of this Lemma follows from Lemma 9.1 in (Stöger & Soltanolkotabi 2021 by using independent matrix Z E Cu instead of the matrix A' A"X(XX" - YY omitting the assumption S 3 X|| and updating respectively the transformation steps.
Lemma H.3. For matrix X E CaxT, S with its SVD-decomppsitiion X = Ex and some full-rank matrix Y E x and Y1 = (Id + μZ)Y consider V VEW", V ViΣ, WH and the following decomposition of Y and Y1
Y YWW" YWIWH WH.
Y1 = WWWW WT + Y, W 1.1.
Assume that VRY.W W is invertible, which also implies that Y.W is has full-rank, and that IIV Vy S 50 and μ S min& W 1 and moreover, μ is small enough that 0 = Id p YWW"H"VVy = ld. Consider two matrices
G - WWW.-I/VVWw WFW.,
G2 V Y. WWW_WWW...
Then these matrices can be represented as
G uV Vn (V VH YW, wW..FWi.
with M, = V XXHVX and
G2 = (id- [122 + HM YW, (Id (Id- - Ma) YW, WFY"rw.).
WWFW
53

---

Implicit Regularization for Tubal Tensors via GD
with M₂ vi WWWHYHV, X1 and M3 V (Z (Xx= -X Moreover, the norm of 11 and G2 can be bounded respectively as Proof. The proof of this Lemma follows from Lemma 9.2 in Stöger & Soltamolkotabi 2021) by changing the matrix A" A(X XH УУ to the independent matrix C and taking into account the respective changes without having the condition || S X|I
|Gi|l & 2n( www.w/lwwww///.. ||z (XX# ,I ww / 1| + - - -Xxx -
|G22| - || 11 (
+ + 12+ 1Z - (xx* xX |IXWa11.
Lemma H.4. For a matrix E C r S. n with its SVD-decomposition = Vx W X and some full-rank matrix Y E C and Y1 == (Id + μZ)Y consider V = VEW" v = E, WT, and the following decomposition of Y and
Y YWWH + +YW_W1 W..
Y = W.WW W.
Then it holds that
[| 11 S 1+ (2
|XWIJIYW V Vyw |I + 1z- -XXX" [I-(XX=-XXX)) YY
min (VRY))
||WW||
(H.5)
minn (V
Moreover, if P YW ww..HWw W, -V - the following applies
11 + + P 1
then it holds that
H X1
Vriwi || $ || Vywll (1- 4
2 omin min + MIllW + +1IZ - (Xx yy
2 //
+ (1 n1| 21)
(H.6)
Jmin (W"W,, J (YW)
WWW II (WHW, miin (YW)
+ 57 ||| + (1 + z||
mmin
Proof. The proof of inequality (H.5) follows from the first part of the proof of Lemma B.3 in (Stöger & Soltanolkotabi
2021). For this one needs to change the matrix A" A(XX" - Hy in (Stöger & Soltanolkotabi 2021 to an independent matrix Z E Cn and take into account the above-given decomposition of matrices and Yı and lack of assumptions on and the norm of matrix Z. Incquality (H.6) follows from the proof of Lemma 9.3 in (Stöger Soltanolkotabij 202I).
Random Tubal Tensors
In this section, derive bounds the minimum and maximum singular values well the Frobenius norm of random tubal tensor with i...d Gaussian random entries. In our analysis of the spectral stage, we applied these lemmas to the small random initialization..
We start with the following proposition from Rudelson and Vershynin (2009), which bounds the smallest singular value of an r x R random real Gaussian matrix.
Proposition I.1 (Ruddelsn & Vershynin, 2009)). Let G E g with r - R have iid N(0, 1) entries. Then, for every e > 0, we have
m ( G) 2 e(VR Vr 1I)
with probability at least (CC))B-ri 6 cR The constants C, c > 0 are universal.
54

---

Implicit Regularization for Tubal Tensors via GD
Also, the following proposition from Tao and Vu (2010) bounds the smallest singular value of random complex Gaussian matrix.
Proposition 1.2 (Tao & Vu 20100). Lei G E Rext have ii.d. CN( entries. Then, for every 0, we have
min (G) 2 Vr
with probability at least e².
Using these propositions, we can obtain a bound on the smallest singular value of an r x random complex Gaussian matrix, provided that r S R. Lemma I.1. Let G C with S R have i.i. CN(O0, 1) entries. Then, for every 0, have
R 2r c(VR- - -2
minn G)
i 2
with probability al least
1 c-
if > 2r
2
ifr R < 2r
The constants C, O are universal.
Proof. First, suppose R > 2r. Let G = UEVH be the SVD of G where U E Crxr and V E CR are unitary and Σ E RrxR, Then, the following real 2r x 2R matrix has a real SVD of
Re (G} Im (G}
Im [G} Re (G}
Re (U) Im (U)
Im {U) Σ Re {U}
Re [V}
Im (V}
=
Σ
Im [V}
Re [e{V}
By using the fact that for any A 1284 with p S q, min (A)²
min #ER"
|AA x we have
||
Re (G)
Im [m]
mmin (G)² O'nin
Im (G}
(C
Re (G) T
Im G
min a =ER*
Im (
Re (G) T
x
min mER2- mi] 2=
||| [[[] Im [G)
+ ||[ ||| Im (G)
Re
2
min mER
Re [G]" Im [
x
min mCR |=||==
Im
Re (G)
x
Re [G] [m] [G)
+ Jmin ([Te) (G)
Im {G}
Jmin
Im
[[e (G)
[[ [[m [G)
20
where the last line follows since reordering the rows of matrix flipping the sign of some doesn't 't change the singular values.
Re [G)
Since G E C has i..dd CN'(O,) 1) entries, v2
2rxx has i.i.d. A/ entries. Therefore, by Proposi-
Im {G}
tion
I.
we have that
Re (G) (G)]
amin (G) 2 Omin
V2
Im (G) 2 c(VR - /2r 1)
55

---

Implicit Regularization for Tubal Tensors via GD
with probability at least (Ce) R--2)-222111 2r-1 e-R as desired.
Next, suppose I R S 2r. Let Grxr be an submatrix of G. Then,
min (G)²
min |=
| 2 > min
| (x = min minn (Grxr)?
||
Hence, by Proposition 1.2
we have
Omin G)) 2 Mmin (Grx)) 2 VT
with probability at least 62.
Using the above lemma, we can bound the smallest singular value of an r x R k tubal tensor.
Lemma 1.2. Let g E Rrxxxx Rxc with r S R have i..dd NN, 12) entries. Then, for every 6 > O, we have
cvk(VR- 22r
if 2r
VR
min 2
CVT
ifr S R s 2r
VrR
with probability at least
(CEe)
ke-cR
if 2r
kc²
ifr < R < 2r
Proof. Since the entries of g are i.idd. NoO,, ) the entries of g are i.i.d. CN(O0, 4). Hence, each scaled slice CrxB for j I...., & has i..d. CN 1) entries. By Lemma L.1 each scaled slice satisfies
R ()) 1
if 2r E( c(VR R 1
(
i R 2r
with probability at least
1 - c if > 2r
2
ifr R < 2r
Then, by taking a union bound, we have that
eVE(VR 22
RR> 2r
VR
min (g) min Miin
1 1555k
cVh
ifr < R 2r
VrR
with probability at least
1 ((Cc)) - ke-eR
if R 2r
kE
if S R < 2r
The following proposition bounds the operator norm of an r x R random Gaussian matrix.
Proposition I.3 ( (Vershynin 2018)). Let U E x have i.i.d. CA((O,)) 1) entries. Then, with probability at least
( -e) we have
| $ / (n, RJ.
Using the above proposition, we can bound the norm of an n R x & random Gaussian tubal tensor.
56

---

Implicit Regularization for Tubal Tensors via GD
Lemma 1.3. Let U E |Rxxxxx have iid. NO0, tO) entries. Then, with probability least 1 O ( -mmxx(n.))) we have
k mmax (n, R}
[24|| -
R
Proof. Since the entries u4 are i.idd NN,,, h.), the entries u are ii.d. CN 2). Hence, each scaled slice u CrxR for j ....., k has i.d CO, 1) entries. By Proposition I.3 each scaled slice satisfies
| Ru
/max(n, R}
with probability at least O ft). Then, by taking a union bound, we have that
1: max n, R}
4 = max
S
ISiSk
R
with probability at least O mmxx(n
Lemma L44 Letll Rex have i.i.d. (o0, } entries. Then, for any fixed V1 E Rexixk with |Vill 1, have
l * VillaxvE
with probability at least 1 O(ke (R).
Proof. Since the entries of 4 i.i.d. ((0, H)), the entries of u i.i.d CN((O, $). and thus, the entries of ú
also i.i.d. CN(O0, h) Then, for each slice j = 1...., k, each entry of the matrix-vector product ' - (1)
1 E C isd.
(1) [12). Hence, the quantity
CN((0, $ 1
(i)
U
2R
13(13
2
has a x2(2R) distribution. It follows that
(1)
4
D
1
holds with probability at least
Ole e.. By taking a union bound over all I.... ki we get that
k
lu * V1
4
4
(3)
j5 1 = 1
k
j=l
P
F
i.e. 1 * &VIlFF x V with probability at least 1 - O(ke
57


Reviews:
[{"review_id": "84eh7EMmrG", "reviewer": "Reviewer_phi4", "summary": "To gain insight on initialization methods, the authors consider its effect on a gradient descent method for calculating a low rank tubal tensor tensor factorization, given linear measurements of the tensor. Tensor tubal rank of a $m\\times n\\times k$ tensor is the the rank of the SVD of the front $m\\times n$ slices of a tensor, after applying the discrete Fourier Transform in the last dimension.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive evaluation of our paper and for recognizing our work as one of the few papers that fully analyzes gradient descent. \n\n**Motivation for our work and the use of tubal rank:** \n\nThe study of implicit regularization was originally motivated by trying to understand how using gradient descent to train neural networks results in good generalization. However, implicit regularization has become its own field of study. Specifically, it has been proposed to design linear network architectures in such a way that an implicit bias towards a desired structure arises - as an alternative to explicit regularization. This viewpoint has been taken for the sparse recovery problem [Vaskevicius et. al. 2019] and the low-rank matrix completion problem [Li. et. al. 2018], but to the best of our knowledge, all previous works generalizing this approach to tensors either provide only a partial analysis or only analyze the gradient flow problem, not gradient descent, so we see our work as the first to establish this kind of approach for a tensor recovery problem. (In particular, we are not sure, which work about implicit bias of gradient descent for near-orthogonal tensor factorization you are referring to, so it would be great if you could provide a reference so that we can specifically comment.) In this context, we find the study of low tubal rank recovery interesting as this model has been shown to be useful in video representation. \n\nWe believe that it is an important line of research to answer questions like:\n- What types of structured tensor recovery problems can be solved with implicit regularization? \n- How to design the learner architecture to bias gradient descent towards solutions with the appropriate structure? \n- Under what conditions and how quickly does convergence occur?\n- Can one characterize the trajectory of the algorithm?  \n\nWe do agree that other types of low rank tensor structures are also important, and we also agree that the corresponding analysis can be more challenging, but we feel that our work is an important starting point for further analysis. This paper is not the end of the story, but rather one part of a larger line of research into implicit regularization for tensor recovery problems. \n\nWe agree that the additional motivational thread of using implicit regularization as an algorithm for structured recovery is currently not stressed enough in the paper. We will be sure to emphasize it in our revision.\n\n**RIP Condition:**\n\nWe would like to note that the RIP condition is a standard condition in the literature, and is used in similar works [Li et. al. 2018] and [Stöger and Soltanolkotabi 2021]. Essentially, this is necessary to ensure that there is one low tubal rank tensor for which the loss function is zero (although there are still infinitely many high tubal rank tensors for which the loss is also zero). Furthermore, [Zhang et. al. 2019] shows that a random sub-Gaussian measurement operator $\\mathcal{A} : \\mathbb{R}^{n \\times n \\times k} \\to \\mathbb{R}^m$ will satisfy the RIP for tubal-rank $r$ tensors with restricted isometry constant $\\delta$ with high probability if $m \\ge O(\\delta^{-2}rnk)$. Since we desire $\\delta = O(\\kappa^{-4}r^{-1/2})$, we need $m \\ge O(\\kappa^{-8}r^2nk)$ measurements. Hence, many random measurement operators (with far fewer measurements than the number of entries in the tensor) will satisfy the RIP.\n\n**Other:**\n\nThank you for bringing the papers [Ge and Ma 2017] and [Wang et. al. 2020] to our attention. We agree that they are related to our paper, and we will be happy to cite and include them in our paper's discussion.\n\nAttempting to generalize our results to the M-rank setting (instead of tubal-rank) is an interesting idea for future work. In the case where the matrix $M$ is a scalar multiple of a unitary matrix, we believe that our results will generalize in a straightforward manner, although we have not checked all the details carefully. However, in the case where $M$ is not a scalar multiple of a unitary matrix, generalizing these results will be more difficult as our proof makes use of the fact that transforming a tensor into the Fourier domain (equivalently the $M$ domain) scales the Frobenius norm by a constant factor. \n\nThank you for pointing out the issue with lowercase/uppercase in our bibliography. We will be sure to fix this in our revision.\n\nT. Vaskevicius, V. Kanade, and P. Rebeschini. \"Implicit regularization for optimal sparse recovery.\" Advances in Neural Information Processing Systems. 2019.\n\nF. Zhang, et al. \"Tensor restricted isometry property analysis for a large class of random measurement ensembles.\" Science China. Information Sciences 64.1 (2021): 119101. https://arxiv.org/pdf/1906.01198", "claims_and_evidence": "The theoretical claims are correctly proved and well supported by numerical evidence.", "methods_and_evaluation_criteria": "Does not apply", "theoretical_claims": "The theoretical claims sound correct, but I was not able to check all details of the proof.", "experimental_designs_or_analyses": "Does not apply.", "relation_to_broader_scientific_literature": "The paper analyses a gradient descent method, and in that sense it fits within other works in the literature that have considered this. In the topic of tensor decomposition and most relevant to this paper, some works include [Ge and Ma, *On the Optimization Landscape of Tensor Decompositions*], and [Wang et al, *Beyond lazy training for over-parameterized tensor decomposition*].\n\nOn the other hand, the authors focus on methods for tubal rank decompositions. Although this decomposition can be calculated efficiently through matrix SVD, some recent works have studied gradient descent type methods in this context [Liu et al, 2019, Liu et al, 2020, Liu et al, 2024].", "essential_references_not_discussed": "I believe the authors should cite [Ge and Ma, *On the Optimization Landscape of Tensor Decompositions*]. Although it is not very related, and the results and proof techniques are quite different, I think the authors should acknowledge one of the first works on trying to obtain guarantees regarding tensor decomposition.", "other_strengths_and_weaknesses": "- The paper is well-written, easy to follow, and the mathematical notation is consistent with what is used in the literature.\n- I find that the numerical experiments are very elucidating, and help understand better the theoretical results that the authors show.\n- The theoretical results are very interesting! This is one of the few papers I have seen that provides a full analysis of the gradient descent method, from initialization to (linear) convergence to the optima. The authors are also able to characterize an interesting transition from power-method behavior to near-the-maxima behavior, and observe that transition in numerical experiments. Finally, they relate their results to parameters of initialization. In that regard, this is a novel paper that deserves acceptance.\n- Nevertheless, the analysis has some weaknesses. First, the authors consider tubal tensor rank factorization. This is factorization to can be calculated efficiently using matrix SVD, and in that regard it differs from other tensor decompositions that are NP-Hard to calculate. Therefore, even though the function that is minimized is not convex, its analysis is surely easier than other tensor decompositions. Furthermore, the condition of RIP on $\\mathcal{A}$ seems to be too stringent: Since this is an RIP condition over low rank decomposition, and not over sparsity conditions, I wonder if this only includes maps that are very close to being orthogonal.", "other_comments_or_suggestions": "- The bibliography has several words written in wrong case (some words that are lowercase should be or start with an uppercase letter).", "questions_for_authors": "- There is a generalization of tubal rank (also by Kilmer) called the M-rank, where M is the DFT matrix for tubal rank (but it can be any invertible matrix in general for M-rank). Do your results generalize well to that setting?", "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": "YQ10kaC2ie", "reviewer": "Reviewer_THrp", "summary": "This paper studies the factorization of third-order tubal tensors using gradient descent (GD) with small initialization in the overparameterized setting. Under the standard restricted isometry property (RIP) condition, the authors show that GD recovers the ground truth tensor in a finite number of steps, provided the initialization is sufficiently small. The analysis builds on the insight that, with small initialization, GD initially behaves like a spectral method, effectively providing a good spectral \"initialization\" for the second phase, during which GD converges linearly. The results extend prior analyses of GD with small initialization from matrix factorization to tubal tensor factorization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive evaluation of our paper. We are glad you found it to be interesting and well-written. \n\n**Clarifying the Connection to Matrix Factorization:**\n\nThank you for bringing the connection to matrix factorization to the discussion.  Yes, while aiming to leverage matrix techniques as much as possible (no need to reinvent the wheel!), we encountered at lot of the technical complexities of these adaptations, which are briefly mentioned in Section 4. \n\nTo describe these technicalities in more details, we will extend Section 4. For example, the tubal-tensor iterates $\\mathcal{U}\\_t \\in \\mathbb{R}^{n \\times R \\times k}$ produced by gradient descent exhibit significant interactions between their slices when transitioning from step $t$ to $t+1$. This necessitated nontrivial estimations, such as those presented in Lemmas E.4 and E.5, to control these interactions and provide the respective bounds. Another intriguing point is that, one need to choose the learning rate $\\mu$ and the initialization scale $\\alpha$ very carefully for the noise term $\\mathcal{U}\\_{t} * \\mathcal{W}\\_{\\perp, t}$ to grow slowly enough in each of the tensor slices in order to not allow overtaking the signal term $\\mathcal{U}\\_{t} * \\mathcal{W}\\_{t}$ in the norm. \n\n**Parameter Dependence in Theorem 3.1:**\n\nWe agree that the parameter dependence in Theorem 3.1 looks unfamiliar at first sight. However,  we find it not surprising that if the tensor is ill-conditioned, i.e., has a very small tubal singular value, gradient descent without regularization will have a hard time discovering that rank-one component unless the initialization is very small (in fact, our bound on the required number of iterations could also be expressed as a polynomial in the initialization parameter, making the exponential dependence implicit).\n\nThis is in line with prior results in the matrix sensing case, which also require an initialization of size depending exponentially on the condition number, see [Stöger and Soltanolkotabi 2021]. In the matrix case, however, this dependence is not as apparent, as the term with the exponential dependence is absorbed in one of the absolute constants, see the range for parameter $\\beta$ in Lemma 8.6. of [Stöger and Soltanolkotabi 2021] with its proof and the corresponding results for tensors in our case. It is worth to mention that of course it is not clear in either case if the dependence needs to be exponential. We consider it an interesting question for follow-up work to investigate the precise dependence on the condition number.\n\nYes, some of the parameters appear polynomially in the bound, and as our numerical experiments, see Figure 4, show, indeed, the test error depends polynomially on the initialization parameter $\\alpha$. It might be that the degree of the true polynomial dependence slightly differs from the one obtained theoretically; however, we strongly believe that the power $\\frac{21}{16}$ approximates this dependence well. \n\n**Other:**\n\nThank you for catching those typos. We will be sure to fix those in our revision.", "claims_and_evidence": "See below.", "methods_and_evaluation_criteria": "See below.", "theoretical_claims": "See below.", "experimental_designs_or_analyses": "See below.", "relation_to_broader_scientific_literature": "See below.", "essential_references_not_discussed": "See below.", "other_strengths_and_weaknesses": "See below.", "other_comments_or_suggestions": "Overall, I find the paper interesting and well-written. Below are my suggestions for improvement.\n\n**Clarifying the Connection to Matrix Factorization:**\nThe proof outline in Section 4 resembles that of matrix factorization—GD first finds a spectral initialization and then converges linearly. Of course extending these results to tensor factorization is nontrivial. Some of the differences are briefly discussed at the end of Section 4. It would strengthen the paper if the authors could further elaborate on the technical innovations (for example, compared to Stoger & Soltanolkotabi 2021) for addressing these challenges mentioned at the end of Section 4.\n\n**Parameter Dependence in Theorem 3.1:**\nThe parameter dependence in Theorem 3.1 feels suboptimal. Notably, there is an exponential dependence on the condition number $\\kappa$. Is this dependence unavoidable, or could it be improved? Additionally, while the other parameters appear polynomially in the bound, the degree of these polynomials seems artificial. It would be helpful if the authors could clarify whether these dependencies are inherent to the problem or merely technical artifacts, and if the latter, provide an explanation for their origin.\n\nMinor Typos:\n\nLine 192: An extraneous “`” character.\n\nLine 205 (right column): A repeated sentence.\n\n\nLastly, I did not verify the proofs in detail.", "questions_for_authors": "See above.", "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": "0gecWAnB0B", "reviewer": "Reviewer_m6Sc", "summary": "In this paper, the authors study tubal tensor factorization via gradient descent. Assuming the ground truth tensor is \nof low tubal rank, they show that gradient descent from a small initialization will converge to the ground truth tensor,\nand the error can be made arbitrarily small by scaling down the initialization scale. \n\nMore specifically, they show that when the learner tensor is still small, the dynamics can be approximated by the tensor\npower method, whence the learner tensor will have a structure similar to the spectral initialization at the end of this \nstage. Then, they show that GD will converge to the ground truth from this warm start.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to evaluate our paper and provide valuable feedback. \n\n**RIP Condition:** \n\n[Zhang et. al. 2021] shows that sub-Gaussian measurements $\\mathcal{A}:\\mathbb{R}^{n\\times n\\times k}\\to\\mathbb{R}^m$ have the RIP for tubal-rank $r$ tensors w.h.p. if $m\\ge O(\\delta^{-2}rnk)$. Since we desire $\\delta=O(\\kappa^{-4}r^{-1/2})$, we need $m\\ge O(\\kappa^{-8}r^2nk)$ measurements. For $k=1$, the matrix case, this is very much comparable to the results in [Li et al. 2018]. In our revision, we will add a discussion on the number of measurements necessary for the RIP to hold.\n\n**Role of Low Tubal Rank Condition in Implicit Regularization:** \n\nWhile Thm 3.1 holds for $R$ as small as $3r$, it is more interesting for $R\\ge n$ so that our learner model, like [Li et. al. 2018], also does not explicitly encode low tubal rank structure, and no bound on the ground truth tubal rank is needed. In this case, we can substitute $\\min\\\\{n,R\\\\}=n$ so there is no dependence on $R$.\n\nWhen $R\\ge n$ and the number of measurements satisfies $m<k(n^2+n)/2$ (but is still large enough for $\\mathcal{A}$ to satisfy the RIP), there are infinitely many $\\mathcal{U}\\in\\mathbb{R}^{n\\times R\\times k}$ with $\\mathcal{A}(\\mathcal{U}*\\mathcal{U}^T) = \\mathcal{A}(\\mathcal{X} * \\mathcal{X}^T)$, and thus, $\\ell(\\mathcal{U})=0$. However, the gradient descent iterates converge to a tensor of low tubal rank instead of one of the many high tubal rank tensors with zero loss. This suggests gradient descent is implicitly biased towards \"simpler\" tensors with low tubal rank. \n\nWe hope this clarifies the implicit bias phenomena, as well as the role of the low tubal rank condition. Also, we will add a remark after the main theorem discussing how for $R\\ge n$ the theorem describes an implicit regularization phenomenon.\n\n**Motivation for our work and the use of tubal rank:** \n\nThe study of implicit regularization was originally motivated by trying to understand how using gradient descent to train neural networks results in good generalization. However, implicit regularization has become its own field of study. Specifically, it has been proposed to design linear network architectures in such a way that an implicit bias towards a desired structure arises - as an alternative to explicit regularization. This viewpoint has been taken for the sparse recovery problem [Vaskevicius et. al. 2019] and the low-rank matrix completion problem [Li. et. al. 2018], but to the best of our knowledge, all previous works generalizing this approach to tensors either provide only a partial analysis or only analyze the gradient flow problem, not gradient descent, so we see our work as the first to establish this kind of approach for a tensor recovery problem. (In particular, we are not sure, which work about implicit bias of gradient descent for near-orthogonal tensor factorization you are referring to, so it would be great if you could provide a reference so that we can specifically comment.) In this context, we find the study of low tubal rank recovery interesting as this model has been shown to be useful in video representation. \n\nWe believe that this is an important line of research with many open questions. See our response to Reviewer phi4 for more details. \n\nWe agree other tensor ranks are also important, but we feel that our work is an important starting point for further analysis. This paper is not the end of the story, but rather one part of a larger line of research into implicit regularization for tensor recovery problems. \n\nWe agree that the additional motivational thread of using implicit regularization as an algorithm for structured recovery is currently not stressed enough in the paper. We will be sure to emphasize it in our revision.\n\n**Other:** \n\nThank you for pointing out that tubal rank/t-SVD are not widely-used notions. We will expand the details we currently have in the Notations and Preliminaries section in the main body of our paper, as well as add a section on tubal rank/t-SVD in the Appendix. \n\nThank you for suggesting the question whether the tubal rank of the learner tensor gradually increases in the course of the gradient descent iterations. Indeed, during the spectral stage where the gradient descent iterates are small, gradient descent behaves approximately like a power method. As such, when the gradient descent iterates are expressed in the basis of the slices of the t-SVD of the tubal-symmetric tensor $\\mathcal{I}+\\mu(\\mathcal{A}^*\\mathcal{A})(\\mathcal{X}*\\mathcal{X}^T)$, the coefficients grow approximately exponentially at rates determined by the corresponding eigentubes. As such, it seems like one should be able to obtain similar results as in [2], however, we could not check the details carefully in the short revision period. We aim for a detailed investigation in future work.\n\nSee Response to Reviewer phi4 for the citations for [Vaskevicius et. al. 2019] and [Zhang et. al. 2019].", "claims_and_evidence": "This is a theory paper and the authors provide proofs (and numerical experiments) to support their claims.", "methods_and_evaluation_criteria": "NA.", "theoretical_claims": "Unfortunately, I am not familiar with tubal tensor factorization, so I couldn't check the correctness of the proof. \nHowever, based on my understanding of matrix factorization and orthogonal tensor decomposition, the results and proof\nstrategy look reasonable. \n\nI have one concern regarding the role of the low-tubal-rank condition. It is not clear to me where this low rank \ncondition is used and how it is related to the *implicit* regularization. \n\nIn [Li et al., 2018], the number of measurements needed is $\\tilde{O}(d r^2)$ (instead of $d^3$), as \nthis many measurements is enough to ensure the (matrix) RIP condition they need. In this paper, however, the authors \nassume the RIP condition for tubal-rank $r$ tensors. It is unclear whether this low tubal rank condition leads to \na better sample complexity. In addition, in [Li et al., 2018], the number of steps needed also depends on $r$ instead \nof $d$. It is not clear whether Theorem 3.1 of this paper implies a similar result. \n\nMeanwhile, in [Li et al., 2018], the shapes of the learner matrices are $d \\times d$ instead of $d \\times R$. In other \nword, they do not explicitly encode a low-rank structure in the learner model, but the sample/iteration complexity \nstill depends on $r$ instead of purely on $d$. In this paper, the shape of the learner tensor is $n \\times R \\times k$,\ninstead of, say, $n \\times d \\times k$, and many parts of the results depend on $R$ instead of $r$. I don't think we \ncan call it *implicit* regularization if we need to have a good estimation on the rank a priori and encode it in the \nlearner model.", "experimental_designs_or_analyses": "This is a theory paper and the simulations provided by the authors are serviceable.", "relation_to_broader_scientific_literature": "This paper seems to be a more technical challenging version of the corresponding results in matrix factorization \nand (near-)orthogonal tensor decomposition. It is not clear to me what new insights we can draw from this paper.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The usage of tubal rank is not well-motivated. Matrix factorization can be viewed as training linear networks, and \nthe usual CP-rank based tensor decomposition can be related to two-layer networks with Gaussian inputs via the Hermite \nanalysis [1], and the low-rank condition is equivalent to saying the teacher network has a small number of neurons. On\nthe other hand, I do not see the connection between tubal tensor factorization and other tasks. Moreover, it seems that \nthe notion of tubal rank is restricted to order $3$ tensors and cannot be easily generalized to tensors of higher orders.\n\n\n[1] R. Ge, J. D. Lee, and T. Ma, “Learning One-hidden-layer Neural Networks with Landscape Design,” in International Conference on Learning Representations, 2018. [Online]. Available: https://openreview.net/forum?id=BkwHObbRZ", "other_comments_or_suggestions": "I don't think tubal rank and tubal-SVD are widely-used notions/techniques in this area. It might be good to have a section in the \nappendix explaining them in more detail.", "questions_for_authors": "* Could you explain the role of the low tubal rank condition? See the \"Theoretical Claims\" section.\n* Could you justify the usage of tubal rank (cf. the \"Other Strengths And Weaknesses\" section)? \n* Could you obtain results similar to the one in [2]? Namely, is it true that GD will gradually increase the tubal rank \n  of the leaner tensor until it can fit the target. It seems that you have a fine characterization on the training \n  dynamics. It would be more interesting if you can obtain results like this based your analysis on the training dynamics.\n\nI'm willing to raise my score if you could answer the first two questions. \n\n[2] Z. Li, Y. Luo, and K. Lyu, “Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning,” arXiv:2012.09839 [cs, stat], Apr. 2021, Accessed: Jan. 30, 2022. [Online]. Available: http://arxiv.org/abs/2012.09839", "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:

Meta-review: Reviewers were unanimous in voting for acceptance of this submission, commending its theoretical contributions and supporting experiments.  Several (relatively minor) suggestions were given, some of which were already addressed by the authors during the discussion period.  I of course support the reviewers' recommendation.
Decision: Accept (oral)