A Sampling-Based Method for Tensor Ring Decomposition
arXiv:2010.08581
Abstract
We propose a sampling-based method for computing the tensor ring (TR) decomposition of a data tensor. The method uses leverage score sampled alternating least squares to fit the TR cores in an iterative fashion. By taking advantage of the special structure of TR tensors, we can efficiently estimate the leverage scores and attain a method which has complexity sublinear in the number of input tensor entries. We provide high-probability relative-error guarantees for the sampled least squares problems. We compare our proposal to existing methods in experiments on both synthetic and real data. Our method achieves substantial speedup -- sometimes two or three orders of magnitude -- over competing methods, while maintaining good accuracy. We also provide an example of how our method can be used for rapid feature extraction.
arXiv commentAccepted to ICML 2021
References in corpus (12)
- Tensorizing Neural Networks
- Tensor Ring Decomposition
- Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
- Ultimate tensorization: compressing convolutional and FC layers alike
- Supervised Learning with Quantum-Inspired Tensor Networks
- Long-term Forecasting using Higher Order Tensor RNNs
- Fast and Guaranteed Tensor Decomposition via Sketching
- Tensor-Train Recurrent Neural Networks for Video Classification
- Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction
- Tensor network ranks
- Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition
- Efficient construction of tensor ring representations from sampling