Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.

Nam H. Nguyen, Petros Drineas, Trac D. Tran

Abstract

Given an order-|$d$| tensor |${\mathcal {A}} \in {\mathbb {R}}^{n \times n \times \ldots \times n}$|⁠, we present a simple, element-wise sparsification algorithm that zeroes out all sufficiently small elements of |${\mathcal {A}}$|⁠, keeps all sufficiently large elements of |${\mathcal {A}}$| and retains some of the remaining elements with probabilities proportional to the square of their magnitudes. We analyze the approximation accuracy of the proposed algorithm using a powerful inequality that we derive. This inequality bounds the spectral norm of a random tensor and is of independent interest. As a result, we obtain novel bounds for the tensor sparsification problem.
BibTeX
@inproceedings{nguyen2015tensor,
  author = {Nam H. Nguyen and Petros Drineas and Trac D. Tran},
  title = {{Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.}},
  booktitle = {Information},
  year = {2015},
  doi = {10.1093/imaiai/iav004},
}
Figure