  This paper develops fast and efficient algorithms for computing Tucker
decomposition with a given multilinear rank. By combining random projection and
the power scheme, we propose two efficient randomized versions for the
truncated high-order singular value decomposition (T-HOSVD) and the
sequentially T-HOSVD (ST-HOSVD), which are two common algorithms for
approximating Tucker decomposition. To reduce the complexities of these two
algorithms, fast and efficient algorithms are designed by combining two
algorithms and approximate matrix multiplication. The theoretical results are
also achieved based on the bounds of singular values of standard Gaussian
matrices and the theoretical results for approximate matrix multiplication.
Finally, the efficiency of these algorithms are illustrated via some test
tensors from synthetic and real datasets.
