  Tensor Train~(TT) decomposition is widely used in the machine learning and
quantum physics communities as a popular tool to efficiently compress
high-dimensional tensor data. In this paper, we propose an efficient algorithm
to accelerate computing the TT decomposition with the Alternating Least Squares
(ALS) algorithm relying on exact leverage scores sampling. For this purpose, we
propose a data structure that allows us to efficiently sample from the tensor
with time complexity logarithmic in the tensor size. Our contribution
specifically leverages the canonical form of the TT decomposition. By
maintaining the canonical form through each iteration of ALS, we can
efficiently compute (and sample from) the leverage scores, thus achieving
significant speed-up in solving each sketched least-square problem. Experiments
on synthetic and real data on dense and sparse tensors demonstrate that our
method outperforms SVD-based and ALS-based algorithms.
