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 relative error high probability guarantees for the sampled least squares problems. We compare our proposal to existing methods in experiments on both synthetic and real data. The real data comes from hyperspectral imaging, video recordings, and a subset of the COIL-100 image dataset. Our method achieves substantial speedup---sometimes two or three orders of magnitude---over competing methods, while maintaining good accuracy  .
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 .
R
sampling based
sampling-based
R
relative error high probability
high-probability relative-error
D
The real data comes from hyperspectral imaging, video recordings, and a subset of the COIL-100 image dataset.
R
speedup---sometimes
speedup -- sometimes
R
magnitude---over
magnitude -- over
A
. We also provide an example of how our method can be used for rapid feature extraction