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.

本文提出了一种基于采样的、使用杠杆分数样本交替最小二乘法的张量环分解计算方法，其中利用张量环张量的特殊结构，可高效地评估杠杆分数并获得复杂度次线性的方法，该方法在合成数据和真实数据实验中与现有方法相比具有显著加速效果，同时保持良好的准确性，提供了一个快速特征提取的示例。