Preconditioned Riemannian Gradient Descent Algorithm for Low-Multilinear-Rank Tensor Completion
Authors: Yuanwei Zhang
Fengmiao Bian
Xiaoqun Zhang
Jian-Feng Cai
Venue: ICML 2025 poster (2025)
Keywords: Tensor completion
Multilinear rank
Riemannian gradient descent
Preconditioning
Primary area: optimization->nonconvex

Abstract: Tensors play a crucial role in numerous scientific and engineering fields. This paper addresses the low-multilinear-rank tensor completion problem, a fundamental task in tensor-related applications. By exploiting the manifold structure inherent to the fixed-multilinear-rank tensor set, we introduce a simple yet highly effective preconditioned Riemannian metric and propose the Preconditioned Riemannian Gradient Descent (PRGD) algorithm. Compared to the standard Riemannian Gradient Descent (RGD), PRGD achieves faster convergence while maintaining the same order of per-iteration computational complexity. Theoretically, we provide the recovery guarantee for PRGD under near-optimal sampling complexity. Numerical results highlight the efficiency of PRGD, outperforming state-of-the-art methods on both synthetic data and real-world video inpainting tasks.

Preconditioned Riemannian Gradient Descent Algorithm for Low-Multilinear-Ral Tensor Completion
Yuanwei Zhang'
Fengmiao Bian
Xiaoqun Zhang'
13 Jian-Feng Cai
Abstract
the underlying three-order tensor X, E 18 Kna Kna from its partially observed entries:
Tensors play crucial role in numerous scien- tific and engineering fields. This paper addresses the low-mulilinear-raank tensor completion prob- lem, a fundamental task in tensor-related ap- plications. By exploiting the manifold struc- ture inherent fixed-multliinear-rnkk tensor set, we introduce a simple yet highly effective pre- conditioned Riemannian metric and propose the Preconditioned Riemannian Gradient Descent (PRGI) algorithm. Compared to the standard Riemannian Gradient Descent (RGD), PRGD achieves faster convergence while maintaining the same order of per-iteration computational complexity. Theoretically, we provide the re- covery guarantee for PRGD under near-optimal sampling complexity. Numerical results high- light the efficiency of PRGD, outperforming state-of-the-ar methods on both synthetic data and real-world video inpainting tasks. Code is available at https//giihbb.com/iuusaannii 0418/PRGD-Tuckee
X. (i,j,)) (1.j.h) E
where Ω is the index set of observed entries. However, with- out any assumptions, the problem ill-possed since the number observed entries [S2] is usually much smaller than the ambient dimension 723. One commonly adopted assumption is the low-rankness of X, Compared to matri- ces, tensors possess richer variety of rank notions, each associated with different tensor decomposition structures. Examples include the CP decomposition (Hitchcock, 1927), Tucker decomposition (Tucker, 1966), Tensor- Train decom- position (Oseledets, 2011) and several others (Kolda Bader, 2009). this work, we focus on the Tucker de- composition and its associated multilinear rank. The low- multilinear- rank tensor completion problem is formulated as follows:
min f(x) = 2 1)((x)) 1 - (I)
XER"1
s.t. rank(x)) =
where r (ri, r2, ra) is the multilinear rank satisfies
1. Introduction
ri S n, for all 1,2,3, Pg is projection operator for element- wiselt sampling and || denotes the Frobe- nius norm.
Tensors multidimensional arrays, which routinely arising in different fields, such community detection (Jing et al., 2021; Zhen & Wang, 2023), multi-dimensional recom- mendation system (Zhou et al., 2024), video and hyperspec- tral image processing (Zhang et al., 2021; Yang et al., 2023), signal processing (Chang Wu, 2022) and quantum state tomography (Qin et al., 2024). In this paper, we consider the tensor completion problem, where the goal is to reconstruct
1.1. Related Works
Compared with low-rank matrix completion, low-rank ten- sor completion presents unique challenges due to its more sophisticated algebraic structure. For instance, while nu- clear norm minimization achieves near-optimal sampling complexity for low-rank matrix completion (Candès Tao, 2010), computing the tensor nuclear norm is NP-hard (Fried- land & Lim, 2018) and applying nuclear norm minimization tensor's unfolding matrices results in suboptimal sam- pling complexity O (where
'School of Mathematical Sciences and Institute of Natu- ral Sciences, Shanghai Jiao Tong University, Shanghai, China. "Department of Mathematics. The Hong Kong University of Science and Technology, Hong Kong, China. 'Shanghai Ar- tificial Intelligence Laboratory. Shanghai, China. Correspon- dence Jian-Fen -eng Cai <jfcai ukk Xiaoqun Zhang @
max;=1,2,3 n2 and assume r; = O(1), 1,2,3) (Mu et al., 2014; Huang et al., 2015). The state-of-the
sampling complexity of polynomial-ting algorithms 3 (Cai et al., 2022b; Tong et al., 2022: Wang et al., 2023), which is considered near-optimal given the conjecture that no polynomial-
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Preconditioned RGD Low-Multilnnea--Ran Tensor Completion
algorithm can achieve sampling complexity lower than this threshold (Barak & Moitra, 2016). These algorithms can be broadly categorized into two main types.
rendering them computationally expensive for large-scale problems. In this work, we develop simple yet efficient preconditioner along with data-driven Riemannian metric on the tensor manifold, resulting in the PRGD algorithm for (1). Numerical experiments on synthetic data show that the proposed PRGD algorithm can be several times faster than state-of-the algorithms. Additionally, we provide a theoretical recovery guarantee, demonstrating that PRGD achieves near-optimal sampling complexity.
The first category consists of algorithms based on the factor- ization form of the Tucker format, where the optimization variables are factor matrices and the core tensor. Among them, (Xia & Yuan, 2019) assumed orthogonality of the fac- tor matrices and proposed a Grassmannian gradient descent algorithm. (Han et al., 2022) introduced regularization to enforce orthogonal constraints on factor matrices, resulting in a regularized gradient descent algorithm. (Tong et al., 2022) developed a scaled gradient descent algorithm and derived an iteration complexity that is independent of X, 's condition number.
1.2. Our Contributions
The main contributions of this work are summarized as follows:
Another category involves algorithms that optimize directly on the tensor variable and employ projection in each it- eration to exploit the low-rank structure. (Rauhut et al., 2017) developed an iterative hard thresholding algorithm and (Chen et al., 2019) proposed a projected gradient de- scent algorithm. Among those approaches, Riemannian optimization methods are particularly noteworthy due to their theoretical advantages and computational efficiency. For instance, (Wang et al., 2023) developed the Riemannian gradient descent algorithm and established the entrywise lin- ear convergence guarantee. (Luo & Zhang, 2023) proposed a Riemannian Gaussian-Newton algorithm that achieves a quadratic convergence rate. Notably, Riemannian optimiza- tion methods also exhibit an iteration complexity that is free of the condition number (Cai et al., 2022b; 2023).
Data-driven Riemannian metric and tangent space pa- rameterization. We design computationally efficient, data-driven metric from the gradient and equip the tan- gent space of the iterate on the manifold with this data- driven metric. To compute the induced Riemannian gradient, we introduce a novel tangent space parame- terization along with a detailed analytical framework, providing deeper insights into this method.
PRGD algorithm and empirical studies. Building on the data-driven metric and induced Riemannian gradi- ent, we proposed the PRGD algorithm and empirical studies on both synthetic and real datasets. The com- putational complexity of PRGD maintains the same order RGD's per iteration. The numerical results demonstrate that PRGD can be several times faster than state-of-the-an algorithms.
To the best of our knowledge, existing Riemannian opti- mization methods developed on the fixedmullilinear-rant manifold for (1) exclusively utilize the canonical metric induced by the ambient space TR x XRs_ However, the Riemannian metric can vary across points on the manifold, providing the potential for more tailored designs. Thus, natural question arises:
Recovery guarantee. We analyze the theoretical proper- ties of PRGD and establish that, with proper initializa- tion, such as using spectral methods, PRGD converges linearly to the global minimizer with contracting factor that is independent of the condition number. Fur- thermore, PRGD achieves a near-optimal sampling complexity of 0113/2)
Can we construct more suitable Riemannian metric that en- ables the resulting Riemannian gradient descent algorithm for (1) to achieve faster convergence while maintaining near-optimal sampling complexity?
Preconditioning techniques have long been recognized as powerful tools to accelerate convergence. Our work con- tributes to the recent strand of works preconditioned methods for tensor/matrix variable optimization problems (Kasai & Mishra, 2016; Gupta et al., 2018; Tong et al., 2022; Cai et al., 2022a; Gao et al., 2024; Bian et al., 2024; 2025). Notably. (Gupta et al., 2018) proposed a precondi- tioned method, called Shampoo, for unconstrained tensor optimization problems. This method constructs precondi- tioners by accumulating outer products of historical gradi- ents. However, Shampoo's 's preconditioners are fully dense,
Notations. In this paper, we use the calligraphic letters (x, X)) to denote tensors, bold-face capital letters (U, Ü) to denote matrices, lower case bold-face letters (x, y) to denote vectors, mathematical scripts (P, to denote operators, and blackboard bold-face letters (R, to de- note sets. Additionally, for matrix U E mm Xm22 we define ||U|||, == max; [U( [))l is the f2,00 norm of U. We define ń = n))))) 1/3 as the geometric mean, n = max,=1,2,3 n. and r = max T.. For constant a and b, a V b = max (a, b) and a A = min b).
2

---

Preconditioned RGD Low-Mullilinerr-RRa. Tensor Completion
2. Preliminaries
and
|| 1 1|
Spiki(X.)
2.1. Tensor Operations and Tucker Format
We give a brief introduction of tensor notations here for the paper to be self-contained, interested readers can refer to (Kolda& & Bader, 2009) for more details.
A low incoherence or spikiness parameter indicates that the entries of the tensor are evenly distributed, enabling small subset of entries to effectively capture and reveal the structure of the entire tensor. The relationship between these two parameters as follows.
Tensor matricization and multiplication. For tensor X E g2 the mode-1 matricization (X)) E I Xwana is given by [ for is E [mg]] The (2+e) and M2x(2) are defined sim- ilarly, We denote x; as the the mode-i tensor multiplica- tion, for matrix U Rmxx; the mode-1 multiplication X x U Imxxaa satisfies
(6,,(6 tin
Lemma 2.2 (Lemma 13.5. (Cai et al., 2023)). Let X. with multilinear rank (r1,72,73). Incoh(X.) and Spiki(X.) V, then
S VÑO.
where Ki is the condition number of X..
=
Multilinear rank and Tucker format. The multi- linear rank of X' is the collection rank(x)) == (2)))(
2.3. Fixed-Multillneer-Raall Manifold and RGD Algorithm
rank((M23({))) If X has multilinear rank r = (21, r3), then there exist D e grixraraa and U, E [ satisfying U. U.U Ir, for i i= 1,2,3 such that
rank(.((2(()) ran.
For tensors in I X the set of tensors with multilinear rank (11. (21./2,73) ra) forms a smooth embedded submani- fold, denoted as M,,, i.e.
MI, = (X' E R Xmaxna rank( = r].
x= U.
Given X' E Mr. X = D x U3 with U.U, U; = I Denote Tx the tangent space of X, given tensor Z, the projection has the form
This is called the Tucker format of X.
Tensor condition number. For X with multilinear rank r (r1, Fi..2,rrl rs). The condition number of X' defined as
P (2) -2 U Σ D W. X Un
= mmax (2))
max (x0)
mmi (X)
min;= r, (x)))
where and W , are parameters computed via explicit for- mulas by D, U, and 2. By equipping M,, with the canoni- cal metric, it becomes Riemannian manifold. Riemannian optimization method, recogmized for their computational efficiency and sampling optimality, have been extensively studied for solving (1) (Kressner et al., 2014; Wang et al., 2023; Luo & Zhang, 2023; Zhang et al., 2024). The Rieman- nian gradient descent (RGD) algorithm iteratively generates sequence as follows:
where (-) is the r-th largest singular value of input matrix. Tensor norm. For tensor X. E IR=1X"2xX; the inner product between two tensors is defined as
(x,3) = Σ x(i,j,k) ((,,i,A)
The Frobenius norm is defined as ||>||| V(X,
x Ri (X*- ar grad f(x*))
(2)
2.2. Incoherence Condition
where grad f(x²) is the Riemannian gradient at X Or is the stepsize, and 9, is the retraction operator. The iteration (2) contains the following two key components:
For the completion problem, it is crucial to assume the information of X carries fairly among all its entries to make the problem wols-possed. The following two concepts are widely studied to characterise such property (Yuan & Zhang, 2016; Cai et al., 2023).
Riemannian gradient and tangent space projection. The Riemannian gradient depends on the metric used in tangent space. Under the canonical metric, grad f(x*) PI, Vf(²"), where Vf is the Eu- clidean gradient of f in the space RD Xns, By pro- jecting the Euclidean gradient onto Tx,, the Rieman- nian gradient is at most rank 2r, rendering considerable computational efficiency in subsequent retraction step (Kressner et al., 2014; Cai et al., 2020).
Definition 2.1 (Incoherence and Spikiness). For X. with multilinear rank (r1, 72, and X, D. x x²_ U; The the incoherence and spikiness parameter of X. are defined as:
Incoh(X.. = max
Thi U
12,02,00
1=1.33
T
3

---

Preconditioned RGD Low-Muuttilnnrr--Ra Tensor Completion
Retraction by HOSVD. The retraction operator Be is map from tangent space xxx to manifold M,. A widely used choice for retraction is the high-order singular value decompasition (HOSVD) operator Hf, (De Lathauwer et al., 2000). For 2 E R X X
enhancing computational and memorial efficiency. Similar preconditioner has also been developed in (Bian et al., 2024; 2025).
Proposition 3.1. For X E My, denote PIx as the projec- tion operator onto Tx under (--)) w; and is the Euclidean gradient at X. Then the Riemannian gradient grad under our data-driven metric is:
H+ == 2 - Z where Z; TR is the re-principle left singular vector matrix of (Z).
gradf(X) = P..WW
The efficiency of RGD is significantly influenced by the choice of the Riemannian metric. This motivates the central aim of this work: designing more suitable Riemannian metric on M, to achieve faster convergence.
However, it is difficult directly obtain the explicit form of PTx since the components in standard tangent space parameterization are not orthogonal under our data-driven metric w. We need to reparameterize the tangent space Tx according to our data-driven metric.
3. Preconditioned RGD
3.1. Data-Driven Metric and Riemannian Gradient
3.2. Tangent Space Parameterization
Our preconditioners are derived from the gradient at each iteration, yielding data-driven metric tailored to the given observations and algorithmic data. Recognizing the impor- tance of incoherence and spikiness in tensor completion, our preconditioner rescales the gradient entry-wise to enhance these properties.
We first give the following lemma and the proof can be found in the Appendix A.
Lemma 3.2. Given a gauge sequence G₁ E R" i 1,2, (e.g. each G; is a symmetric positive definite matrix). For X E Mr with X'
x U; and U, G,Ü, Ir. i = 1,2,3. Then each element in the tangent space X' can be represented as:
Let G == -x(t.) RT X be the Eu- clidean gradient of the objective funetion f iterate X². We define the following diagonal matrices for i = 1,2,
3 D X W.
C 3
C
Σ 1=1
Ü,
(5)
G = (ce -n,, + P
(3)
where E, > 0 is a constant and diaa ()) sets the off- diagonal elements of input matrix to zeros, making G.,, positive definite diagonal matrices. The exponent is ap- plied entrywise to the diagonal vectors and the value 6 is set twice the tensor order for normalization. We then define new inner product in RT1 K Xn as follows:
G.W.W = O = 1,2,3 and with W; E Ruxn, R
Note that each G.,i E gm,x,, is positive definite. So we can use G., 's gauge sequence in Lemma 3.2 and obtain the following proposition.
2w, = (W()),, Z) = (D x2= Z).
(4)
Proposition 3.3. For X E Wl,, use G., 's as a gauge se- quence in Lemma 3.2, then the four components (5) are orthogonal to each other under (:'') we:
where V 3 E RRRixnxXn are two arbitrary tensors. It is straightforward to verify that ( wr is inner product. This weighted inner product is then endowed in the tangent space Tx,, and our preconditioned Riemannian gradient descent is derived under this metric.
(C x x Ü, X, W. X
= 0,
(D X We Xz4n Ú D X1 Wi x j4t -
Notice that Gr.; is a diagonal matrix whose diagonals are ap- proximately the norms of mode-i slices of G Therefore, in the preconditioned Riemannian gradient descent algorithm, each element of G is scaled by the inverse of the product of its slice norms, which unifies its entries and enhances the incoherence condition. We note that our preconditioner is also closely related to Shampoo's 's preconditioners (Gupta et al., 2018), but we discard historical gradients and retain only the diagonals of the preconditioner matrices, thereby
3.3. The Closed form of Prx
With the parameterization and orthogonality between com- ponents in Lemma 3.2, we can derive the closed form of denote
Prx (A) for arbitrary tensor A E 2 Xna,
3 Pr. (A) = CA x²_ U. Σ
D x1 A, X1+1 U,
4

---

Preconditioned RGD Low-Multllnnar--Ban Tensor Completion
0 with unknown C E R and U. A = i- 1, 1,2,3 3, then it is equivalent to solve the following problem
Algorithm I involves an additional procedure called trim- ming, which is used to guarantee the incoherence property of iterates in matrix or tensor completion task (Wei et al., 2020; Tong et al., 2022; Cai et al., 2022b). The trimming operator Trimç is defined as follows, for given tensor W,
CA CAXi=1 U.+ Σ Dx A X jzt U, A
min CA.(A.)
1=1
W
s.t. Ü, Gr,A; - Or i 1,2,3.
[Trime (W)))a, -
{ S Sign(Wa..k) if Waaa 2 S Wijak
otherwise.
Here || l1w, is the induced norm of inner product bw: Due to Proposition 3.3, CA and A; can be solved individu- ally:
This operation trims large entries of W, ensuring that its spikiness remains within an acceptable level. Consequently, it guarantees the incoherence property of the iterates by Lemma 2.2.
CA x x All
CA argmin Ca
U,
Wi D Ai Xzti Ü, - -A
Theorem 4.1 demonstrates that, under appropriate initial- ization conditions, Algorithm achieves linear conver- gence to the global minimizer. To satisfy these conditions, we propose an initialization algorithm presented in Algo- rithm Leveraging the subspace estimators introduced in (Cai al., 2021), Algorithm 2 first estimates the fac- tor matrices U; of W using the top-r eigenvectors of the diagonally-deleted Gram matrix of p MM (F..(()) (we use off-diag = & P diag and f is the identity operator). Subsequently, the algorithm constructs the initialization x by applying the trimming procedure on W to ensure the re- constructed tensor satisfies the required spikiness condition.
A:
argmin U. A;D,,
Thus, the explicit form of PI, can be derived, as summa- rized in the following lemma:
Lemma 3.4. For tensor X' E Mr and & =5,, X
X' _ G E My. denote Pr as projection operators onto tangent space TT of 2 under Euclidean metric, then:
W, Prx W.
Lemma 3.4 indicates that compared to RGD, computing the Riemannian gradient Ar "yy.W,-'' in PRGD requires two additional operations. The first operation, * costs O([S2) since G is sparse. For the second operation W, PT W. (") P.
Algorithm 2 Spectral Initialization with Trimming
Input: Pn(X')) E R" X X multilinear rank r, sam- pling ratio p and spikiness parameter v.
for 1, 2, do
3 lies in xe thus can be expressed as the sum of four multilinear-rank-r tensors. The computational cost is (nr). Consequently, our pro- posed preconditioned strategy is efficient, as the additional computational overhead is negligible compared to the com- putational cost of RGD, which scales as (n)r)) (Cai al., 2020).
T. = p p===-1.iil (0
U: + the top-r; eigenvectors of P off-diig (TTT.
end for
W
= pp- 1-1 x U,U.T Output: X = HHr(
HH,HHH,TTTnnn (Trim, (Wo) with c = 77
8|
Here we remark that the parameter v in Algorithm I and Algorithm 2 is not necessarily the true spikiness condition. Instead, it can be treated as tuning parameter set slightly larger than Spiki(X.). Furthermore, we numerically observe that the algorithm performs nearly the same with and with- out the trimming procedure. Therefore, from a practical perspective, the trimming step can be omitted.
3.4. PRGD Algorithm
The details of the proposed PRGD algorithm, based on the derivation of the Riemannian gradient under Wi above, are summarized in Algorithm 1.
Algorithm 1 Preconditioned RGD
Initialization: XO E M, and spikiness parameter v for i = 0,1,.... T Tmax do
4. Recovery Guarantee
The convergence analysis of PRGD is divided into two parts, local linear convergence and initialization estimation. We first present the local linear convergence of PRGD in Theorem 4.1.
g' Pa(x') Px()).. W = xxt a, Ar W. W
w' = Trime, (W') with &
&|IW' 7n9/20
x++11 = (W)).
Theorem 4.1. Suppose X. E M, with Spiki S v, Ω satisfies the Bernoulli model (i.e. each entry observed
end for
5

---

Preconditioned RGD Low-Multilnear--Ran Ran- Tensor Completion
independently with probability p) and the initialization sat- isfies
(10-3, 5 x 10-1, 10-4,005000 10-5). Since no step size strat- egy is proposed for the ScaledGI algorithm in (Tong et al., 2022), to make fair comparison, we tune the optimal con- stant step size for all tested algorithms and report the results. All simulations are performed in MATLAB r2023b with a 2.6GHZ Intel Xeon ICX Platinum 8358 CPU.
Amin Cr
1 - S
and Incoh(X²)) S 22/6
for a sufficiently large but absolute constant Č O. Then there exist an absolute constant C >> O such that if satisfies
We test those algorithms on both synthetic data and real data. For the synthetic data, we set n2 n2 ng = n and r1 = 12 T3 Following the same manner in (Kressner et al., 2014), we construct the ground truth tensor X. by first generating the entries of core tensor and factor matrices from a uniform distribution on [0, 1]. then use QR decomposition on the random factor matrices to obtain the orthonormal ones. For the real data, we consider the video inpainting problem, where the goal is to reconstruct the original video from its partially observed pixels. Throughout this section, we use the relative error frequently that is defined by
p (olo@(n)) 2 1og(n)r8v2n3) nn -3 Kgy
+ C
then with high probability (i.e. least cin ca for C1, 02 > and 0 sufficiently large), by choosing E, com- puted from the gradient and step size at = the sequence {2" generated by Algorithm 1 satisfy
| X.1IF S 0.351 ||x X.
for all t -0,1,2...
|| X. 1
relative error
Theorem 4.1 dictates that Algorithm 1 converges linearly to X' provided that the initialization 2² is sufficiently close to Xt and the incoherence condition is satisfied. By lever- aging the spectral initialization property from (Tong et al., 2022) and the trimming property from (Cai et al., 2023), we derive the following estimation for Algorithm 2, ensuring it meets the initialization error requirements specified in Theorem 4.1.
|X
where N is the output tensor of the algorithm.
5.1. Reocovery Ability
Phase Transition. We first explore the recovery abilities of PRGD in the framework of phase transition. test considered be successful if the recovered tensor has relative error smaller than 10-3 For each set of parameters, we run 100 random trails and count the success rate. The results in Figure/ 1 demonstrate the recovery is successful when the sampling size is moderately large. And when the rank increases, more sampling needed for a successful recovery. These are consistent with our theoretical findings.
Lemma 4.2. Assume the condition of X" and Ω from Theo- rem 4.1 holds. Then there exists an absolute constant C' > 0 such that if
Z C log (n)n (,) + C'loo' 1aann-3-'''' 3 mig
then with high probability, the initialization tensor X from Algorithm 2 satisfies
(uinn(X.) and Incoh(2*)) S 20/60
- -xalle
Crè
0.9
0.8
By directly combining Theorem 4.1 with Lemma 4.2, the re- covery guarantee of the PRGD algorithm can be established with nearly optimal sampling complexity (mz3/2). De- tailed proofs of Theorem 4.1 and Lemma 4.2 are provided in the Appendix B.
0.7
Success rate
0.6
0.5
0.4
5. Numerical Experiments
0.3
Tudaer Rank
0.2
Tudder Rank
In this section, we proposed several numerical compar- isons of our proposed PRGD algorithm with state-of-the art algorithms that include RGD (Cai et al., 2020; Wang et al., 2023), for demonstrating the effectiveness of precon- dition, and ScaledGD (Tong et al., 2022), for comparisons with factorization based algorithms. For our PRGD algo- rithm, we keep the hyperparamter & a constant chosen from
Tudeer (5.
0.1
Turker Rank (6, 6,
Teader Rank (7, 7,
01
10
15
20
25
30
35
40
45
50
55
60
9/2
Figure The success rate of PRGD with respect the sample
size 3/2 for tensor with size n = 100 and rank ranging from to 7.
6

---

Preconditioned RGD Low-Multilinea-RRuu Tensor Completion
5.2. Comparison with Other Algorithms
The results in Figure demonstrate that our PRGD algo- rithm significantly outperforms the other two algorithms in terms of speed under various parameter settings, achieving approximately 10x speedup compared to RGD and 3 to x speedup compared to ScaledGI.. Additionally, the results in Figure are consistent with those in Figure 2, further verifying that the additional computational cost per iteration of PRGD is negligible compared RGD.
Iteration Count and Runtime. We next investigate the iteration count and runtime of all tested algorithms under different oversampling ratios (OS), which is defined
pr
OS
(Ml,))
r + 3(nr r2)
Here we consider the tensors of size n 100, 150, 200 and rank 5. The OSs are set to 10, 15, 20 to represent different sampling levels. We count the iteration numbers and runtimes of the tested algorithm until the relative error is less than 10-4. For each parameter setting, we perform five random trials and report the average results in Figure 2 and Figure 3.
Increase the Sampling Level. To highlight the advantage of using preconditioning across different sampling levels. We fix the tensor size n = 100 and rank r = 5 while increasing the OS from 10 to 100, corresponding to sampling ratio from 1.6% to 16%. We perform five random trials for each OS and report the average results in Figure 4.
x 109 100
150 150 150
200 209 200
10
PRGD
PRGD
ScaledGD
10
ScaledGD
RGD
RGD
CPU time (second)
Iterations
10
10
10
20
40
60
80
100
10
05
05
Figure 4. The iteration counts of three algorithms at different sam- pling levels.
Figure The runtime results of tested algorithms in different set- tings.
Figure shows that when the sampling level is low, the benefits of precondition are substantial compared to RGD, As the sampling level increases, RGD gradually improves, outperforming ScaledGD and approaching the performance of PRGD.
PRGD
ScaledGD
RGD
10
Noisy Data Reconstruction. We then investigate the prop- erty of the PRGD algorithm in the presence of noise. For ground truth tensor X., the known entries of X, are per- turbed by rescaled Gaussian noise E, such that || 11 || for given noise level σ. We fix the size n 100, rank r 10, OS 10 and noise level a from 5 x 10 to 10-1, The stopping criteria is chosen when _ - / S 10-4, For each parameter set- ting, we repeat five random trails and we report the average relative error when the stopping criteria satisfied. The re- sults shown in Figure and Appendix indicate our PRGD is faster than others and robust to the additive noise.
Iterations
10
10
20
10
15
20
0S
Figure 3. The iteration numbers of tested algorithms in different settings.

---

Preconditioned RGD Low-Mulilinear- Tensor Completion
10 4
lems.
PRGD
ScaledGD
RGD
6. Conclusion
10
In this work, we propose a preconditioned Riemannian gra- dient descent algorithm for the Now-multilinear-ret tensor completion problem. The preconditioned metric is data- driven and computationally efficient. Numerical experi- ments demonstrate that the proposed PRGD achieves ap- proximately 10x acceleration compared the standard RGD. Furthermore, we establish the linear convergence of PRGD and provide a recovery guarantee with near-optimal sampling complexity. Lastly, we summarize several promis- ing directions for future research.
Relatvee Error
10
10
5e-4
1e-3
5e-3
1e-2
5e-2
1e-1
Figure 5. Noisy data reconstruction results different noise levels.
Other low-mulilinear-rrnk applications. Practical data often contain noise and outliers. In this work, we evaluate PRGD numerically on noisy data. However, a theoretical analysis of robust tensor completion and tensor regression remains for further investigation.
5.3. Real Data Reconstruction
Video Inpainting. We evaluate the performance of our proposed algorithm on the Tomato video from (Liu et al., 2012), as well as the Akiyo and Hall Monitor videos from the YUV video !ataset!. For the Akiyo and Hall Monitor videos, only the first 100 frames are used. Since these videos are in RGB format, concatenate their three colour channels along the third dimension and treat each video a three-order tensor.
Entrywise convergence analysis of PRGD. In this work, our convergence analysis focuses on estimating the & error of iterates. In contrast, (Wang et al., 2023) directly deals with & error, thus they can avoid the trimming operations and simultaneously maintain the incoherence condition of iterates below acceptable level. It would be interesting to investigate whether PRGD can exhibit similar properties.
Table 1. PSNR values of the outputs generated by different algo- rithms for three test vidcos with different multilinear ranks.
VIDEO(SIZE)
r
PRGD
RGD
SCALEDGD
50
27.34
27.15
27.09
TOMATO
60
27.79
27.44
27.15
Other preconditioned Riemannian optimization meth- ods. Building upon the preconditioned Riemannian metric proposed in this work, it is worthwhile to inves- tigate extensions such as the preconditioned Rieman- nian conjugate gradient descent and Gauss-Newton methods. Furthermore, exploring new preconditioned Riemannian metrics a promising direction for future research. By leveraging the tangent space parame- terization framework in this study, the corresponding Riemannian optimization methods can be readily de- rived.
(242, 320, 501)
70
28.25
27.50
27.15
50
27.61
27.43
26.68
HALL MONITOR
60
28.34
28.06
26,25
(288, 352, 300)
70
28.83
28.75
28.52
50
29.29
29.09
28.81
AKIYO
60
29.95
29.69
28.67
(288, 352, 300)
70
30.45
30.42
28.62
We assume that only 10% of the pixels are observed for each video and employ different algorithms reconstruct the original video. We vary the multilinear rank (r, r,r) and report the Peak -oonal-to-Noise Ratio (PSNR) of the recon- structed videos in Table 1. The image of certain frames of reconstructed vidcos and more detailed results are available in Appendix. C. It can be observed that our PRGD algo- rithm consistently achieves higher PSNR values compared to other algorithms across different settings and datasets, demonstrating its effectiveness for video inpainting prob-
A Acknowledgements
The authors would like to thank the four anonymous review- ers for their valuable comments. The work of Jian-Feng Cai was supported by the Hong Kong Research Grants Coun- cil GRF Grants 16307023 and 16306124. Xiaoqun Zhang was supported by the National Science Foundation of China (No. (N0.9009)))24 and Shanghai Municipal Science and Tech- nology Major Project (2021 SHZDZX0102).
8

---

Preconditioned RGD Low-Multllnear--ae Ran Tensor Completion
Impact Statement
De Lathauwer, L., De Moor, B., and Vandewalle, J. A multilinear singular value decomposition. SIAM journal Matrix Analysis and Applications, 2154):1253-12788
This paper presents work that aims to advance the field of tensor-related optimization without any known detrimental broader impacts. The insights and methods proposed in this study are intended to make positive contribution to tensor-related optimization and related areas.
2000.
Friedland, S. and Lim, L.-H. Nuclear norm of higher-order tensors. Mathematics of Computation, 87(311):1255- 1281. 2018.
References
Gao, B., Peng, R., and Yuan, Y.-x. Riemannian precondi- tioned algorithms for tensor completion via tensor ring decomposition. Computational Optimization and Appli- cations, 88(2):443 468, 2024.
Barak, B. and Moitra, A. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learming Theory, pp. 417-445. PMLR, 2016.
Bian, F., Cai, J.-F. and Zhang, A preconditioned rie- mannian gradient descent algorithm for low-rank matrix recovery. SIAM Journal on Matrix Analysis and Applica- tions, 45(4):2075-2103, 2024.
Gupta, V., Koren, T., and Singer, Y. Shampoo: Pre- conditioned stochastic tensor optimization. In Interna- tional Conference on Machine Learning, pp. 1842-1850. PMLR, 2018
Bian, F., Cai, J.-F., Zhang, X., and Zhang, Y. Fast and provable tensor-train format tensor completion via pre- condtioned riemannian gradient descent. arXiv preprint arXiv:2501. 13385, 2025.
Han, R., Willett, R., and Zhang, A. R. An optimal statisti- cal and computational framework for generalized tensor estimation. The Annals of Statistics, 50(1):1-22)) 2022.
Hitchcock, F. L. The expression of tensor or polyadic as a sum of products. Journal of Mathematics and Physics, 6(1 611-4):164-189 1927.
Cai, C., Li, G., Chi, Y., Poor, V., and Chen, Subspace estimation from unbalanced and incomplete data matrices: 12,00 statistical guarantees. Annals of Statistics, 49(2): 944-962 2021.
Huang, B., Mu, C., Goldfarb, D., and Wright, Provable models for robust low-rank tensor completion. Pacific Journal of Optimization, 11()):39-3644, 2015.
Cai, J.-F, Miao, L., Wang. Y., and Xian, Y. Provable near-optimal low-multilinear-ran tensor recovery. arXiv preprint Xivx22007.08904 2020.
Jing, B.-Y., Li, T., Lyu, Z., and Xia, D. Community de-
tection mixture multilayer networks via regularized tensor decomposition. The Annals of Statistics, 49(6): 3181-3205, 2021.
Cai, J.-F. Huang, W. Wang, H., and Wei, K. Tensor completion via tensor train based low-rank quotient ge- ometry under a preconditioned metrie. arXiv preprint (XXiv2209.047866 2022a.
Kasai, H. and Mishra, B. Low-rank tensor completion: a riemannian manifold preconditioning approach. Inter- national conference on machine learning, pp. 1012-1021. PMLR, 2016.
Cai, J.-F., Li, J., and Xia, D. Provable tensor-train format tensor completion by riemannian optimization. Journal of Machine Learning Research, 23(123):1-77, 2022b.
Kolda, T. G. and Bader, B. W. Tensor decompositions and applications. SIAM review, 51(3) 500, 2009.
Cai, J.-F., Li, J., and Xia, D. Generalized low-rank plus sparse tensor estimation by fast riemannian optimization. Journal of the American Statistical Association, 1 118(544); 2588-2604, 2023.
Kressner, D., Steinlechner, M., and Vandereycken, B. Low- rank tensor completion by riemamnian optimization. BIT Numerical Mathematics, 54:447-465 2014.
Candès, E. J. and Tao, The power of convex relaxation: Near-optimal matrix completion. IEEE transactions information theory, 56(5):2053-2008) 2010.
Liu, J., Musialski, P., Wonka, P., and Ye, J. Tensor comple- tion for estimating missing values in visual data. IEEE transactions on patter analysis and machine intelligence, 35(1):208-235 2012.
Chang, S. Y. and Wu, H.-C Tensor wiener filter. IEEE Transactions on Signal Processing, 70:410-422, 2022.
Chen, H., Raskutti, G., and Yuan, M. Non-convex projected gradient descent for generalized low-rank tensor regres- sion. Journal of Machine Learning Research, 20(5):1-37, 2019.
Luo, Y. and Zhang, A. R. Low-rank tensor estimation via rie- mannian gauss- newton: Statistical optimality and second- order convergence. The Journal of Machine Learning Research, 24(1):18274-11 18321, 2023.

---

Preconditioned RGD Low-Mulillneer-Rau Tensor Completion
Mu, C., Huang, B., Wright, J., and Goldfarb, D. Square deal: Lower bounds and improved relaxations for tensor recov- ery. In International conference machine learning, pp. 73 73-81. PMLR, 2014.
Zhen, Y. and Wang. J. Community detection in general hy- pergraph via graph embedding- Journal of the American Statistical Association, 118(543):1600-13) 2023.
Zhou, J., Hao, B., Wen, Z.., Zhang, J., and Sun, W. W. Stochastic low-rank tensor bandits for multi-dimensional online decision making. Journal of the American Statisti- cal Association, pp. 1-14, 2024.
Oseledets, I. V. Tensor-train decomposition. SIAM Journal on Scientific Computing, 3365):2255-2311 2011.
Qin, Z., Jameson, C., Gong, Z., Wakin, M. B., and Zhu, 7. Quantum state tomography for matrix product density operators. IEEE Transactions on Information Theory, 2024.
Rauhut, H., Schneider, R., and Stojanac, Z. Low rank tensor recovery via iterative hard thresholding. Linear Algebra and its Applications, 523:220 262, 2017.
Tong, T., Ma. C., Y. Scaling and scalability: Provable nonconvex low- rank tensor estimation from incomplete measurements. Journal of Machine Learning Reseurch, 23(16)):1-77, 2022.
A., Tripp, E., and Chi,
Tucker, L. R. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279-311 1966.
Wang, H., Chen, J., and Wei, K. Implicit regularization and entrywise convergence of riemannian optimization for low tucker-rank tensor completion. Journal of Machine Learning Research, 24(347):1-84) 2023.
Wei, K., Cai, J.-F., Chan, T. and Leung. S. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems and Imaging, 14(2):233-2653 2020.
Xia, D. and Yuan, M. On polynomial time methods for exact low-rank tensor completion. Foundations of Com- putational Mathematics,
2019.
Yang, J., Xiao, I.,, Zhao, Y.QQ., and Chan, J. C.-W. Unsuper- vised deep tensor network for hypeespectral-mutissetra image fusion. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Yuan, M. and Zhang, C.-H. On tensor completion via nu- clear norm minimization. Foundations of Computational Mathematics,
2016.
Zhang, S., Wang, L., Zhang, L.., and Huang, H. Learning ten- sor low-rank prior for hyperspectral image reconstruction. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 12005-12015, 2021.
Zhang, Y., Zhu, Y.NN., and Zhang, X. A single-mode quasi riemannian gradient descent algorithm for low-rank ten- sor recovery. arXiv preprint arXiv:2401. 15925, 2024.
10

---

Preconditioned RGD Low-Muulltinnar--Raa Rank Tensor Completion
A. Appendix
Proof of Proposition 3.1
Proof. For X' Mr, we derive the Riemannian gradient grad under the data-driven metric (:-)),- Let r(s) be smooth curve in M, with 7(0) X. Denote Arx be the orthogonal projection operator onto Tx under (r and is the gradient on X, then
Jo 16 = (5(0), = (f(0), W. 9) w..
therefore, the Riemannian gradient is
gradf(²)= F W Tx.
Proof of Lemma 3.2
Proof. For a symmetric positive definite matrix G E R St(n,r, G) = (U E R GU = I,} is the generized
Stiefel manifold. The tangent space at U E St(n, r, G) is
+U To Stn, r, G) == (Ú E R"xr, : GU + U GÚ = 0,} = (Ú e R"x,, UTGÜ GÜ E Sakew (r)}:
where SHow (r) denotes the space of skew-symmetric real r x r matrices. Consider the extended tangent map of
Uz) + + S S x U.
3
3
Rexexx x II
To St(n, r.),,,,.G))..... Gi) - TT x
II
Sakew (r),
1=1
3
(s.Ün.ú,.Us) + x U,+ Σ
s x U, xx U. U,,
1=1
where & prxxra and Ü, Tu, St(ni, G.). Moreover, for ý Ty, the & and U, are unique determined if impose
U,G.Ü,- O,,, 1=,1==12 1,2,3.
Then S and Ü, are given by the following formulas:
$ x
U. (In,- U.U.UU G.) Xayz Xazi (UT. Gi)) M(S)), ;= 1,2,3.
Thus the extended tangent map is an isomorphism and we complete the proof.
Proof of Proposition 3.3
Proof. Note that for 2 S x Ü, the matricization of 2 satisfies
Mi = ( MD Ü, 8 0₂
12 = U2 M, Ü, Ú,
Ma(2) = ( M; = Ú, U2800 Ū,
Denote Ü, G W.
G W i, = 1,2,3, then
(C x3 Ú, x, W. x Ú,)#, IC x U,D x W. X 0,) (..M.C W W.A((D)))
=0

---

Preconditioned RGD Low-Muulillnear--Ran Tensor Completion
where the third equality is due to Ü W. = =Ü Gr Wx & = O,, Similarly, when & + I
(D X WR jjtk ú D X1 Wt Xjxt új), = (D X W. Xjtk J D XI WT xjxt Ū,)
=( k. ( U (.
=0
here for simplicity, we denote (D X1 W X1 Ū,) = (D) for some matrix R.
Proof of Lemma 3.4
Proof. For X' E My, we denote := (2t then & E M, since the W operation doesn't 't changes the multilinear rank.
We denote X = D x =1 Ü. with 0,0, = I,, i = 1, as the standard Tucker decomposition. Let Ü. = G 0,,i=
3, then X' W. (2) = D x U, with U, U, I 1,
By Lemma 3.2, for arbitrary tensor A E RR xxxxxxxx,n the projection Prx = CA x E xt A. X Ü, where CA and A 's can be solved as follows:
CA x U: A 2 W
CA
argmin C2
argmin
C 1= Ü,
W. (A) 12
x3 Ú, (w: (W:)
where the third equality is due to 0. Ü, r, 1,2,3.
While for each A,, denote A, GA,(
Dx; A, x5 Ü, A 2
A = argmin
U. A.=.,
thus
| x; A, x1x U, - WW (A)1
A, = argmin 0. o
(D, M. (W/ xixs 0
argmin 0. A.
[nn 0.0.) M. (1/ (A) xzzz x)) ((:
where (D) is the Moore-Penrose pseudoinverse of (D). Thus the components in P (A) are equalivent to:
T CA Ú. x3 ú, x Ú. -, (w: x 0.0.) X U, Ü
+ (Dx: A X5 Ú,) , 1,=
D Dx, A X14i
To conclude
W. 3. PT. (A). (A). As A is an arbitrary tensor, we complete the proof.
12

---

Preconditioned RGD LoDooMMullilne Tensor Completion
B. Appendix
first refer to the following lemmas:
Lemma B.1 (Lemma (3. et al., 2023)), Ler X. E M, with spikiness parameter v. Assume W satisfies - -V-1x11>- =
Omin (..)
&|JWW|E Then, the tensor Hr He (Trim,(()) is incoherent with parameter 20Ko if we choose ( Tn3/2
Also, it satisfies:
|, (Trim - X. lr - IW -X.llr + Cort/21 X.11?
(6)
Imin (d,
where Co 0 constant.
Lemma B.2 (Lemma 6. (Tong et al., 2022)), Suppose that X, is ju-incoherent, nh 2 + Kin and p satisfies:
pス -- n prr 2 kū log (n) + E -2 - 2 (n),
for some small constant Then with high probability, the spectral initialization W in Algorithm satisfies:
I! X.IIe I co (X.).
Lemma B.3 (Lemma 20, (Tong et al., 2022)). Suppose satisfies the Bernoulli observation model. Then, with high probability,
- s l0g")) + In
holds simultaneously for all N, E M,, here C₁ is a constant. Denote X' = Cx xi=1 X;,Y = Cr x²=1 Y, then the quantity t obeys
T S ( Y (CY))l [[x)((())ll 1 (c
(1 22
Y 2 A |2el Y 20 (1l 12,00 Y3llF A ||
Lemma B.4 (Lemma 18. (Tong al., 2022)). Suppose that Then, with high probability, one has:
S x x V E Ml p-incoherent, and nºp 2 1¹ n'nr² log
u log pra
- (a)(')))(AA) Xn)1 Cap
[ (Alli
simultaneously for all tensors NA,No, E Rn X22XXn in the form of
3 XA = Σ DA. jiti V, X2 AAA XB = Σ DBS x V, X U.
3
i=1
1=1
where U A, B E Ruxr DA,i, DB,i E Rexexr i == 1,2,3 are arbitrary factors, and C2 > 0 is a universal constant.
Lemma B.5 (Lemma 5.2. (Cai et al., 2020)). Let X.Xo E M, be two order-3 multilinear-rank-r tensors, then we have
7
II - TTx Mmin (X.)
18 - xx111
Lemma B.6 (Lemma 4.5. (Wei et al., 2020)). Lei U1, U2 E Raxr be two orthogonal matrices. Then there exists r X unitary matrix Q such that
UU - U22Q < |U Ur..
Lemma B.7. For any Z E Bd X x and N, we have
s 1
1122: < 14 1
(8)
where vi = E and μr = (e: + ([ 12)). Here we define G == max,=12233 max (l.()()))() be the maximum of G, 's slice norms and P: 14/4-
13

---

Preconditioned RGD Low-Multiinner--an Rank Tensor Completion
Lemma B.8. The operator (W e, f) have the following bound:
| - 5 E4 3 (1 1 -11
19
-
(9)
Proof. is straightforward since (es + (191112)= < 11 S E, -
Lemma B.9. for tensor X E My is y-incoherent, then X = Wi² is (pz m)--icchhreent.
Proof. Suppose X' D xi_ U, with U, 1,2,3, Then & D xi_1 U.)
Consider the orthogonalization G 1 U,:
U.R. with vT = I,, 1 1,2,3.
Then
G U. | | V RrilRa
thus R 1/VF v U.lI| - As the condition number ((R,) <x( s p we have
R 1l2 | <(R.) S 14 pi:
Now we consider the |V2.22.0 max; |le V ll2 where e; R"x is vector with i-th element be 1 and others be 0.
l V = ll; G U. 112 $ lle, G. | s vi ot lle G U.l12 s of lle U.ll2-
So Vil2,,00 S p² 1111,,, and Incoh(A) (²) S pi
Proof of Lemma 4.2
Proof. By Lemma B.2, the with the requirement of sampling ratio p. the tensor w from Algorithm 2 satisfies
mmin (X..)
I X.1lx W
15000Cor
with high probability. Thus by Lemma B.I, the initial tensor 2 Hr, (Trim; with & incoherent with parameter 2nngg and satisfies
sllw 7n
is and X is
1x0 - X=1lF I 1IW Xxx + C/r1/21110 - 11.
Tmin (X.,
mmin (XC.)
10000Cor
Proof of Theorem 4.1
Proof. Now we prove the linear convergence of Algorithm Using the idea induction, we start the proof assuming ||44- X.Ilr < [min(X.) and Incoh(Xi) 2rio (here the constant Co keeps the same with constant in Lemma B.
10000C.r
Denote Pt. = ";:: X. and a; -1 Then, by Lemma 3.4, we have
14

---

Preconditioned RGD LowoMuulttiinrr--RRa Ran- Tensor Completion
I X,1, || a. a R. W Pald" xx.) X.
- 11 - 8) - a1 Ax 1 R,W 18 (8--(()) -x:]1l
- -1(22* - 82 - Px 18' X.) G
9 -p (0,,, PnW, -G + g) - &)
- =1( Tx 108 x) F of
9 (1 w ,W -4 - 100" -2)1le
= 110 Pr x1)
18
21 r + o 8 (P 10, AnW -W, + W.¹ E g) (110-11)) -iilll (10)
< ( xx )(8 8 te/
b/2
Pix W } ( p- (2) - -x,) F
+ Pr F1 (W,
- $ )) - -21 4
13
Now we turn to estimate the 1 12, 1s, respectively.
Estimation of L1. By Lemma B.5
c 4
7
< mmin (2te) 1|-- -xal
(11)
0 miin (x
where the second inequality follows from (8) and miin (#/²x') X+.) 2 e, mmin (de).
Estimation of Ia.
By Lemma B.8:
I3 S ( - - ( 299 F
Gelll ) -3)) )1)) || - 22. 11
I 4 -
+
(12)
11eel1 -3) :t) 1
S c pi
1
1 +
- x:11
Et
where the third inequality follows from the Lemma B.7.
Estimation of Iz.
For simplicity, we omit the subscript & and denote X' = - -,;3 X. in the following. Now we first fix orthogonal decomposition of X = x x Ü, then we choose an orthogonal decomposition of E, accordingly. Let &. D' x3 x Ü be orthogonal decomposition, then we define the following R1, R2, R3:
1 - Ü.R. i= 1,2,3.
R = arg min RED.,
Here, O, contains all unitary matrices with dimension X Tj. Then we define U, Ü 1,2,3 and D. D' x R. Thus R, = D. x 0. In this manner, by Lemma B.6 we have:
-, < i.u. 0'000 S V2 R.
(13)
Mmin (Z.)
15

---

Preconditioned RGD Low-Muultiiinrrr-RR Ran Tensor Completion
where
== W. 2 "_=,,&=00 = x Us X. -, =D. x²_ U.-
Then, 12 is rewritten as
1/ = ( ( ( - -x),,
-
= ( 9a)x X.), W,, Txx 26)-
for some No with || S 1. Since TTx = C x Ü, Ei= D xjys Ü, x; W; for some C and W.,i 1,2,3,
we have
W. TT Xo C x U,
D j U, x: W
(14)
No,o
Xo.
where No,5, 3,,,, are all rank-r tensors. We also split X X. into the sum of rank-r tensors:
D x Ü, D. _ Ü, (D - D.) X1 U1 X2 U2 X3 Us D. x1 (ū1 - U, x2 U2x
(15)
DD. x1 U, X2 (U2 U2) x3 Ug + D. x1 U, x2 U2 X3 (Ü, U,).
3%
34
Thus,
-0-1-1a0(( X,), 3 Ix
Ko)
ΣΣ
(p No,)-
(16)
Before estimate the terms in (16) using Lemma B.3, we give the following estimation on factor matrices and core tensors.
Upper bound of C and W.
T For C: Since C = No x Ü, and Ü,' iss are orthogonal matrices, ||C|| = || S 1.
For Wi: Because W. = (J,: 0,0, Mi j#
(D) where .((((D) is the Moore-Penrose pseudoin- x 0 0,),a (D)
verse of MDD with (( Ir., we have
|| s |m Ü,Ü, Ilall-4, (D)llll j Ü,11e 11 S (m) S v 1 (X),
and thus ||olee $ 1/ W 1F S v/ 3 Tm (X').
Upper bound of Ü Ü, D - D., and Ü, - Ü, For ease of exposition, we suppose the incoherence parameter of X' and X, are Ho and p1, respectively. Then by Lemma B.9, the incoherence parameter of & and E. are p po and p P1.
I ni For Ú, Since |0 S Vri and | 111,,00 S pē poy
100,2 I HOpp - ri Tuel SVz Vri
Vri Vn,"
For U/: Similarly,
110 s mipivo V |0 S siz Vr,
For U, Ü It follows from (13) that
1 -ille vi t 1000001100 - -f1le Sv - 22
R.lle
- 4 /212 - X2
vi p: (2i)
Tmiu (E.)
10 12,00 s (wo + ur)Prrs v1 1 Pi
Vna'
16

---

Preconditioned RGD LoWoMutttttinnnarRRRa Tensor Completion
For D and D,: since X = D x U. = D. x²=1 0g are two orthogonal decomposition, one has:
| = 1128|11 I Vin. mmxx |p.1|r = 1|A.Ile l1 S Vinl m (2
For D - -D: We have
- 8 ||D. - D1r 11 x i= -0,)--
x U, 1|r $ P x1 -0) x2 (ū,) X3 (Ug) 1 || + +1 x1 U, X2 - x3 <s("))" FI
+ l| x1 Ú X2 0, X2 (0, - + 11(2, - -2) x 0,1 |F
< 1.F (102 - U, + |0 - Ü2l1F F + 10 - -ÜalP) + || 811
2 3 (R.) pē 221 XF 1| =
m (2.)
S 44Vrnoju * Pi 11
Now we estimate terms (($ p -p-1 Pa)lk Xo.) for k; = 0,1, in (16) as follows.
For k: =1= 0, we use Lemma B.3. To this end, we notice that
|i 22, 1 1 11
I 122,00
D.Ile [ 11111////
S soop? V
-
(11
=1, -
vri 4/Trouu 221111 Xx 1.11
V n1
S 4por
3 2n
- 2/2
uu
- b
312
p
nollo - -X.11F
and, for = 2,
(U,12,0010..l1 Hop? v/
- V Vin us
Vrs S porny - + U/ pp=
Thus, Lemma B.3 implies that, with high probability,
-l-----aail No.o)1 si
log
+
n log (n)
1 u =2 211x1 -x.11
-
p
p
(17)
1 11-0 -X.1F.
0.00010;
as long as
p 22 C max (n) - 2 (n) nn - >/p,
where C' > 0 is a sufficiently large but absolute constant.
When k = 0 and = 1,,,3, we use Lemma B.3 again. For 1 = 1, we have
||ū iD D.) 12,0 W (D) S Ü 1|,,0,0010
W Wills||111
S Hoppir vi
-b
Ti V
....VTOTHH pł 1| X.11 plll:0 vi - 3 (X) Vrppoomxxx2 (X)
m
n
< 4por nn
- b
No ui Hmpp
-
max (2) 11 X211F.
miiu (x)
For 1. = 3, we have
, - D.))l2.00 U (D))l S 10,112,,00110 10..oolDDDD..0 (
s popp vj -b v [ri AVTROuu pt || - -xalle vi -b vri vrri o (x)
S 4 ni &11 Sapi mox - -Xalee
17

---

Preconditioned RGD Low-Mallllnner--aa Rank Tensor Completion
and
12 I pop: V ni
Pi m2) S Hortn, 21, Pi o (2), i= 2,
V
Thus, it follows from Lemma B.3 that, with the conditions satisfied, for / = 1,2.3.
log
n log (mg)
1grin 3pp maxx (A) - 1 - 1. 1
I( -11-----0)00 Xo,i s Gi
miin (x) 1/
p
P
Summing it over 1, we obtain that, with high probability,
[i pp- p-lP--plPP Xo.1) S 11000,,-111-0 -x-11
(18)
as long as
mmxx (2)
minn (X) Ko, (ogg((n)((a (n) "6 nn -3 o Fine (dt
2 C max log (n)33r pi
pg min (2t) Kg
When It 1,2,3 and 0, the estimation is done similarly by using
(n)
n Ing
111 -p- 10-1pppaaaa Pa))1, Xo,0) Sc
-
| |
ÜallF
log (n)
n logo
S Ci
(1011l2,00 (1511l..00
P
P
-
log log" (n)
n log
1gr : An # 128 X.1lF; (og)((n)
$ Ci
p
11( p1aaa) No,0 S
log2(n)
+
n
log"(n)
IP.I=
||0
2
I12
Ü21F
1 Üzllf
log
logg((n) (n)
[1üilla.e (i2l2.x))
S
+
P
log2(n)
n log nlgg((m)
(n)
1
paurr'n Ap 11 XiIle.
p
p
18

---

Preconditioned RGD Low-Multllnear--aa -an Tensor Completion
and
log"(n)
n log nog)(n)
111 - p Pallss so,0)1 S
+
1 |
p
p
|1
2
12,00
U2|
|
[0 - Üğāl
log"
n nlog (n)
S Ci
(10i 1
P
||01||/||U2||1|||
Ü U2
log (n)
n llg (n)
$ Ci
&p 2112 -x,1IF
Summing them up and noticing no 2 la give that, with high probability,
(SS-p-Pa))i Kn,o) < 0.0001e, + X.1lr,
p- 9n))),
(19)
long
p 2 C max log ( ppp mmax (X)
mmin (X) Ko, (n)ugr nn -3 max (2))
o
2
Pb o2
min (2)
Kig
When k + 0, and k = 1, we further divide it into three cases.
For k = = 1, recall that
Xu, D W1 X2 U2 Xs Us.
-D D1 -ū)
x2 0, x3 Ü..
which, together with Lemma B.4, implies that
nino² log n pm
1( - pー D,),,, S C2/
|.o,llee ||
M Mino² log n
S C2y
U Us P..IE [Will 11ū - -Ūille
p
Vâno log n
max (2)
$ C2y/
1
| - xx,11e..
pm
mmin (X)
For = 2, notice that No,2 D x U1 X2 W. 2 X3 U and
Y/2 = U x2 U - Ú2) X3 Ug D. " Ú,) (1)x x2 (Ü, Ú x3 U..
-Ú)
x3
V/.2
Therefore, Lemma B.4 gives
2ânr² log pm3
11/5- 1(0--~-'0) 11) SC2
12 [|>ll
n log pmo
S $22/
U 1 W2ll JŪ U2il1
S <O21
"Ânra log n pr3
p Kn
3
σ max (2)) -
U1 1| -x.llr,
σ min (x)
19

---

Preconditioned RGD Low-Muttttinee Rank Tensor Completion
and Lemma B.3 gives
|( pp- D~)n))D2222 Yo,2)l
lon"(n)
n (og
SC
[0111,01/P1111111 - D.D..
p
I02 - U2112,00 W2llF 10 1اا1
(n)
n (n)
mmx (2t - V 11 X.1lr.
Ci
1o(m0 /2)rr pp no
p
p
Tmiu (2)
For = 3, we utilize 3/3 D. x U X2 2, X3 (Üz - ( and
Xo,3 D x1 X2
x3
D
x1 U x2 (U2 -2) x3 W3+DXi x1 (Ü1 0,) x2 U2 x3 W3
X
X4,3,2
No,3.3
Then, is deducted from Lemma B.4 that
p n log n
I( - p-11111) Xo,3,1)1 s /
10,,,111 ||>'sl
pño
n log n pro
s Voy
1 D. W 11 Ü2ll
mênoa log n
o max (X)
1/2 2 $1,2 - -X,1le,
S C2y
T pi Ko
pms
mmin (x)
and from Lemma B.3 that
(ng
n (n))
K( - Pa)l's, No) X0,2) SC
+
U0 2,00 | |11= ||D.||
p
p
I
00.12,00110
Ü22
- 103 2212,,00 W
-
S
log" (n)
n p
log (n)
nn(P0 + #))r p,
mmax (2) 1
m (2) 1/ 11.2 - X.1lr
p
and
log (ng
n log llgg(n) | DP.1lel U, - ÜT|Lr|1Pl
K( -p-1ga))' X Xo,3,a SC, 5
p | 020 U2llF -10 02l12,00 WallF
p
log
3 (n)
n mnlog (n)))(n)
mmax (2) - 11/2'-
S <
+
uilno + m1) n mo
1/2 T (x)
- 1.11F..
P
The above inequalities are added to derive that, with high probability.
3
- Σ |( -p - Pr).. S 0.0001v; - 311x- -Xille,
(20)
as long as
log" (n))()) -/8 mmax (2))
Ko, (n) v Vlg(n))22( nn nn-3 3 2 (2)
p 2 C. max
Pr min (X)) Kg
min (x)
20

---

Preconditioned RGD Low-Multiinear--Ban Rank Tensor Completion
When k + 0,1 0, j discuss it in several cases.
For k and | 2.3, we have
log"(n)
n (n) +
1( - pp'
sci
1111111 - U/l.=|D.11I
P
112212,,00
W W2llF ||0all,,00 1331F
log (n)
n nlog"
1gr 8p8 9 Ko
maax (2) -
I C1
1/2 11 X=lle
m (X)
p
p
and
log
logg"(n) (n)
001l210001P Uill=-ID.11
|1ū 212,,0
Ü22lF
110 1
W3llF
log"(n)
n log (n)
mmax (X) 1 11 - X.
pgron 7 p2 no
S Ci
+
o (X) 11
p
- For k == 2 and / = 1,3, we have
log)(n)
n log (n)
(n)
11(5 - p- Pp) No,1)l 5c, Sc
+1
p
p
I02 2|02212,,00
U2lo
1
Üzll
log S
log²(n)
n log (ng)
mmax (2') -1 2 11,8 - Xx
paurr" 3 pē ki mmin (x) 11
P
p
and
log"(()
n (n)
Ko.aH| sa
+
P
P
1|02222,000 1 - -Uile 1 WsllF
(ogg(())
n (mg
max (2)
<
Ci
+
m 3 2p8 NO
m (2) 11 11 X.11r.
p
P
- For k = 3 and / = 2, we have
log
n log)(()
1( - pp Pallss No,1)
I Walle//
p
p
-11 1 Ü2lla
1
U - -UGl
s Ci
log2(n)
n nlogg
f n. 3 ppt No amin (x) V/ 11 - Xx
Fmax
(xaxx(X) (X) -
P
p
21

---

Preconditioned RGD Low-Mullttinerr--R. Rank Tensor Completion
and
log (n)
log (m)
[( -p-1pp1-00
P1)''s ko,2 S
+
p
P
||U 2,,0
W 22lF | 103- - 103l5
(ng
log
(l)og(n)
m mx)
MouR pp No m (2) 11 1| Xalls-
+V
P
P
Summing all inequalities up, we obtain that, with high probability,
Σ Σ Mi - -p-1 No,1 0.0001,, +||X8 - X.1IF,
(21)
k=11-111thh
as long as
max (2)
Kon (n) wn "p max (2)) min (2) Kig
p C max (n))gr)) n pp
mmin (2)
By combining (17), (18), (19), (20), and (21), we have the following estimation of I2, with high probability,
1 Pn)), Xo.) 0.0005k; - 2| X.
12 s
(22)
k= t=0
as long as
{ (n))@n
T max (X) min (x) No. (n)g(())a v log(n))(rr)) nā nn- pi pmnx (2)
2 C' max
min (x)
Kg
Now we take e, Ge which yields Pr 22. Since #M KOV, p1 -22K, and
1amin (X*)) amin mmin( (X.)) |omax maxx (X.)) S |2 - X:11 S 10000 min (X.),
the estimates (11)(22)(12) imply that: if p 2 C max (log In) 2ng. (nog(m))&nnr") log(m))(n3rr) nn 3/0
then, with high probability, it holds that
J 0.001 - X.lle Plugging these estimats in (10), obtain
12 < 0.0005e; $1120 - -x,1le, Is I 0.3485V, $ $1120 Xx111.-
Iw
Xe 21 + + 12 + c¹ 11 S 0.35v 1|x - X.
Finally, by Lemma B.I, Lemma B.7, and the assumption || -x--x S mm)n we obtain
100000.r
| X1
Hr (in,Hr(Trinn (Trim; -1x))ll)
2/.2/211114 X2.13
< I - XallF +
Omiul (2a)
1 I -Xillx,+ 1 1/2 pM - X'o 13,
1
14.
Omin Omin(Ka)
< 0.35|| - -Xalle + 1/r-12
0.13|120- - -Xx
m (X.
s 0.351 -x.11.
22

---

Preconditioned RGD LowooMtlttthnnaaaRatt Tensor Completion
This implies that || X- 1| <
(miu((.))
and Incoh(X*+1) - 22no, which conclude the proof of Theorem 4.1.
10000Cor
23

---

Preconditioned RGD Low-Multlinear--ann Rank Tensor Completion
C. Appendix
Phase Transition
0.9
0.9
0.8
0.8
0.7
0.7
Shopes Tate
Success rale
0.6
0.3
0.2
Treasr Size (15, R0, 70)
0.2
Tudke Baak
Unaos Sax (106, 106, 1000
Beak
0.1
Diaes 1120, 128, 125)
0.1
08
08
30
63
50
prt 1/
Figure The success rate of PRGD with rank and size ranging from 50 to 150.
Figure 7. The success rate of PRGD tensor with size
100 and rank r ranging from 3 to 7.
Noisy Data Reconstruction
The results of noisy tensor completion with n 100, 10, OS = 10 and a E (5 x 10 10-4, 10- X 10 ,,10-2,5
10 20 100101
FRGD
18
10
18
5e0tte mee
Rebatee Smer
Rubaba
28-7
10
28-
52
120
150
200
250
300
252
422
20
100
335
202
233
330
350
400
33
120
150
200
250
300
350
422
ltrations
her382r5
Itrodton2
Figure = 10-4
Figure 9. 0= 10-3
Figure 10. 5 10
10"
10-
105
10
Rebove Ererr
Rekriee.ror E/T
10-7
12.4
10
28
Ibraatinn
Ittottinn
Figure 11. o -0 -
Figure 12. o= 5
Pigure 13, == 10
24

---

Preconditioned RGD Low-Mallllnear--Ban Tensor Completion
Video Inpainting Result
The original video is represented || - //|| Σ 10-2 To demonstrate the representability within the Tucker format, apply the HOSVD to Xr with multilinear rank of (r, r) and the resulting tensor XLR serves near-optimal approximation. Detailed results of recovered tensors from different algorithms, along with AiR, are presented in Table 2 and Figure 14.
three-order tensor X. For each algorithm, the stopping criteria is chosen when
Table PSNR values and relative errors of the recovered vidcos from difterent algorithms for three test vidcos under varying multilinear ranks.
PRGD
RGD
SCALEDGD
ALR
VIDEO(SIZE)
r
PSNR
ERR
PSNR
ERR
PSNR
ERR
PSNR
ERR
50
27.34
8.711E-02
27.15
8.906E-02
27.09
8.970E-02
27.69
8,370E-02
TOMATO
60
27.79
8.272E-02
27.44
8.608E-02
27.15
8.900E-02
28.41
7.699E-02
(242,320, 320, 501)
70
28.25
7.847E-02
27.50
8.547E-02
27.15
8.907E-02
29.12
7.095E-02
50
27.61
7.090E-02
27.43
7.244E-02
26.68
7.892E-02
28.11
6.693E-02
HALL MONITOR
60
28.34
6.522E-02
28.06
6.737E-02
26.25
8.295E-00
29.10
5.975E-02
(288, 352, 300)
70
28.83
6.166E-02
28.75
6.220E 02
28.52
6.390E 02
30.08
5,337E-02
29.29
7.616E-02
29.09
7.787E-02
28.81
8.04SE
29.87
7.123E-02
AKIYO
60
29.95
7.054E-02
29.69
7.267E-02
28.67
8.181E 02
31.01
6,245E-02
(288, 352, 300)
70
30.45
6.663E-02
30.42
6.681E-02
28.62
8.227E-02
32.12
5.497E-02
Figure 14. The recovered results of three videos with 70. From top bottom Tomato-Ist frame, Hall Monitor-40th frame and Akiyo-15th frame. From left to right are original, observed, PRGD, RGD, ScaledGD and Ain-
25


Reviews:
[{"review_id": "lreKcdyI6H", "reviewer": "Reviewer_NJ9K", "summary": "This paper introduces the Preconditioned Riemannian Gradient Descent (PRGD) algorithm for low-multilinear-rank tensor completion. By designing a data-driven Riemannian metric and an efficient diagonal preconditioner derived from gradient statistics, PRGD achieves 10× faster convergence than standard Riemannian Gradient Descent (RGD) while maintaining comparable computational complexity. Theoretically, PRGD guarantees linear convergence under near-optimal sampling complexity \\(O(n^{3/2})\\), validated by synthetic experiments (e.g., 10× speedup for \\(n=100\\) tensors) and real-world video inpainting tasks (e.g., 0.75 dB higher PSNR than RGD on the Tomato dataset at rank 70). The method addresses tensor incoherence/spikiness via gradient-based preconditioning and tangent space parameterization, providing a computationally efficient solution for high-dimensional tensor optimization.", "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": "> **Q1:** In the experimental section, the author presents too few...should be provided.\n\n**A1:** Thank you for your constructive feedback. We have conducted video inpainting on the videos from your recommended source (see section 5.3 and page 25). In response to your suggestion, we expanded the experimental evaluation to include additional **color image and video inpainting tasks,** incorporating the **suggested PSNR, SSIM, and Runtime (seconds) metrics**. The datasets used are *Tomato* (T), *Akiyo* (A), *Hall-Monitor* (H) videos, as well as the *Airplane (F-16)* color image.\n\nAdditionally, as suggested by Reviewer eeW6, we compare our algorithm with TT-RGD (Tensor-Train RGD) on both image and video tasks. Below, we summarize the results:\n\n**Video Results:** Sampling ratio $\\rho=0.1$, Tucker rank $(70,70,70)$. For TT-RGD, we set TT rank $(33,33)$ to match parameter dimensionality.\n\n| |PSNR(T)|SSIM(T)|TIME(T)|PSNR(A)|SSIM(A)|TIME(A)|PSNR(H)|SSIM(H)|TIME(H)|\n|-|-|-|-|-|-|-|-|-|-|\n|**PRGD**|**28.25**|**0.754**|12.80|**30.45**|0.869|23.91|**28.83**|**0.824**|39.83|\n|**RGD**|27.50|0.711|9.59|30.42|**0.870**|16.58|28.75|0.820|24.61|\n|**ScaledGD**|27.15|0.678|**9.27**|28.62|0.812|**12.57**|28.52|0.813|**23.98**|\n|**TT-RGD**|26.65|0.673|158.05|28.27|0.821|143.49|25.71|0.736|180.57|\n\n**Image Results:** *Airplane(F-16)* image with size $(512,512,3)$, $\\rho=0.3$.  The Tucker rank is set to $(r,r,3)$ and varies $r=20,30,40$. The TT rank $(r_t,3)$ is set accordingly to match parameter dimensionality.\n|$r=20,r_t=10$|PSNR|SSIM|TIME|\n|-|-|-|-|\n|**PRGD**|**23.16**|**0.659**|0.41|\n|**RGD**|22.93|0.648|0.35|\n|**ScaledGD**|22.80|0.647|**0.33**|\n|**TT-RGD**|20.74|0.591|0.83|\n\n|$r=30,r_t=16$|PSNR|SSIM|TIME|\n|-|-|-|-|\n|**PRGD**|**24.80**|**0.695**|0.76|\n|**RGD**|24.71|0.692|0.73|\n|**ScaledGD**|24.70|0.695|**0.69**|\n|**TT-RGD**|22.16|0.609|1.05|\n\n|$r=40,r_t=21$|PSNR|SSIM|TIME|\n|-|-|-|-|\n|**PRGD**|**25.77**|**0.716**|0.83|\n|**RGD**|25.46|0.704|**0.61**|\n|**ScaledGD**|25.47|0.703|**0.61**|\n|**TT-RGD**|22.76|0.612|1.35|\n\n**Key observations:** PRGD consistently outperforms baselines in PSNR/SSIM with comparable runtime needed. Also, TT-RGD lags in both performance and speed, highlighting the advantage of the Tucker-rank approach.\n\n> **Q2:** The author should provide ablation experiments\n\n**A2:** Thank you for your suggestion. Actually, in our current experiments, we have already included key ablation analyses. The primary innovation of PRGD is the preconditioned metric. **By removing this component, PRGD reduces to standard RGD**, which we compare against in all experiments. For real-world data, we further validate PRGD by **testing different rank parameters** and giving detailed comparisons.\nAdditionally, we are happy to conduct additional ablation studies if you could specify particular components.\n\n> **Q3:**  Preprocessing and Riemannian optimization both appear to be existing technologies. The innovation of PRGD lies more in the combination of these methods rather than a disruptive breakthrough.\n\n**A3:**  Thank you for your comment. To the best of our knowledge, existing Riemannian optimization methods on the fixed-multilinear-rank manifold use the canonical metric. We design a computationally efficient preconditioner tailored to the fixed-multilinear-rank manifold and provide rigorous proofs of convergence theory, which distinguishes PRGD from prior works.\n\n**Computational efficiency:** Methods like Shampoo [1] rely on dense preconditioners requiring outer products of historical gradients, which are expensive for large-scale problems. **PRGD’s preconditioners are several lightweight diagonal matrices**, preserving similar per-iteration cost as RGD while achieving more than $10\\times$ faster speed (as empirically validated).\n\n[1] Gupta, V., Koren, T., & Singer, Y. Shampoo: Preconditioned stochastic tensor optimization. In International Conference on Machine Learning (pp.1842-1850). PMLR, 2018.\n\n>**Q4:** The author mentioned about data-driven metrics. I'm not sure if data-driven here means being able to automatically learn according to the characteristics of the data. What features does it have?\n\n**A4:** Thank you for raising this important question. Our data-driven metric is designed to automatically adapt to the local geometry of the optimization landscape by utilizing gradient information at each iteration. The preconditioners $G_{t, i}$ in (3) are constructed from **the iteration data**, more specifically, the diagonal entries of the outer product of gradient unfoldings, which implicitly approximate the Hessian matrix. This ensures the metric flattens the objective function, enabling PRGD to take more effective descent directions.\n> **Q5**: There are some typos....carefully.\n\n**A5**: We sincerely appreciate your careful reading and valuable feedback. We have corrected all identified typos and made a full proofreading of the final version.", "claims_and_evidence": "Please refer to below", "methods_and_evaluation_criteria": "Please refer to below", "theoretical_claims": "Please refer to below", "experimental_designs_or_analyses": "Please refer to below", "relation_to_broader_scientific_literature": "Please refer to below", "essential_references_not_discussed": "Please refer to below", "other_strengths_and_weaknesses": "Advantage：This manuscript combines preprocessing techniques with Riemannian optimization and proposes a data-driven preprocessing Riemannian metric. In terms of theory, the author provides rigorous proofs demonstrating the linear convergence of the method and that the sampling complexity is close to the theoretical lower bound.\nDisadvantages: \n1.In the experimental section, the author presents too few experimental results, which do not provide sufficient evidence to convincingly demonstrate the advantages of the proposed algorithm. The author should refer to article and increase the number of experiments. The experiments should include color images and videos, and performance metrics such as PSNR, SSIM, and TIME should be provided. The datasets can be referenced from the following sources: https://sipi.usc.edu/database/database.php and http://trace.eas.asu.edu/yuv/.\n2. The author should provide ablation experiments.\n3. Preprocessing and Riemannian optimization both appear to be existing technologies. The innovation of PRGD lies more in the combination of these methods rather than a disruptive breakthrough.", "other_comments_or_suggestions": "There are some typos，eg:\nRiemannain optimization\" → \"Riemannian optimization\"，\"ap plied\" → \"applied\"，Sampling complexity formula uses \\(\\overline{n}\\) without prior definition (defined later in 1-36), and others.\nThe author should check typos carefully.", "questions_for_authors": "The author mentioned about data-driven metrics. I'm not sure if data-driven here means being able to automatically learn according to the characteristics of the data. What features does it have?", "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": "RitsgkfQuT", "reviewer": "Reviewer_eeW6", "summary": "In this paper, the author introduces a Preconditioned Riemannian Gradient Descent (PRGD) algorithm for low tensor completion based on Tucker decomposition model. A data-driven Riemannian metric is proposed to accelerate convergence. Theoretical analysis is given to guarantee the recovery performance. Experimental results verify the desired performance of the proposed method.", "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": "> **Q1:** Could the proposed method be applied to higher-order data (4th-order tensor or higher?)\n\n**A1:**  Thank you for raising this important question. Indeed, our PRGD algorithm can be extended to the higher-order tensor case and handle higher-order data.\n\nFrom the algorithmic perspective, for the general $d$ order tensor case, we need firstly to compute preconditioners, e.g. the diagonal matrices $G_{t, i}, i=1, \\dots, d$, following the same manner as in (3). And the data-driven metric in (4) will be $\\langle\\mathcal{X}\\times_{i=1}^d G_{t, i}, \\mathcal{Y}\\rangle$ where $\\mathcal{X}, \\mathcal{Y}\\in \\mathbb{R}^{n_1\\times \\cdots\\times n_d}$ are two arbitrary tensor. Next, we can **extend the tangent space parameterization in Lemma 3.2 to the $d$ order case**, which involves $d$ gauge matrices and $d+1$ components as in (5).  Based on this tangent space parameterization, we can derive the tangent space projection formula under $\\langle\\cdot,\\cdot \\rangle_{\\mathscr{W}_t}$ and the preconditioned Riemannian gradient. \n\nRegarding the convergence theory, we first need to extend our key tools, the concentration inequalities in Lemma B. 2 and Lemma B.3, to the $d$ order case. Once this is done, **the contraction analysis of the distances between iterates and ground truth can be conducted within the same framework** as presented in the current work, thereby establishing the linear convergence of the algorithm.\n\n> **Q2:** Could the proposed method be extended to other types of tensor decomposition model (CP, TT or TR)?\n\n**A2:** Thank you for your insightful observation.  Indeed, the proposed method can be extended to the TT format, as the set of **fixed-TT-rank tensors forms a smooth manifold** [1]. By endowing the tangent space of this manifold with our preconditioned metric, one can derive a TT-PRGD method.\n\nRegarding the CP and TR formats, the situation is less straightforward. To the best of our knowledge, the set of fixed-CP-rank tensors does not form a smooth manifold, and it remains unverified whether the fixed-TR-rank set forms a smooth manifold. However, it is still worth exploring other preconditioning strategies for these formats, which could be an interesting direction for future research.\n\n[1] Holtz, Sebastian, Thorsten Rohwedder, and Reinhold Schneider. \"On manifolds of tensors of fixed TT-rank.\" *Numerische Mathematik* 120.4 (2012): 701-731.\n\n\n>**Q3:** Please add comparisons on real data, as tensor completion is a task that many tensor completion methods (not only Tucker format) can be compared.\n\n**A3:** Thank you for your insightful suggestions. We have expanded our experiments to include comparisons with other format tensor completion methods, specifically the Tensor-Train format RGD (TT-RGD) algorithm [2], on both color image and video datasets. The code of TT-RGD is obtained from the Manopt toolbox. The results demonstrate that **TT-RGD lags in both performance and speed**, highlighting the advantage of the Tucker-rank approach. **Detailed comparison results and analysis are included in our response to Q1 of Reviewer NJ9K.**\n\n[2] Cai, Jian-Feng, Jingyang Li, and Dong Xia. \"Provable tensor-train format tensor completion by Riemannian optimization.\" *Journal of Machine Learning Research* 23.123 (2022): 1-77.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I roughly check the proofs. No big issues.", "experimental_designs_or_analyses": "I've checked the experimental analysis. No big issues.", "relation_to_broader_scientific_literature": "The author proposes a novel data-driven Riemannian metric construction method with theoretical guarantees, contributing to efficiency in tensor completion.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength:\n \nData-driven method with theoretical guarantee and experiment verifications.\n\nWeakness:\n1. The order of tensor is limited to 3.\n2. Limited comparison in experiments.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Could the proposed method be applied to higher-order data (4th-order tensor or higher?)\n2. Could the proposed method be extended to other types of tensor decomposition model (CP, TT or TR)?\n2. Please add comparisons on real data, as tensor completion is a task that many tensor completion methods (not only Tucker format) can be compared.", "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": "UNtFY1czLH", "reviewer": "Reviewer_1EC9", "summary": "This paper introduces the Preconditioned Riemannian Gradient Descent algorithm for low-multilinear-rank tensor completion, leveraging the manifold structure to achieve faster convergence than standard Riemannian Gradient Descent while maintaining the same per-iteration complexity.", "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": "> **Q1:** The proposed method appears somewhat unconventional. What is the motivation for introducing (4) and (5)?\n\n**A1:** Thank you for your question. The derivation of PRGD involves **two essential steps:** (1) endowing the preconditioned metric to the tangent space of the iterate on the manifold. (2) projecting the Euclidean gradient onto the tangent space under the preconditioned metric to obtain the preconditioned Riemannian gradient. \n\nSpecifically, **(4) is to define the preconditioned Riemannian metric and (5) is to reparameterize the tangent space**. This reparameterization ensures that the four terms in (5) are mutually orthogonal under the preconditioned metric. Consequently,  we can derive the explicit formula for the tangent space projection operator and the preconditioned Riemannian gradient according to Proposition 3.1.\n\n> **Q2:** In line 219, $\\mathscr{W}_t$ is not defined. Additionally, if the inverse of  $\\mathscr{W}_t$ needs to be computed, it may not be easy or computationally efficient.\n\n**A2:**  We have defined $\\mathscr{W}\\_t$ in (4) (line 195) as $\\mathscr{W}\\_t(\\mathcal{Y})=\\mathcal{Y}\\times\\_{i=1}^3G_{t,i}$ for $\\mathcal{Y}\\in\\mathbb{R}^{n_1\\times n_2\\times n_3}$, where $G_{t,i}\\in\\mathbb{R}^{n_i\\times n_i}$ ($i=1,2,3$) are preconditioned matrices.\n\nRegarding the inverse of $\\mathscr{W}\\_t$, since $G_{t,i}$ are diagonal matrices, computing $\\mathscr{W}\\_t^{-1}$ reduces to **element-wise scaling** of the input tensor. In PRGD, we only apply $\\mathscr{W}\\_t^{-1}$ to the sparse gradient tensor $\\mathcal{G}^t=\\mathscr{P}\\_{\\Omega}(\\mathcal{X}^t-\\mathcal{X}\\_*)$ , which only needs $O(|\\Omega|)$ operations. **This cost is negligible compared to RGD's computations**. Thus, the $\\mathscr{W}_t^{-1}$ is computatioanlly efficient.\n\n> **Q3:** According to the paper, the proposed method merely adds a complex residual to constrain the gradient’s step size. However, computing this residual is inefficient, and the motivation for using such a residual is unclear.\n\n**A3:** Thank you for your comment. We are pleased to clarify the motivation and computation efficiency of our preconditioners in (3) (line 187).\n\n**Computational Efficiency:** Constructing $G_{t,i}$ requires the diagonal entries of the outer product of gradient unfoldings, which correspond to the norms of mode-$i$ slices of gradient tensor (as explained in lines 202-206). Since gradient tensor is sparse, **this computation takes only $O(|\\Omega|)$ operations, making it computationally efficient**. \n\n**Motivation:** The outer product of gradient unfolding is used to **approximate the Hessian matrix** of objective function, as demonstrated in conventional optimization techniques such as AdaGrad [1] and Adam. To ensure computational efficiency, we preserve only the diagonal entries, while the parameter $\\epsilon_t$ ensures $G_{t,i}$ remains positive definite. Intuitively, this metric flattens the landscape of the objective function, enabling PRGD to take more effective descent directions.\n\n[1] Duchi, J, Hazan, E., & Singer, Y. \"Adaptive subgradient methods for online learning and stochastic optimization.\" JMLR 12.7 (2011).\n\n> **Q4:** Why should one transition from classical and simpler methods to the proposed approach,...,There should be compelling reasons to persuade researchers to adopt this method.\n\n**A4:** Thank you for your question. The PRGD algorithm we proposed is **computationally efficient while offering substantial improvements** over RGD.\n\n**As analyzed in lines 237-248**, the additional cost of preconditioning in PRGD is negligible compared with RGD.  **Thus, PRGD maintains the same per-iteration computational complexity as RGD.**.\n\nMore importantly, our numerical experiments (such as Fig 2 and Fig 3) demonstrate that PRGD **achieves approximately $10\\times$ acceleration** compared to standard RGD. We believe this improvement is substantial and provides a compelling reason to adopt our method.\n\n> **Q5:** As shown in Fig 5, the noisy data....substantiate the claimed advantages of the proposed method.\n\n**A5:**  Thank you for your question. The noisy data reconstruction experiment is designed to **evaluate the robustness of the algorithm**. As shown in the optimization plots (Page 24, Lines 1285-1319), **our PRGD algorithm consistently converges faster than the other two algorithms** across all noise levels. Consequently, when the stopping criterion ($||\\mathcal{X}^{t+1}-\\mathcal{X}^t||_F/||\\mathcal{X}^t||_F\\leq 10^{-4}$) is met, PRGD achieves a lower relative error. \n\nFurthermore, Fig 5 demonstrates PRGD's robustness, the relative error remains consistently below the noise level $\\sigma$. This highlights the effectiveness of PRGD and substantiates the claimed advantages.\n\n> **Q6:** In Fig. 2 and Fig. 3, the text... Some of the equations are numbered...their first appearance\n\n**A6**: We sincerely appreciate your valuable feedback. We have corrected all identified typos and made a full proofreading of the final version.", "claims_and_evidence": "The proposed method appears somewhat unconventional. What is the motivation for introducing (4) and (5)? In line 219, \\( W_t \\) is not defined. Additionally, if the inverse of \\( W \\) needs to be computed, it may not be easy or computationally efficient. According to the paper, the proposed method merely adds a complex residual to constrain the gradient’s step size. However, computing this residual is inefficient, and the motivation for using such a residual is unclear. \n\nWhy should one transition from classical and simpler methods to the proposed approach, which is more complex but offers only marginal improvements? There should be compelling reasons to persuade researchers to adopt this method.", "methods_and_evaluation_criteria": "See claims and evidence.", "theoretical_claims": "See claims and evidence.", "experimental_designs_or_analyses": "As shown in Figure 5, the noisy data reconstruction results at different noise levels indicate that the proposed method only outperforms SOTA methods in low-noise scenarios (less than \\(10^{-3}\\)), which is hardly observable in real-world applications due to the minimal noise presence. However, at higher noise levels (greater than \\(10^{-2}\\)), which are still relatively moderate compared to real-world cases, the performance advantage is not evident. Providing an explanation for this behavior is essential to substantiate the claimed advantages of the proposed method.\n\nIn Fig. 2 and Fig. 3, the text at the top of the figures overlaps with the figures.", "relation_to_broader_scientific_literature": "Tensor is widely used in computer vision field.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Some of the equations are numbered (e.g., line 23), while others are not (line 45). It is better to number all of them to ensure each equation is trackable. Additionally, all notations should be introduced before they are used, or at the very least, immediately after their first appearance.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "10TWysYTIv", "reviewer": "Reviewer_Mbdu", "summary": "The authors proposa a preconditioned Reimannian gradient descent algorithm for low-rank tensor completion. \nThe provide analysis of the computational cost and convergence guarantees", "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": "> **Q1:** The paper focuses on Tucker decomposition. Can PRGD be extended to Tensor Train (TT) or Tensor Ring decompositions?\n\n**A1:**  Thank you for raising this important question. **Please refer to our response to Q2 of Reviewer eeW6.**\n\n> **Q2:** Can the method be generalized to arbitrary high-order tensors?\n\n**A2:** Thank you for your insightful question. **Please refer to our response to Q1 of Reviewer eeW6.**\n\n> **Q3:** How sensitive is PRGD to misspecified rank selection?\n\n**A3:** Thank you for your question. To evaluate the sensitivity of PRGD to rank selection, we conducted additional experiments comparing PRGD with other SOTA algorithms under varying ranks. We fix $n=150,\\operatorname{OS}=15$ and choose rank $r$ from $3,4,5,6$.  For each algorithm, we conduct $3$ random trials and count the average iteration number and CPU time (seconds) required to achieve a relative error tolerance $10^{-4}$.\n\n**Iteration number:**\t\n||$r=3$|$r=4$|$r=5$|$r=6$|\n|-|-|-|-|-|\n|**PRGD**|71.0|131.3|106.7|53.7|\n|**ScaledGD**|269.0|476.7|296.3|205.0|\n|**RGD**|623.7|2293.0|1697.3|722.0|\n\n**CPU time (seconds):**\n||$r=3$|$r=4$|$r=5$|$r=6$ |\n|-|-|-|-|-|\n|**PRGD**|1.67|3.16|3.01|1.50|\n|**ScaledGD**|6.45|11.75|7.93|4.92|\n|**RGD**|9.34|35.65|28.45|13.67|\n\n**Key Observation:** PRGD consistently outperforms other algorithms across all tested ranks and is less sensitive to rank selection.\n\n> **Q4:** Riemannian optimization methods such as Gauss-Newton achieve faster convergence. How does PRGD compare in terms of convergence rates when tested against second-order methods?\n\n**A4:** Thank you for your insightful question. Indeed, the Riemannian Gauss-Newton (RGN) algorithm proposed in [1] achieves second-order convergence, while PRGD guarantees only linear convergence.\n\nHowever, RGN **requires solving a RGN equation at each iteration, which is computationally expensive, particularly for the large-scale problems**. In contrast, the PRGD algorithm maintains a similar computational cost to RGD. Overall,  PRGD might be more computationally efficient than RGN.\n\n[1] Luo, Y, and Zhang. A.R \"Low-rank tensor estimation via riemannian gauss-newton: Statistical optimality and second-order convergence.\" JMLR 24.381 (2023): 1-48.\n\n> **Q5:** How does the PRGD algorithm handle tensors with very high dimensionality or sparsity? Are there any specific challenges or adjustments needed in such cases?\n\n**A5:** Thank you for your insightful question. **The design of PRGD's preconditioners $G_{t, i}$ inherently addresses these concerns**. Specifically, the $G_{t,i}$ in (3) utilizes the outer product of the gradient unfoldings. To ensure computational efficiency in high dimensionality scenarios, we preserve only the diagonal entries, which **reduces the $\\mathscr{W}_t^{-1}$ operation to element-wise scaling** of the input tensor. Additionally, those diagonal entries are the norms of mode-$i$ slices of the gradient tensor, thus **computing $G_{t, i}$ takes only $O(|\\Omega|)$ operations**. This makes PRGD computationally efficient in the cases of high sparsity.\n\n> **Q6:** Could you provide more insights into the computational complexity of PRGD compared to RGD, especially for large-scale problems?\n\n**A6:** As analysed in lines 237 - 248, the additional computation cost of PRGD is $O(|\\Omega| + n r)$, which is negligible compared to the RGD algorithm, whose complexity scales as $O(n^3 r)$. Therefore, PRGD maintains the same computational complexity as RGD for large-scale problems. \n\n> **Q7:** Is $G_{t, i}$ the optimal choice, are there alternatives or tradeoffs to be made?\n\n**A7:** The Hessian matrix would be the optimal choice without considering the computational costs. Our $G_{t,i}$'s approximate the Hessian using the diagonal entries of the outer product of the gradient unfoldings, with $\\epsilon_t$ ensuring positive definiteness. This design balances efficiency, leveraging the advantages of tensor products (as in Shampoo [2]) and diagonal approximations (as in AdaGrad [3]), while remaining practical for large-scale problems.\n\n[2] Gupta, V., Koren, T., & Singer, Y. Shampoo: Preconditioned stochastic tensor optimization. In ICML (pp.1842-1850). PMLR, 2018.\n\n[3] Duchi, J, Hazan, E., & Singer, Y. \"Adaptive subgradient methods for online learning and stochastic optimization.\" JMLR 12.7 (2011).\n\n> **Q8:** What is the influence of the learning rate on the method's performance? Is the preconditioned Riemannian update sensitive to the curvature of the low-rank manifold?\n\n**A8:** The learning rate is important for PRGD's performance, as it directly impacts the convergence speed and stability of the algorithm. In our experiments, we tuned the constant step sizes for all tested algorithms to ensure optimal, enabling a fair comparison. \n\nPRGD is not sensitive to the curvature of the low-rank manifold. As demonstrated in Theorem 4.1, the contractive factor is invariant to the condition number of $\\mathcal{X}\\_*$, which can represent the curvature of the manifold.", "claims_and_evidence": "The claims are mostly clear and have theorem support. \n\nQuestion:\n- Is $G_{t,i}$ the optimal choice, are there alternatives or tradeoffs to be made?", "methods_and_evaluation_criteria": "The incorporation of preconditioners to RGD makes sense and evidently improves convergence speed. \nComparisons with state-of-the-art algorithms like RGD and ScaledGD are appropriate.", "theoretical_claims": "The Theorems are well structured and concise. \n\nIn lemma 4.2: Can you comment on the practicality of the spectral initialization? What happens if the singular values decay slowly (or at a slower than expected rate)?", "experimental_designs_or_analyses": "I think the experimental design is reasonable. \n\nWhat is the influence of the learning rate on the method's performance? Is the preconditioned Riemannian update sensitive to the curvature of the low-rank manifold?", "relation_to_broader_scientific_literature": "The paper seems to be well situated within the literature of low-rank tensor completion, and refers to recent works.", "essential_references_not_discussed": "I'm not aware of any misssing key references", "other_strengths_and_weaknesses": "Strength\n\n-The paper presents a novel approach to tensor completion with clear theoretical and empirical support.\n\n-The algorithm shows significant improvements in convergence speed, which is a critical aspect of optimization algorithms.\n\nWeaknesses\n\n- The paper could benefit from a discussion on the scalability of the PRGD algorithm for very large-scale tensors.", "other_comments_or_suggestions": "see above", "questions_for_authors": "- The paper focuses on Tucker decomposition. Can PRGD be extended to Tensor Train (TT) or Tensor Ring decompositions?\n- Can the method be generalized to arbitrary high order tensors? \n\n\n-How sensitive is PRGD to misspecified rank selection?\n\n-Riemannian optimization methods such as Gauss-Newton achieve faster convergence. How does PRGD compare in terms of convergence rates when tested against second-order methods?\n\n- How does the PRGD algorithm handle tensors with very high dimensionality or sparsity? Are there any specific challenges or adjustments needed in such cases?\n\n-Could you provide more insights into the computational complexity of PRGD compared to RGD, especially for large-scale problems?", "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: A preconditioned Riemannian gradient descent (RGD) algorithm is proposed for low multilinear rank tensor completion. Recognizing that tensors with a fixed multilinear rank form a smooth embedded submanifold, some standard operations such as projection to a tangent space and retraction (based on HOSVD) are presented for applying Riemannian gradient descent. A preconditioning strategy is proposed to apply in every iteration of RGD. Assuming the initialization is good enough, the proposed algorithm guarantees linear convergence to the global optimum with high probability.
Decision: Accept (poster)