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

Eugene Agyei-Kodie; Longxiu Huang; Shuang Li; Xiao Liang

cs.LGSep 29, 2026

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

Authors: Eugene Agyei-Kodie, Longxiu Huang, Shuang Li, Xiao Liang

Organizations: 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.

Abstract

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.

Figures & tables

Figure 1: Consistent near-exact recovery across 100 independent random initializations. The target is generated from two independent standard Gaussian factors of size

6\times 1\times 3

and normalized to unit Frobenius norm. We use

m=70

noiseless Gaussian measurements with sensing entries distributed as

\mathcal{N}(0,1/m)

. The target and sensing operator are fixed across all runs, while the initial factors are drawn independently from

\mathcal{N}(0,0.1^{2})

. Each run performs 5000 gradient-descent iterations with stepsize

0.05

. The left panel reports

-\log_{10}

of the final relative reconstruction error, and the right panel reports

-\log_{10}

of the final balanced objective value.

Figure 2: Benign global geometry of the balanced objective for a uniform rank-one ground truth with

n_{1}=n_{2}=4

n_{3}=3

, and

r=1

. The objective is evaluated on the slice

\mathcal{W}_{\mathrm{glob}}(\xi,\eta)=\xi\overline{\mathcal{W}}+\eta\|\overline{\mathcal{W}}\|_{F}\mathcal{D}_{\perp},

where

\xi

is the radial coordinate and

\eta

is a transverse normal coordinate. Left: Surface plot. Right: Contour plot. The stars at

(1,0)

and

(-1,0)

mark

\overline{\mathcal{W}}

and

-\overline{\mathcal{W}}

, two points of the positive-dimensional solution orbit

\mathcal{S}_{\star}

. The triangle at the origin marks the rank-deficient strict saddle.

Panel of Figure 3 — Figure 3: Multi-rank-dependent local geometry at a selected global minimizer $\overline{\mathcal{W}}$ , for two ground truths with equal tubal rank $r=2$ and dimensions $n_{1}=n_{2}=4$ , $n_{3}=3$ . (a) Uniform multi-rank, $\rho_{k}=r$ for every $k$ . (b) Nonuniform multi-rank with one deficient slice, $\rho_{k_{0}}<r$ . The horizontal and vertical axes in panels Left and Middle are the tangent and normal coordinates, respectively, and the star marks $\overline{\mathcal{W}}$ . Right: Log–log plot of $f(\overline{\mathcal{W}}+t\mathcal{D})$ along the selected normal direction. The uniform and deficient cases follow slopes close to $2$ and $4$ , respectively, illustrating the quadratic and quartic growth laws in Theorem 7 .

Figure 4: The first three panels show medians over ten balanced random starts, with error bars spanning the 25th to 75th percentiles. The dashed horizontal line is the rank-3 approximation floor of the untruncated target. The vertical line (DOF/N) at $r(n_{1}+n_{2}-r)n_{3}/N=0.4420$ is only a parameter-count reference, not a theoretical phase-transition threshold. The lower-right panel shows the percentage of successful starts for the exact-rank target.

Figure 5: Exact-rank OCT-derived target under normalized Gaussian sensing. Columns correspond to $m/N=20\%,\ldots,80\%$ . Rows show the target, the adjoint backprojection $\mathcal{M}^{*}(y)$ , and a representative reconstruction. The number above each reconstruction is that individual trial’s full-volume PSNR (in dB). For each measurement ratio, we select the trial whose full-volume relative recovery error is closest to the median over ten balanced random starts.

Figure 6: Rank-3 model mismatch for the untruncated preprocessed OCT tensor. The layout, representative-trial selection rule, and interpretation of the displayed PSNR values are the same as in Figure 5 . Increasing $m/N$ restores progressively more retinal structure, while a nonzero discrepancy remains because the reconstruction has tubal rank at most 3.

Explore similar work

The power of small initialization in noisy low-tubal-rank tensor recovery
Mar 3, 2026ZHiyu Liu, Haobo Geng, Xudong Wang +3Gradient Descent
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 +1
Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness
Oct 13, 2026Runze Shi, Ziye MaMatrix Factorization Low-Rank Matrix Decomposition
City University of Hong Kong
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.

Mar 3, 2026J/K move · Enter open · S save

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

ZHiyu Liu, Haobo Geng, Xudong Wang, Yandong Tang+2

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+1

Gradient Descent

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness

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