Fast Sampling Based Sketches for Tensors
<|reference_start|>Fast Sampling Based Sketches for Tensors: 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.<|reference_end|>
@article{swartworth2024fast,
    title={Fast Sampling Based Sketches for Tensors},
    author={William Swartworth, David P. Woodruff},
    journal={arXiv preprint arXiv:2406.06735},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.06735},
    primaryClass={cs.DS}
}