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

doi:10.1007/s10915-026-03208-9

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

2026-02-18

0

PRE

AI

DOI：10.1007/s10915-026-03208-9

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Tensor train decomposition

Fixed-TT-rank problem

Fixed-precision problem

TT-SVD

Sub-Gaussian random matrices

Randomized algorithms

The Khatri-Rao product

The power scheme

Facial image analysis

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

Abstract

Journal

Organization