mlsanityData to 7 Oct 2026

Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery

arXiv 2401.02592 ↗First posted 5 Jan 2024stat.ML cs.LG eess.SPcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we provide the first convergence guarantee for the factorization approach. Specifically, to avoid the scaling ambiguity and to facilitate theoretical analysis, we optimize over the so-called left-orthogonal TT format which enforces orthonormality among most of the factors. To ensure the orthonormal structure, we utilize the Riemannian gradient descent (RGD) for optimizing those factors over the Stiefel manifold. We first delve into the TT factorization problem and establish the local linear convergence of RGD. Notably, the rate of convergence only experiences a linear decline as the tensor order increases. We then study the sensing problem that aims to recover a TT format tensor from linear measurements. Assuming the sensing operator satisfies the restricted isometry property (RIP), we show that with a proper initialization, which could be obtained through spectral initialization, RGD also converges to the ground-truth tensor at a linear rate. Furthermore, we expand our analysis to encompass scenarios involving Gaussian noise in the measurements. We prove that RGD can reliably recover the ground truth at a linear rate, with the recovery error exhibiting only polynomial growth in relation to the tensor order. We conduct various experiments to validate our theoretical findings.

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

Builds on

38 of 85 references.

References · 38

  1. 2017How to Escape Saddle Points Efficientlycited by 284
  2. 2015Tensorizing Neural Networkscited by 246
  3. 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
  4. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2019A Tensorized Transformer for Language Modelingcited by 85
  7. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  8. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  9. 2016Efficient tensor completion for color image and video recovery: Low-rank tensor traincited by 61
  10. 2017Tensor-Train Recurrent Neural Networks for Video Classificationcited by 59
  11. 2018Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completioncited by 42
  12. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
26 more
  1. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  2. 2017Global Optimality in Low-rank Matrix Optimizationcited by 35
  3. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  4. 2017Long-term Forecasting using Higher Order Tensor RNNscited by 34
  5. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  6. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  7. 2017Expressive power of recurrent neural networkscited by 30
  8. 2021Tensor-Train Density Estimationcited by 30
  9. 2017Compressing Recurrent Neural Network with Tensor Traincited by 28
  10. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  11. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  12. 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
  13. 2016Tensor Methods and Recommender Systemscited by 24
  14. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 24
  15. 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
  16. 2015Parsimonious Tensor Response Regressioncited by 20
  17. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  18. 2018High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Formatcited by 12
  19. 2018Sparse and Low-rank Tensor Estimation via Cubic Sketchingscited by 11
  20. 2022Exploiting Low-Rank Tensor-Train Deep Neural Networks Based on Riemannian Gradient Descent With Illustrations of Speech Processingcited by 10
  21. 2016Tensor Completion by Alternating Minimization under the Tensor Train (TT) Modelcited by 9
  22. 2019Iterative Hard Thresholding for Low CP-rank Tensor Modelscited by 9
  23. 2023Quantum State Tomography for Matrix Product Density Operatorscited by 9
  24. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  25. 2020The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularizationcited by 7
  26. 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  2. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  3. 2024Robust Low-rank Tensor Train Recoverycited by 2
  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. 2026StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensingcited by 0
  7. 2026Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computationcited by 0
  8. 2026Structured Adaptive Tensor Prediction for Streaming Datacited by 0