# A New Sampling Technique for Tensors

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2015.

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

- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)

## Abstract (arXiv)

In this paper we propose new techniques to sample arbitrary third-order tensors, with an objective of speeding up tensor algorithms that have recently gained popularity in machine learning. Our main contribution is a new way to select, in a biased random way, only O(n1.5/ε2) of the possible n3 elements while still achieving each of the three goals:  em (a) tensor sparsification: for a tensor that has to be formed from arbitrary samples, compute very few elements to get a good spectral approximation, and for arbitrary orthogonal tensors em (b) tensor completion: recover an exactly low-rank tensor from a small number of samples via alternating least squares, or em (c) tensor factorization: approximating factors of a low-rank tensor corrupted by noise.  Our sampling can be used along with existing tensor-based algorithms to speed them up, removing the computational bottleneck in these methods.