# Effective Tensor Sketching via Sparsification

arXiv: https://arxiv.org/abs/1710.11298 · HTML: https://mlsanity.com/paper/1710.11298/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2017.

## Built on by (most cited first, 5 of 5)

- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions](https://mlsanity.com/paper/2108.10129/) (2021)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Sharp spectral norm concentration of sparse random tensors](https://mlsanity.com/paper/2609.20520/) (2026)

## Abstract (arXiv)

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 kth order d×cdots× d cubic tensor of it stable rank rs, the sample size requirement for achieving a relative error varepsilon is, up to a logarithmic factor, of the order rs1/2 dk/2 /varepsilon when varepsilon is relatively large, and rs d /varepsilon2 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.