A Randomized Algorithm for Tensor Singular Value Decomposition Using an Arbitrary Number of Passes

Computation of a tensor singular value decomposition (t-SVD) with a few number of passes over the underlying data tensor is crucial in using modern computer architectures, where the main concern is the communication cost. The current subspace randomized algorithms for computation of the t-SVD, needs 2q + 2 number of passes over the data tensor where q is an non-negative integer number (power iteration parameter). In this paper, we propose a new and flexible randomized algorithm which works for any number of passes q, not necessarily being an even number. It is a generalization of the methods developed for matrices to tensors. The expected error bound of the proposed algorithm is derived. Several numerical experiments are conducted and the results confirmed that the proposed algorithm is efficient and applicable. We also use our proposed method to develop a fast algorithm for tensor completion problem.