# Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery arXiv: https://arxiv.org/abs/2401.02592 ยท HTML: https://mlsanity.com/paper/2401.02592/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 38 of its 85 references that are in the map. - First posted on arXiv 5 Jan 2024. ## Builds on (most cited first, 30 of 38) - [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017) - [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015) - [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016) - [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014) - [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015) - [A Tensorized Transformer for Language Modeling](https://mlsanity.com/paper/1906.09777/) (2019) - [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021) - [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020) - [Efficient tensor completion for color image and video recovery: Low-rank tensor train](https://mlsanity.com/paper/1606.01500/) (2016) - [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017) - [Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completion](https://mlsanity.com/paper/1809.02288/) (2018) - [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020) - [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016) - [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017) - [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019) - [Long-term Forecasting using Higher Order Tensor RNNs](https://mlsanity.com/paper/1711.00073/) (2017) - [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022) - [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023) - [Expressive power of recurrent neural networks](https://mlsanity.com/paper/1711.00811/) (2017) - [Tensor-Train Density Estimation](https://mlsanity.com/paper/2108.00089/) (2021) - [Compressing Recurrent Neural Network with Tensor Train](https://mlsanity.com/paper/1705.08052/) (2017) - [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021) - [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017) - [Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation](https://mlsanity.com/paper/1702.06435/) (2017) - [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017) - [Tensor Methods and Recommender Systems](https://mlsanity.com/paper/1603.06038/) (2016) - [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016) - [Parsimonious Tensor Response Regression](https://mlsanity.com/paper/1501.07815/) (2015) - [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021) - [High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Format](https://mlsanity.com/paper/1804.01983/) (2018) ## Built on by (most cited first, 8 of 8) - [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) - [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024) - [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025) - [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025) - [StoTAM: Stochastic Alternating Minimization for Tucker-Structured Tensor Sensing](https://mlsanity.com/paper/2601.13522/) (2026) - [Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computation](https://mlsanity.com/paper/2602.12982/) (2026) - [Structured Adaptive Tensor Prediction for Streaming Data](https://mlsanity.com/paper/2606.10085/) (2026) ## 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.