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.

翻译：本文提出了高效的算法，用于计算给定多线性秩的 Tucker 分解。通过结合随机投影和幂方法，我们提出了两个随机版本，用于截断高阶奇异值分解（T-HOSVD）和顺序 T-HOSVD（ST-HOSVD），这两个算法是用于逼近 Tucker 分解的常用算法。为了减少这两个算法的复杂度，我们将两个算法和近似矩阵乘法相结合，设计出快速和高效的算法。我们还根据标准高斯矩阵的奇异值界限和近似矩阵乘法的理论结果，得出了理论结果。最后，通过一些来自合成数据集和真实数据集的测试张量，说明了这些算法的效率。