Effective Tensor Sketching via Sparsification

摘要

In this article, 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}imes cdots imes {d}$ cubic tensor of stable rank $ {r}_{ {s}}$ , the sample size requirement for achieving a relative error $arepsilon $ is, up to a logarithmic factor, of the order $ {r}_{ {s}}^{1/2} {d}^{ {k}/2} /arepsilon $ when $arepsilon $ is relatively large, and $ {r}_{ {s}} {d} /arepsilon ^{2}$ and essentially optimal when $arepsilon $ 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.