mlsanityData to 7 Oct 2026

Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent

arXiv 2401.11940 ↗First posted 22 Jan 2024cs.LG math.OC stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

This paper considers the problem of recovering a tensor with an underlying low-tubal-rank structure from a small number of corrupted linear measurements. Traditional approaches tackling such a problem require the computation of tensor Singular Value Decomposition (t-SVD), that is a computationally intensive process, rendering them impractical for dealing with large-scale tensors. Aim to address this challenge, we propose an efficient and effective low-tubal-rank tensor recovery method based on a factorization procedure akin to the Burer-Monteiro (BM) method. Precisely, our fundamental approach involves decomposing a large tensor into two smaller factor tensors, followed by solving the problem through factorized gradient descent (FGD). This strategy eliminates the need for t-SVD computation, thereby reducing computational costs and storage requirements. We provide rigorous theoretical analysis to ensure the convergence of FGD under both noise-free and noisy situations. Additionally, it is worth noting that our method does not require the precise estimation of the tensor tubal-rank. Even in cases where the tubal-rank is slightly overestimated, our approach continues to demonstrate robust performance. A series of experiments have been carried out to demonstrate that, as compared to other popular ones, our approach exhibits superior performance in multiple scenarios, in terms of the faster computational speed and the smaller convergence error.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 42 of its 73 references that are in the map. First posted on arXiv 22 Jan 2024.

Builds on

42 of 73 references.

References · 42

  1. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
  2. 2016Tensor Ring Decompositioncited by 125
  3. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  4. 2018Tensor Robust Principal Component Analysis with A New Tensor Nuclear Normcited by 110
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  7. 2015Exact tensor completion using t-SVDcited by 70
  8. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  9. 2016Efficient tensor completion for color image and video recovery: Low-rank tensor traincited by 61
  10. 2017Tensor SVD: Statistical and Computational Limitscited by 52
  11. 2023Guaranteed Tensor Recovery Fused Low-rankness and Smoothnesscited by 41
  12. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
30 more
  1. 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
  2. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  3. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  4. 2014Provable Tensor Factorization with Missing Datacited by 31
  5. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  6. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  7. 2016Spectral algorithms for tensor completioncited by 27
  8. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  9. 2021Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimizationcited by 24
  10. 2017Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entriescited by 23
  11. 2013Tensor-based formulation and nuclear norm regularization for multi-energy computed tomographycited by 22
  12. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  13. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  14. 2017Multi-dimensional imaging data recovery via minimizing the partial sum of tubal nuclear normcited by 19
  15. 2022Exact Decomposition of Joint Low Rankness and Local Smoothness Plus Sparse Matricescited by 19
  16. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  17. 2018Exact Low Tubal Rank Tensor Recovery from Gaussian Measurementscited by 16
  18. 2020Tensor Completion Made Practicalcited by 15
  19. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  20. 2015Total Variation Regularized Tensor RPCA for Background Subtraction from Compressive Measurementscited by 14
  21. 2017Exact tensor completion with sum-of-squarescited by 14
  22. 2020Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimalitycited by 13
  23. 2017Near-optimal sample complexity for convex tensor completioncited by 9
  24. 2021Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completioncited by 9
  25. 2021Effective Tensor Completion via Element-wise Weighted Low-rank Tensor Train with Overlapping Ket Augmentationcited by 8
  26. 2020Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVDcited by 6
  27. 2019Tensor Restricted Isometry Property Analysis For a Large Class of Random Measurement Ensemblescited by 3
  28. 2022Tensor Completion via Tensor Train Based Low-Rank Quotient Geometry under a Preconditioned Metriccited by 3
  29. 2023Riemannian preconditioned algorithms for tensor completion via tensor ring decompositioncited by 3
  30. 2020T-positive semidefiniteness of third-order symmetric tensors and T-semidefinite programmingcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 3.

7 papers.

  1. 2025Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCAcited by 2
  2. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  3. 2024Non-Convex Tensor Recovery from Local Measurementscited by 1
  4. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  5. 2025Accelerating Large-Scale Regularized High-Order Tensor Recoverycited by 0
  6. 2026Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computationcited by 0
  7. 2026Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensingcited by 0