# Provable Tensor-Train Format Tensor Completion by Riemannian Optimization arXiv: https://arxiv.org/abs/2108.12163 ยท HTML: https://mlsanity.com/paper/2108.12163/ ## Key facts - Cited by 17 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 74 references that are in the map. - First posted on arXiv 27 Aug 2021. ## Builds on (most cited first, 30 of 34) - [Efficient tensor completion for color image and video recovery: Low-rank tensor train](https://mlsanity.com/paper/1606.01500/) (2016) - [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017) - [Tensor Completion Algorithms in Big Data Analytics](https://mlsanity.com/paper/1711.10105/) (2017) - [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019) - [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020) - [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018) - [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019) - [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014) - [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014) - [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020) - [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021) - [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016) - [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017) - [Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization](https://mlsanity.com/paper/2103.08895/) (2021) - [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017) - [Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography](https://mlsanity.com/paper/1307.5348/) (2013) - [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016) - [Statistical Inferences of Linear Forms for Noisy Matrix Completion](https://mlsanity.com/paper/1909.00116/) (2019) - [Structured Matrix Completion with Applications to Genomic Data Integration](https://mlsanity.com/paper/1504.01823/) (2015) - [Provable Sparse Tensor Decomposition](https://mlsanity.com/paper/1502.01425/) (2015) - [Multilayer tensor factorization with applications to recommender systems](https://mlsanity.com/paper/1711.01598/) (2017) - [Tensor Completion Made Practical](https://mlsanity.com/paper/2006.03134/) (2020) - [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017) - [Fast and Accurate Tensor Completion with Total Variation Regularized Tensor Trains](https://mlsanity.com/paper/1804.06128/) (2018) - [Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality](https://mlsanity.com/paper/2006.08580/) (2020) - [High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Format](https://mlsanity.com/paper/1804.01983/) (2018) - [Optimal High-order Tensor SVD via Tensor-Train Orthogonal Iteration](https://mlsanity.com/paper/2010.02482/) (2020) - [Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion](https://mlsanity.com/paper/1606.03504/) (2016) - [Cross: Efficient Low-rank Tensor Completion](https://mlsanity.com/paper/1611.01129/) (2016) - [Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model](https://mlsanity.com/paper/1609.05587/) (2016) ## Built on by (most cited first, 17 of 17) - [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022) - [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024) - [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023) - [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (2021) - [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023) - [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) - [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026) - [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024) - [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024) - [Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion](https://mlsanity.com/paper/2505.11261/) (2025) - [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025) - [Optical Coherence Tomography Image Enhancement via Block Hankelization and Low Rank Tensor Network Approximation](https://mlsanity.com/paper/2306.11750/) (2023) - [Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descent](https://mlsanity.com/paper/2501.13385/) (2025) - [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025) - [Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://mlsanity.com/paper/2510.17734/) (2025) - [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026) ## Abstract (arXiv) The tensor train (TT) format enjoys appealing advantages in handling structural high-order tensors. The recent decade has witnessed the wide applications of TT-format tensors from diverse disciplines, among which tensor completion has drawn considerable attention. Numerous fast algorithms, including the Riemannian gradient descent (RGrad), have been proposed for the TT-format tensor completion. However, the theoretical guarantees of these algorithms are largely missing or sub-optimal, partly due to the complicated and recursive algebraic operations in TT-format decomposition. Moreover, existing results established for the tensors of other formats, for example, Tucker and CP, are inapplicable because the algorithms treating TT-format tensors are substantially different and more involved. In this paper, we provide, to our best knowledge, the first theoretical guarantees of the convergence of RGrad algorithm for TT-format tensor completion, under a nearly optimal sample size condition. The RGrad algorithm converges linearly with a constant contraction rate that is free of tensor condition number without the necessity of re-conditioning. We also propose a novel approach, referred to as the sequential second-order moment method, to attain a warm initialization under a similar sample size requirement. As a byproduct, our result even significantly refines the prior investigation of RGrad algorithm for matrix completion. Lastly, statistically (near) optimal rate is derived for RGrad algorithm if the observed entries consist of random sub-Gaussian noise. Numerical experiments confirm our theoretical discovery and showcase the computational speedup gained by the TT-format decomposition.