Search papers, labs, and topics across Lattice.
This paper investigates low-tubal-rank tensor recovery from noisy linear measurements using factorized gradient descent (FGD) under the t-product framework. It demonstrates that, in contrast to spectral initialization which leads to error scaling with the over-estimated tubal-rank $R$, using a small initialization with FGD achieves near-minimax optimal recovery error independent of $R$. The authors provide a four-stage analysis and early stopping strategy to achieve this improved performance, validating their theoretical results with simulations and real-data experiments.
Small initializations can rescue factorized gradient descent from the curse of overparameterization in noisy tensor completion, achieving near-optimal recovery where spectral initialization fails.
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.
