  The low-rank canonical polyadic tensor decomposition is useful in data
analysis and can be computed by solving a sequence of overdetermined least
squares subproblems. Motivated by consideration of sparse tensors, we propose
sketching each subproblem using leverage scores to select a subset of the rows,
with probabilistic guarantees on the solution accuracy. We randomly sample rows
proportional to leverage score upper bounds that can be efficiently computed
using the special Khatri-Rao subproblem structure inherent in tensor
decomposition. Crucially, for a $(d+1)$-way tensor, the number of rows in the
sketched system is $O(r^d/\epsilon)$ for a decomposition of rank $r$ and
$\epsilon$-accuracy in the least squares solve, independent of both the size
and the number of nonzeros in the tensor. Along the way, we provide a practical
solution to the generic matrix sketching problem of sampling overabundance for
high-leverage-score rows, proposing to include such rows deterministically and
combine repeated samples in the sketched system; we conjecture that this can
lead to improved theoretical bounds. Numerical results on real-world
large-scale tensors show the method is significantly faster than deterministic
methods at nearly the same level of accuracy.
