Faster TKD: Towards Lightweight Decomposition for Large-Scale Tensors with Randomized Block Sampling

The Tucker Decomposition (TKD) is able to provide the low-dimensional and informative representations of real-world large-scale tensorial data, which are necessary to extract potential features and enhance the original data. However, computing such decomposition directly for a dense tensor is usually computationally elusive, due to the repetitive operations of computing large-scale tensor-matrix product. Instead of direct decomposition, this paper proposes an efficient algorithm for seeking the Faster TKD of the large-scale tensor, which is a lightweight decomposition approach based on the technique of randomized sampling. The proposed
algorithm first converts the original large-scale tensor into a small-scale subtensor via full-mode sampling operation, and then the core tensor of TKD can be computed directly based on the subtensor with low complexity. Finally, an approximate TKD of the original large-scale tensor can be obtained after sequentially computing approximate full-mode factor matrices. A theoretical error analysis is provided to show that the approximation error approximates zero with high probability, and the proposed algorithm is verified based on real tensorial data of 23821.24GB.