Combinatorics

Tensor (intrinsic definition)

Filtered algebra

Pure mathematics

Mathematics

Multilinear algebra

Multilinear map

Algorithm

Randomized algorithm

Algebra over a field

Rank (graph theory)

Division algebra

Computer science

Computation

Advances in Computational Mathematics

Randomized algorithms provide a powerful tool for scientific computing. Compared with standard deterministic algorithms, randomized algorithms are often faster and robust. The main purpose of this paper is to design adaptive randomized algorithms for computing the approximate tensor decompositions. We give an adaptive randomized algorithm for the computation of a low multilinear rank approximation of the tensors with unknown multilinear rank and analyze its probabilistic error bound under certain assumptions. Finally, we design an adaptive randomized algorithm for computing the tensor train approximations of the tensors. Based on the bounds about the singular values of sub-Gaussian matrices with independent columns or independent rows, we analyze these randomized algorithms. We illustrate our adaptive randomized algorithms via several numerical examples.

Randomized algorithms for the approximations of Tucker and the tensor train decompositions