Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
This work provides a significant acceleration for the core tensor update in Tucker decomposition, which is a critical bottleneck for researchers and practitioners working with large, high-dimensional tensor data.
This paper addresses the computational bottleneck in the core tensor update step of the alternating least squares (ALS) algorithm for low-rank Tucker decomposition. By employing approximate ridge leverage scores, the authors construct a sketched ridge regression problem whose solution approximates the original, enabling sublinear time complexity for the core tensor update.
Low-rank tensor decomposition generalizes low-rank matrix approximation and is a powerful technique for discovering low-dimensional structure in high-dimensional data. In this paper, we study Tucker decompositions and use tools from randomized numerical linear algebra called ridge leverage scores to accelerate the core tensor update step in the widely-used alternating least squares (ALS) algorithm. Updating the core tensor, a severe bottleneck in ALS, is a highly-structured ridge regression problem where the design matrix is a Kronecker product of the factor matrices. We show how to use approximate ridge leverage scores to construct a sketched instance for any ridge regression problem such that the solution vector for the sketched problem is a $(1+\varepsilon)$-approximation to the original instance. Moreover, we show that classical leverage scores suffice as an approximation, which then allows us to exploit the Kronecker structure and update the core tensor in time that depends predominantly on the rank and the sketching parameters (i.e., sublinear in the size of the input tensor). We also give upper bounds for ridge leverage scores as rows are removed from the design matrix (e.g., if the tensor has missing entries), and we demonstrate the effectiveness of our approximate ridge regressioni algorithm for large, low-rank Tucker decompositions on both synthetic and real-world data.