# On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm

arXiv: https://arxiv.org/abs/1708.00132 · HTML: https://mlsanity.com/paper/1708.00132/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2017.

## Built on by (most cited first, 4 of 4)

- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Lower and Upper Bounds on the VC-Dimension of Tensor Network Models](https://mlsanity.com/paper/2106.11827/) (2021)
- [Coarse to Fine: Image Restoration Boosted by Multi-Scale Low-Rank Tensor Completion](https://mlsanity.com/paper/2203.15189/) (2022)
- [Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descent](https://mlsanity.com/paper/2501.13385/) (2025)

## Abstract (arXiv)

Tensor train (TT) decomposition provides a space-efficient representation for higher-order tensors. Despite its advantage, we face two crucial limitations when we apply the TT decomposition to machine learning problems: the lack of statistical theory and of scalable algorithms. In this paper, we address the limitations. First, we introduce a convex relaxation of the TT decomposition problem and derive its error bound for the tensor completion task. Next, we develop an alternating optimization method with a randomization technique, in which the time complexity is as efficient as the space complexity is. In experiments, we numerically confirm the derived bounds and empirically demonstrate the performance of our method with a real higher-order tensor.