Skip to yearly menu bar Skip to main content


Spotlight Poster

Fast Sampling-Based Sketches for Tensors

William Swartworth · David Woodruff

Hall C 4-9 #2810

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 00 sampling and producing 11 embeddings. In both settings we achieve sketches that can be applied to a rank one tensor in (Rd)q(Rd)q (for q=2,3q=2,3) in time scaling with dd rather than d2d2 or d3d3. 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.

Chat is not available.