mlsanityData to 14 Oct 2026

Provable Tensor-Train Format Tensor Completion by Riemannian Optimization

arXiv 2108.12163 ↗First posted 27 Aug 2021cs.LG cs.IT math.ITcited by 17

Not on the map. Why?

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.

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

34 of 74 references.

References · 34

  1. 2016Efficient tensor completion for color image and video recovery: Low-rank tensor traincited by 61
  2. 2017Tensor SVD: Statistical and Computational Limitscited by 53
  3. 2017Tensor Completion Algorithms in Big Data Analyticscited by 48
  4. 2019Inference and Uncertainty Quantification for Noisy Matrix Completioncited by 39
  5. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
  6. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  7. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  8. 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
  9. 2014Provable Tensor Factorization with Missing Datacited by 31
  10. 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 30
  11. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  12. 2016Spectral algorithms for tensor completioncited by 27
22 more
  1. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  2. 2021Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimizationcited by 24
  3. 2017Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entriescited by 23
  4. 2013Tensor-based formulation and nuclear norm regularization for multi-energy computed tomographycited by 22
  5. 2016Guarantees of Riemannian Optimization for Low Rank Matrix Completioncited by 19
  6. 2019Statistical Inferences of Linear Forms for Noisy Matrix Completioncited by 18
  7. 2015Structured Matrix Completion with Applications to Genomic Data Integrationcited by 17
  8. 2015Provable Sparse Tensor Decompositioncited by 16
  9. 2017Multilayer tensor factorization with applications to recommender systemscited by 16
  10. 2020Tensor Completion Made Practicalcited by 15
  11. 2017Exact tensor completion with sum-of-squarescited by 14
  12. 2018Fast and Accurate Tensor Completion with Total Variation Regularized Tensor Trainscited by 14
  13. 2020Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimalitycited by 13
  14. 2018High-dimension Tensor Completion via Gradient-based Optimization Under Tensor-train Formatcited by 12
  15. 2020Optimal High-order Tensor SVD via Tensor-Train Orthogonal Iterationcited by 11
  16. 2016Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completioncited by 10
  17. 2016Cross: Efficient Low-rank Tensor Completioncited by 10
  18. 2016Tensor Completion by Alternating Minimization under the Tensor Train (TT) Modelcited by 9
  19. 2015Optimal Estimation of Low Rank Density Matricescited by 6
  20. 2017On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithmcited by 4
  21. 2021Covariate-assisted Sparse Tensor Completioncited by 4
  22. 2016Estimation of low rank density matrices: bounds in Schatten norms and other distancescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 3; 2024: 4; 2025: 6; 2026: 2.

17 papers.

Sort:

  1. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  2. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  3. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  4. 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6
  5. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  6. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  7. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  8. 2026Low-Rank Adaptation Redux for Large Modelscited by 3
  9. 2024Robust Low-rank Tensor Train Recoverycited by 2
  10. 2024Tensor Methods in High Dimensional Data Analysis: Opportunities and Challengescited by 1
  11. 2025Fourier Low-rank and Sparse Tensor for Efficient Tensor Completioncited by 1
  12. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
5 more
  1. 2023Optical Coherence Tomography Image Enhancement via Block Hankelization and Low Rank Tensor Network Approximationcited by 0
  2. 2025Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descentcited by 0
  3. 2025Accelerating Large-Scale Regularized High-Order Tensor Recoverycited by 0
  4. 2025Efficient Tensor Completion Algorithms for Highly Oscillatory Operatorscited by 0
  5. 2026Tensor Completion using Subspace Informationcited by 0