# Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 74 references that are in the map.
- First posted on arXiv 8 Dec 2025.

## Builds on (most cited first, 30 of 32)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm](https://mlsanity.com/paper/1804.03728/) (2018)
- [Exact tensor completion using t-SVD](https://mlsanity.com/paper/1502.04689/) (2015)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Tensor Methods and Recommender Systems](https://mlsanity.com/paper/1603.06038/) (2016)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Multi-dimensional imaging data recovery via minimizing the partial sum of tubal nuclear norm](https://mlsanity.com/paper/1712.05870/) (2017)
- [Low-tubal-rank Tensor Completion using Alternating Minimization](https://mlsanity.com/paper/1610.01690/) (2016)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements](https://mlsanity.com/paper/1806.02511/) (2018)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Nonconvex Matrix Factorization from Rank-One Measurements](https://mlsanity.com/paper/1802.06286/) (2018)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Robust Low-tubal-rank Tensor Completion based on Tensor Factorization and Maximum Correntopy Criterion](https://mlsanity.com/paper/2010.11740/) (2020)
- [Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition](https://mlsanity.com/paper/2406.06002/) (2024)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Tensor Restricted Isometry Property Analysis For a Large Class of Random Measurement Ensembles](https://mlsanity.com/paper/1906.01198/) (2019)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Implicit Regularization for Tubal Tensor Factorizations via Gradient Descent](https://mlsanity.com/paper/2410.16247/) (2024)
- [Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2501.01696/) (2025)
- [Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCA](https://mlsanity.com/paper/2501.04565/) (2025)
- [A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation](https://mlsanity.com/paper/2305.11458/) (2023)

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

- [Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing](https://mlsanity.com/paper/2609.37865/) (2026)

## Abstract (arXiv)

The problem of low-tubal-rank tensor estimation is a fundamental task with wide applications across high-dimensional signal processing, machine learning, and image science. Traditional approaches tackle such a problem by performing tensor singular value decomposition, which is computationally expensive and becomes infeasible for large-scale tensors. Recent approaches address this issue by factorizing the tensor into two smaller factor tensors and solving the resulting problem using gradient descent. However, this kind of approach requires an accurate estimate of the tensor rank, and when the rank is overestimated, the convergence of gradient descent and its variants slows down significantly or even diverges. To address this problem, we propose an Alternating Preconditioned Gradient Descent (APGD) algorithm, which accelerates convergence in the over-parameterized setting by adding a preconditioning term to the original gradient and updating these two factors alternately. Based on certain geometric assumptions on the objective function, we establish linear convergence guarantees for more general low-tubal-rank tensor estimation problems. Then we further analyze the specific cases of low-tubal-rank tensor factorization and low-tubal-rank tensor recovery. Our theoretical results show that APGD achieves linear convergence even under over-parameterization, and the convergence rate is independent of the tensor condition number. Extensive simulations on synthetic data are carried out to validate our theoretical assertions.