A Two-Sided Sketching Algorithm for Low-rank Tensor Train Approximation
For practitioners needing fast tensor decomposition, this method reduces computational bottlenecks, but it is an incremental improvement over existing sketching-based approaches.
The authors propose a randomized algorithm for low-rank tensor train approximation using one-pass sketching and subspace iteration, achieving faster computation by avoiding large-scale SVD. Numerical experiments show effectiveness and efficiency on synthetic and real-world data.
Tensor train (TT) decomposition is a powerful method to acquire low-rank tensors. However, the computational process is frequently obstructed by the large-scale matrix singular value decomposition (SVD). The sketching algorithm serves as an efficient data compression technique that can quickly derive low-rank matrix approximations. In this paper, we propose a randomized algorithm to obtain the TT approximation of tensors using a one-pass sketching algorithm and subspace iteration, and offer thorough error-bound and robustness analysis. Numerical experiments on synthetic and real-world datasets demonstrate the effectiveness and efficiency of the proposed algorithm.