Effective Tensor Sketching via Sparsification
Effective Tensor Sketching via Sparsification
复制标题
DOI：
10.1109/tit.2021.3049174
复制
发表时间：
2017-10
影响因子：
2.5
通讯作者：
Dong Xia;M. Yuan
中科院分区：
文献类型：
--
作者：
Dong Xia;M. Yuan
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 kth order $ {d}\times \cdots \times {d}$ cubic tensor of 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.
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 kth order $ {d}\times \cdots \times {d}$ cubic tensor of 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.