Fast Sampling-Based Sketches for Tensors
Abstract
We introduce a new approach for applying sampling-based sketches to two and three mode tensors. We illustrate our technique to construct sketches for the classical problems of $\ell_0$ sampling and producing $\ell_1$ embeddings. In both settings we achieve sketches that can be applied to a rank one tensor in $(\mathbb{R}^d)^{\otimes q}$ (for $q=2,3$) in time scaling with $d$ rather than $d^2$ or $d^3$. Our main idea is a particular sampling construction based on fast convolution which allows us to quickly compute sums over sufficiently random subsets of tensor entries.
Cite
Text
Swartworth and Woodruff. "Fast Sampling-Based Sketches for Tensors." International Conference on Machine Learning, 2024.Markdown
[Swartworth and Woodruff. "Fast Sampling-Based Sketches for Tensors." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/swartworth2024icml-fast/)BibTeX
@inproceedings{swartworth2024icml-fast,
title = {{Fast Sampling-Based Sketches for Tensors}},
author = {Swartworth, William Joseph and Woodruff, David},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {47378-47395},
volume = {235},
url = {https://mlanthology.org/icml/2024/swartworth2024icml-fast/}
}