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

Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent
Sep 21, 2026Yushi Zhou, Feng ZhangRiemannian Optimization Tensor Decomposition
School of Mathematics and Statistics, Southwest University, Chongqing, China.
Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing
Sep 29, 2026Eugene Agyei-Kodie, Longxiu Huang, Shuang Li +1Nonconvex Optimization Optimization Convergence Analysis
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.
Low Rank Tensor Completion via Adaptive ADMM
May 5, 2026Niclas Führling, Getuar Rexhepi, Giuseppe Thadeu Freitas de AbreuTensor Completion Nuclear Norm Minimization
School of Computer Science and Engineering, Constructor University, Bremen, Germany

Sep 21, 2026J/K move · Enter open · S save

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

Yushi Zhou, Feng Zhang

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

Riemannian Optimization Tensor Decomposition

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

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

Low Rank Tensor Completion via Adaptive ADMM