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 ℓ0ℓ0 sampling and producing ℓ1ℓ1 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.