The power of small initialization in noisy low-tubal-rank tensor recovery

ZHiyu Liu; Haobo Geng; Xudong Wang; Yandong Tang; Zhi Han; Yao Wang

cs.LGMar 3, 2026

The power of small initialization in noisy low-tubal-rank tensor recovery

Authors: ZHiyu Liu, Haobo Geng, Xudong Wang, Yandong Tang, Zhi Han, Yao Wang

Organizations: State Key Laboratory of Robotics and Intelligent Systems, Shenyang Institute of Automation, Chinese Academy of Sciences, China · University of Chinese Academy of Sciences, China · School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore · The Center for Intelligent Decision-making and Machine Learning, School of Management, Xi’an Jiaotong University, China

Abstract

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

Figures & tables

Figure 1: Comparison of training and testing errors for Problem ( 1 ) using FGD with spectral vs. small initialization. The ground-truth tensor has tubal-rank $r=2$ , overestimated rank $R=4$ , size $n=20$ , $k=3$ , $m=5kr(2n-r)$ measurements, and noise $\sigma=10^{-3}$ . Spectral initialization follows Liu et al. (2024b) , while small initialization uses a near-zero starting point. Training error is $\frac{1}{4m}||\bm{y}-\bm{\mathfrak{M}}(\bm{\mathcal{U}}*\bm{\mathcal{U}}^{\top})||^{2}$ , and testing error is $||\bm{\mathcal{U}}*\bm{\mathcal{U}}^{\top}-\bm{\mathcal{X}}_{\star}||_{F}^{2}/||\bm{\mathcal{X}}_{\star}||_{F}^{2}$ . “Baseline” denotes recovery under exact rank $R=r$ . Insets show early (first 500 iterations) vs. full error curves.

methods	rate	guarantee	error
( Zhang et al., 2020 )	✗	✓	✗
( Liu et al., 2024b )	sub- linear	local	$\widetilde{\mathcal{O}}\left(\frac{nkR\sigma^{2}}{m}\right)$
( Karnik et al., 2025 )	linear	global	✗
Ours	linear	global	$\widetilde{\mathcal{O}}\left(\frac{nkr\sigma^{2}}{m}\right)$

Table 1: Comparison of several low-tubal-rank tensor recovery methods based on t-SVD. The noise vector

\bm{s}

is assumed to consist of Gaussian random variables with zero mean and variance

\sigma^{2}

Panel of Figure 2 — Figure 2: Performance comparison under varying $r$ , $\sigma$ , $n$ , and $m$ . Subfigure (a) illustrates the recovery error of all methods under different over-rank values $R$ , with parameters set as $m=10nrk$ , $n=30$ , $\sigma=10^{-3}$ , $\eta=0.1$ , and $T=5000$ . Subfigure (b) illustrates the error under varying noise levels $\sigma$ , with $m=10nrk$ , $n=30$ , $R=3r$ , $\eta=0.1$ , and $T=5000$ . Subfigure (c) illustrates the error as the problem dimension $n$ changes, where $m=10nrk$ , $R=3r$ , $\eta=0.1$ , $T=20000$ , and $\sigma=10^{-3}$ . Subfigure (d) illustrates the performance under different numbers of measurements $C_{m}$ , with $m=2C_{m}nrk$ , $n=30$ , $R=3r$ , $\eta=0.01$ , $T=20000$ , and $\sigma=10^{-3}$ .

Panel of Figure 3 — Figure 3: Validation of the algorithm with $m=10nrk$ , $R=3r$ , $n=30$ , $\sigma=10^{-3}$ , $\eta=0.1$ . (a) Validation loss vs. RSE, with the blue dot marking the minimum. (b) Error of the validation-based method compared with the minimum errors of baseline and small-initialization under varying $m_{\text{train}}$ .

Figure 4: Validation of the sensitivity of FGD to different tubal-ranks.

Methods	$p=0.2$				$p=0.3$
	$\sigma=0.07$		$\sigma=0.1$		$\sigma=0.07$		$\sigma=0.1$
	PSNR $\uparrow$	RE $\downarrow$	PSNR $\uparrow$	RE $\downarrow$	PSNR $\uparrow$	RE $\downarrow$	PSNR $\uparrow$	RE $\downarrow$
TCTF	16.5892	0.3175	16.5484	0.3191	20.6744	0.2008	20.6335	0.2024
TNN	21.2692	0.1851	19.7672	0.2188	22.0592	0.1681	20.1682	0.2082
TC-RE	20.9288	0.1921	19.5480	0.2242	21.5387	0.1782	19.8376	0.2161
UTF	16.3227	0.3243	14.8770	0.3802	19.2245	0.2355	17.8283	0.2734

Table 2: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels. “FGD-ES” denotes FGD with early stopping, while “FGD-best” refers to the minimum error achieved by FGD over all iterations. We write GTNN-HOP 0.3 as GTNN for short.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

\bar{\mathbf{X}}^{(i)}=\begin{cases}\bar{\mathbf{Y}}^{(i)}\,\bar{\mathbf{Z}}^{(i)},&i=1,\dots,\left\lceil\dfrac{n_{3}+1}{2}\right\rceil,\\[4.0pt] \operatorname{conj}\!\big(\bar{\mathbf{X}}^{(n_{3}-i+2)}\big),&i=\left\lceil\dfrac{n_{3}+1}{2}\right\rceil+1,\dots,n_{3}.\end{cases}

Appendix

Algorithm 1 Tensor-Tensor Product

Panel of Figure 5 — Figure 5: Validation of the four-phase convergence analysis in Section 3.3. The left panel shows the first 1,000 iterations; the right panel shows the full 10,000 iterations. The orange curve corresponds to the orange axis on the right, and the blue curve corresponds to the blue axis on the left. Parameter settings: $n=10$ , $k=3$ , $r=2$ , $R=10$ , $m=5knR$ , $\eta=0.1$ , noise standard deviation $\sigma=0.01$ , and initialization scale $\alpha=10^{-7}$ .

Figure 6: Comparison of training and testing errors for Problem ( 118 ) using FGD with spectral vs. small initialization. The ground-truth tensor has tubal-rank

r=2

, overestimated rank

R=4

, size

n_{1}=n_{2}=20

k=3

m=5kr(2n_{1}-r)

measurements, and noise

\sigma=10^{-3}

. Spectral initialization follows Liu et al. (2024b) , while small initialization uses a near-zero starting point. Training error is

\frac{1}{2}||\bm{y}-\bm{\mathfrak{M}}(\bm{\mathcal{L}}*\bm{\mathcal{R}}^{\top})||^{2}

, and testing error is

||\bm{\mathcal{L}}*\bm{\mathcal{R}}^{\top}-\bm{\mathcal{X}}_{\star}||_{F}^{2}/||\bm{\mathcal{X}}_{\star}||_{F}^{2}

. “Baseline” denotes recovery under exact rank

R=r

. Insets show early (first 500 iterations) vs. full error curves.

Panel of Figure 7 — Figure 7: Performance comparison under varying $R$ , $b$ with Laplace noise with $\mu=0$ . Subfigure (a) illustrates the recovery error of all methods under different over-rank values $R$ , with parameters set as $m=5kr(2n-r)$ , $n=30$ , $b=10^{-3}$ , $\eta=0.1$ , and $T=5000$ . Subfigure (b) illustrates the error under varying noise levels $b$ , with $m=5kr(2n-r)$ , $n=30$ , $R=3r$ , $\eta=0.1$ , and $T=5000$ .

Panel of Figure 8 — Figure 8: Performance comparison under varying $R$ , $\lambda$ with exponential noise. Subfigure (a) illustrates the recovery error of all methods under different over-rank values $R$ , with parameters set as $m=5kr(2n-r)$ , $n=30$ , $b=10^{-3}$ , $\eta=0.1$ , $\lambda=1000$ and $T=5000$ . Subfigure (b) illustrates the error under varying noise levels $\lambda$ , with $m=5kr(2n-r)$ , $n=30$ , $R=3r$ , $\eta=0.1$ , and $T=5000$ .

Panel of Figure 9 — Figure 9: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate $p=0.2$ and noise standard deviation $\sigma=0.07$ .

Panel of Figure 10 — Figure 10: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate $p=0.2$ and noise standard deviation $\sigma=0.1$ .

Panel of Figure 11 — Figure 11: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate $p=0.3$ and noise standard deviation $\sigma=0.07$ .

Panel of Figure 12 — Figure 12: Comparison of PSNR values and Relative Error across 50 images for different methods, with sampling rate $p=0.3$ and noise standard deviation $\sigma=0.1$ .

Figure 13: Comparison of the image recovery performance of different methods under varying sampling rate $p$ . The noise standard deviation $\sigma=0.05$ . And 5% of the observed entries are used for validation.

Methods	$p=0.3$				$p=0.4$
	$\sigma=0.03$		$\sigma=0.05$		$\sigma=0.03$		$\sigma=0.05$
	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$
UTF	7.8242	0.276	7.3535	0.2884	6.8286	0.3112	5.5376	0.3559
TNN	20.211	0.0659	17.2288	0.0934	20.4965	0.0639	17.1281	0.0947
TC-RE	19.7102	0.0698	16.9971	0.096	19.7435	0.0698	16.4039	0.1029
GTNN-HOP 0.3	19.6553	0.0706	16.1069	0.107	20.0091	0.068	16.268	0.1051

Appendix

Table 3: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels. A higher PSNR and smaller RE indicates better reconstruction quality.“FGD-ES” denotes FGD with early stopping, while “FGD-best” refers to the minimum error achieved by FGD over all iterations.

Methods	$p=0.3$				$p=0.4$
	$\sigma=0.03$		$\sigma=0.05$		$\sigma=0.03$		$\sigma=0.05$
	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$
TNN	20.7258	0.0613	17.4371	0.0895	21.0157	0.0592	17.3267	0.0906
TC-RE	19.928	0.0671	17.1895	0.0920	20.2059	0.0650	16.5464	0.0991
UTF	6.3467	0.3207	6.4038	0.3186	5.9414	0.3360	4.7523	0.3853
GTNN-HOP 0.3	19.9438	0.0670	16.1328	0.1039	20.2975	0.0643	16.2845	0.1021

Appendix

Table 4: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels. A higher PSNR and smaller RE indicates better reconstruction quality.“FGD-ES” denotes FGD with early stopping, while “FGD-best” refers to the minimum error achieved by FGD over all iterations.

Methods	$p=0.3$				$p=0.4$
	$\sigma=0.03$		$\sigma=0.05$		$\sigma=0.03$		$\sigma=0.05$
	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$
TNN	19.4802	0.0474	16.9433	0.0635	19.8369	0.0455	16.8423	0.0642
TC-RE	19.0227	0.0499	16.6549	0.0656	19.1568	0.0492	16.1336	0.0697
UTF	4.0060	0.2814	3.7117	0.2911	1.1904	0.3891	0.7714	0.4084
GTNN-HOP 0.3	19.3115	0.0483	16.1687	0.0694	19.7269	0.0461	16.3390	0.0680

Appendix

Table 5: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels for the “highway” video. A higher PSNR and smaller RE indicates better reconstruction quality. “FGD-ES” denotes FGD with early stopping, while “FGD-best” refers to the minimum error achieved by FGD over all iterations.

Methods	$p=0.3$				$p=0.4$
	$\sigma=0.03$		$\sigma=0.05$		$\sigma=0.03$		$\sigma=0.05$
	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$
TNN	19.3458	0.0717	16.6844	0.0974	19.8125	0.0679	16.7441	0.0967
TC-RE	19.2177	0.0728	16.5983	0.0984	19.2186	0.0728	16.0643	0.1046
UTF	11.4879	0.1772	10.2100	0.2053	10.8456	0.1908	8.6211	0.2465
GTNN-HOP 0.3	19.0898	0.0738	15.7370	0.1086	19.5613	0.0699	15.9544	0.1059

Appendix

Table 6: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels for the “suzie” video. A higher PSNR and smaller RE indicates better reconstruction quality. “FGD-ES” denotes FGD with early stopping, while “FGD-best” refers to the minimum error achieved by FGD over all iterations.

Methods	$p=0.3$				$p=0.4$
	$\sigma=0.03$		$\sigma=0.05$		$\sigma=0.03$		$\sigma=0.05$
	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$	PSNR $\uparrow$	RSE $\downarrow$
TNN	21.2922	0.0831	17.8503	0.1235	21.3210	0.0828	17.5991	0.1271
TC-RE	20.6724	0.0892	17.5455	0.1279	20.3926	0.0921	16.8711	0.1382
UTF	9.4560	0.3245	9.0886	0.3386	9.3371	0.3290	8.0055	0.3835
GTNN-HOP 0.3	20.2760	0.0934	16.3891	0.1461	20.4505	0.0915	16.4938	0.1443

Appendix

Table 7: Comparison of different methods in terms of average Peak Signal-to-Noise Ratio (PSNR) and average Relative Error (RE) under various sampling rates and noise levels for the “miss-america” video. A higher PSNR and smaller RE indicates better reconstruction quality. “FGD-ES” denotes FGD with early stopping, while “FGD-best” refers to the minimum error achieved by FGD over all iterations.

Figure 14: Comparison of the video recovery performance of different methods under varying sampling rate $p$ and noise standard deviation $\sigma$ for video ”akiyo”. For FGD-ES, 5% of the observed entries are used for validation.

Panel of Figure 15 — Figure 15: Evaluate the effect of different tubal-rank $R$ on the performance of video completion. Subfigure (a) shows the PSNR values of FGD-best on the four videos, and subfigure (b) shows the corresponding RE values. Subfigure (c) reports the PSNR values of FGD-ES on the four videos, while subfigure (d) presents the associated RE values.

Explore similar work

Sep 21, 2026

Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent

We consider the recovery of low-multilinear-rank tensors from linear measurements and propose an adaptive block-weighted modewise Riemannian gradient descent method. The method combines memory-efficient modewise measurements with a normalized adaptive weighting strategy for the core and factor components of the Riemannian gradient. The weighting improves convergence without increasing the multilinear-rank bound of the search direction or the size of the reduced core used for retraction. Under the tensor restricted isometry property and a suitable initialization, we establish local linear convergence and derive sampling guarantees for sub-Gaussian and subsampled orthogonal with random sign (SORS) measurements. Numerical experiments on synthetic low-Tucker-rank tensors show that the proposed method reduces iteration counts and computational time while maintaining reliable recovery performance, especially near the recovery threshold and for structured SORS measurements.

Yushi Zhou, Feng Zhang

School of Mathematics and Statistics, Southwest University, Chongqing, China.

Riemannian Optimization Tensor Decomposition

Ask PDF

Sep 29, 2026

Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing

We study the optimization landscape of low-tubal-rank tensor sensing through a balanced factorization. Under a tubal restricted isometry condition, we establish a quantitative strict-saddle landscape with no spurious local minima for arbitrary Fourier multi-rank profiles. We further show that the local geometry depends on the Fourier-slice ranks rather than the tubal rank alone. Uniform ranks yield quadratic growth transverse to the solution orbit, whereas nonuniform ranks produce quartically flat directions through hidden frequency-wise overparameterization, even when the factor width equals the exact tubal rank. Numerical experiments illustrate the global optimization behavior and the contrasting local geometries.

Eugene Agyei-Kodie, Longxiu Huang, Shuang Li +1

Department of Mathematics, Michigan State University, 619 Red Cedar, East Lansing, 48824, MI, USA. · Department of Computational Mathematics, Science and Engineering, Michigan State University, 428 S Shaw Ln, East Lansing, 48824, MI, USA. · Department of Electrical and Computer Engineering, Iowa State University, 2520 Osborn Dr, Ames, 50011, IA, USA.

Nonconvex Optimization Optimization Convergence Analysis Tensor Decomposition

Ask PDF

May 5, 2026

Low Rank Tensor Completion via Adaptive ADMM

We consider a novel algorithm, for the completion of partially observed low-rank tensors, as a generalization of matrix completion. The proposed low-rank tensor completion (TC) method builds on the conventional nuclear norm (NN) minimization-based low-rank TC paradigm, by leveraging the alternating direction method of multipliers (ADMM) optimization framework. To that extend the original NN minimization problem is reformulated into multiple subproblems, which are then solved iteratively via closed-form proximal operators, making use of over-relaxation and an adaptive penalty parameter update scheme, to further speed up convergence and improve the overall performance of the method. Simulation results demonstrate the superior performance of the new method in terms of normalized mean square error (NMSE), compared to the conventional state-of-the-art (SotA) techniques, including NN minimization approaches, as well as a mixture of the latter with a matrix factorization approach, while its convergence can be significantly improved by initializing the algorithm with the solution of the SotA.

Niclas Führling, Getuar Rexhepi, Giuseppe Thadeu Freitas de Abreu

School of Computer Science and Engineering, Constructor University, Bremen, Germany

Tensor Completion Nuclear Norm Minimization Alternating Direction Method of Multipliers Low-Rank Approximation

Ask PDF