A Sampling-Based Method for Tensor Ring Decomposition

Osman Asif Malik, Stephen Becker
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7400-7411, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-malik21b, title = {A Sampling-Based Method for Tensor Ring Decomposition}, author = {Malik, Osman Asif and Becker, Stephen}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7400--7411}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/malik21b/malik21b.pdf}, url = {https://proceedings.mlr.press/v139/malik21b.html}, 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.} }
Endnote
%0 Conference Paper %T A Sampling-Based Method for Tensor Ring Decomposition %A Osman Asif Malik %A Stephen Becker %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-malik21b %I PMLR %P 7400--7411 %U https://proceedings.mlr.press/v139/malik21b.html %V 139 %X 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.
APA
Malik, O.A. & Becker, S.. (2021). A Sampling-Based Method for Tensor Ring Decomposition. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7400-7411 Available from https://proceedings.mlr.press/v139/malik21b.html.

Related Material