A Randomized Tensor Train Singular Value Decomposition

The hierarchical SVD provides a quasi-best low-rank approximation of high-dimensional data in the hierarchical Tucker framework. Similar to the SVD for matrices, it provides a fundamental but expensive tool for tensor computations. In the present work, we examine generalizations of randomized matrix decomposition methods to higher-order tensors in the framework of the hierarchical tensor representation. In particular we present and analyze a randomized algorithm for the calculation of the hierarchical SVD (HSVD) for the tensor train (TT) format.