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

arXiv: https://arxiv.org/abs/2603.02729 · HTML: https://mlsanity.com/paper/2603.02729/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2026.

## Built on by (most cited first, 2 of 2)

- [All-day Multi-scenes Lifelong Vision-and-Language Navigation with Tucker Adaptation](https://mlsanity.com/paper/2603.14276/) (2026)
- [Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing](https://mlsanity.com/paper/2609.37865/) (2026)

## Abstract (arXiv)

We study the problem of recovering a low-tubal-rank tensor X_star∈ ℝn × n × k from noisy linear measurements under the t-product framework. A widely adopted strategy involves factorizing the optimization variable as U * U^top, where U ∈ ℝn × R × k, followed by applying factorized gradient descent (FGD) to solve the resulting optimization problem. Since the tubal-rank r of the underlying tensor X_star is typically unknown, this method often assumes r < R ≤ 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.