A Randomized Block Krylov Method for Tensor Train Approximation

Tensor train decomposition is a powerful tool to tackle high-dimensional large-scale tensor data and is not suffering from the curse of dimensionality. It relies on performing the singular value decomposition (SVD) of auxiliary unfolding matrices. Some randomized algorithms have been proposed to accelerate the SVD calculation of the unfolding matrix, but they are not suitable for noisy data. This paper proposes a randomized algorithm for low-rank tensor train approximation of large-scale tensors based on randomized block Krylov subspace iteration and provides theoretical guarantees. Extensive numerical trials conducted on synthetic as well as real-world tensor data showcase the outstanding efficacy of the suggested algorithm, particularly when dealing with noisy data.