More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees
This work addresses computational bottlenecks in tensor decomposition for researchers and practitioners in machine learning and data analysis, offering a more efficient approach with theoretical guarantees.
The paper tackles the exponential per-iteration cost dependence on tensor modes in alternating least squares (ALS) methods for CP and tensor ring decomposition by proposing sampling-based ALS methods that eliminate this dependence, significantly improving efficiency over prior state-of-the-art.
Recent papers have developed alternating least squares (ALS) methods for CP and tensor ring decomposition with a per-iteration cost which is sublinear in the number of input tensor entries for low-rank decomposition. However, the per-iteration cost of these methods still has an exponential dependence on the number of tensor modes when parameters are chosen to achieve certain worst-case guarantees. In this paper, we propose sampling-based ALS methods for the CP and tensor ring decompositions whose cost does not have this exponential dependence, thereby significantly improving on the previous state-of-the-art. We provide a detailed theoretical analysis and also apply the methods in a feature extraction experiment.