A fast randomized algorithm for computing a hybrid CUR-type Tucker decomposition

The paper develops a fast randomized algorithm for computing a hybrid CUR-type decomposition of tensors in the Tucker representation. Specifically, to obtain the factor matrices, random sampling techniques are utilized to accelerate the procedure of constructing the classical matrix decompositions, that are, the interpolatory decomposition and singular value decomposition. Compared with the non-random algorithm, the proposed algorithm has advantages in speed with lower computational cost while keeping a high degree of accuracy. We establish a detailed probabilistic error analysis for the algorithm and provide numerical results that show the promise of our approach.