Title: Effective Tensor Sketching via Sparsification,
Abstract: In this paper, we investigate effective sketching schemes via sparsification
for high dimensional multilinear arrays or tensors. More specifically, we
propose a novel tensor sparsification algorithm that retains a subset of the
entries of a tensor in a judicious way, and prove that it can attain a given
level of approximation accuracy in terms of tensor spectral norm with a much
smaller sample complexity when compared with existing approaches. In
particular, we show that for a $k$th order $d\times\cdots\times d$ cubic tensor
of {\it stable rank} $r_s$, the sample size requirement for achieving a
relative error $\varepsilon$ is, up to a logarithmic factor, of the order
$r_s^{1/2} d^{k/2} /\varepsilon$ when $\varepsilon$ is relatively large, and
$r_s d /\varepsilon^2$ and essentially optimal when $\varepsilon$ is
sufficiently small. It is especially noteworthy that the sample size
requirement for achieving a high accuracy is of an order independent of $k$. To
further demonstrate the utility of our techniques, we also study how higher
order singular value decomposition (HOSVD) of large tensors can be efficiently
approximated via sparsification.