Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
32 of 74 references.
References · 32
- 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 224
- 2016Tensor Ring Decompositioncited by 127
- 2018Tensor Robust Principal Component Analysis with A New Tensor Nuclear Normcited by 112
- 2015Exact tensor completion using t-SVDcited by 70
- 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 45
- 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
- 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
- 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
- 2016Tensor Methods and Recommender Systemscited by 24
- 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
- 2017Multi-dimensional imaging data recovery via minimizing the partial sum of tubal nuclear normcited by 19
- 2016Low-tubal-rank Tensor Completion using Alternating Minimizationcited by 18
20 more
- 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
- 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
- 2018Exact Low Tubal Rank Tensor Recovery from Gaussian Measurementscited by 16
- 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
- 2018Nonconvex Matrix Factorization from Rank-One Measurementscited by 13
- 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
- 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
- 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
- 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
- 2020Robust Low-tubal-rank Tensor Completion based on Tensor Factorization and Maximum Correntopy Criterioncited by 6
- 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
- 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
- 2019Tensor Restricted Isometry Property Analysis For a Large Class of Random Measurement Ensemblescited by 3
- 2024Robust Low-rank Tensor Train Recoverycited by 2
- 2024Implicit Regularization for Tubal Tensor Factorizations via Gradient Descentcited by 2
- 2025Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descentcited by 2
- 2025Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCAcited by 2
- 2023A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimationcited by 1
- 2024Non-Convex Tensor Recovery from Local Measurementscited by 1
- 2025Preconditioned subgradient method for composite optimization: overparameterization and fast convergencecited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.