Spotlight Poster
Fast Sampling-Based Sketches for Tensors
William Swartworth · David Woodruff
Hall C 4-9 #2810
[
Abstract
]
Tue 23 Jul 4:30 a.m. PDT
— 6 a.m. PDT
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.
Live content is unavailable. Log in and register to view live content