  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.
