Efficient Randomized Algorithms for Computing an Approximation of the Tensor Train Decomposition

In this paper, we focus on the fixed-TT-rank and the fixed-precision problems of finding an approximation of the tensor train (TT) decomposition of a tensor. Note that the TT-SVD and TT-cross are two well-known algorithms for these two problems. Firstly, by combining the random projection technique with the power scheme, we obtain two types of randomized algorithms for the fixed-TT-rank problem. Secondly, by using the non-asymptotic theory of sub-Gaussian random matrices, we derive the upper bounds of the proposed randomized algorithms. Thirdly, we deduce a new deterministic strategy to estimate the desired TT-rank with a given tolerance and another adaptive randomized algorithm that finds a low TT-rank representation satisfying a given tolerance, and is beneficial when the target TT-rank is not known in advance. We finally illustrate the accuracy of the proposed algorithms via some test tensors from synthetic and real databases. In particular, for the fixed-TT-rank problem, the proposed algorithms can be several times faster than the TT-SVD, and the accuracy of the proposed algorithms and the TT-SVD are comparable for several test tensors. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2026.