A Caltech Library Service

Multi-dimensional Tensor Sketch

Shi, Yang and Anandkumar, Animashree (2019) Multi-dimensional Tensor Sketch. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Sketching refers to a class of randomized dimensionality reduction methods that aim to preserve relevant information in large-scale datasets. They have efficient memory requirements and typically require just a single pass over the dataset. Efficient sketching methods have been derived for vector and matrix-valued datasets. When the datasets are higher-order tensors, a naive approach is to flatten the tensors into vectors or matrices and then sketch them. However, this is inefficient since it ignores the multi-dimensional nature of tensors. In this paper, we propose a novel multi-dimensional tensor sketch (MTS) that preserves higher order data structures while reducing dimensionality. We build this as an extension to the popular count sketch (CS) and show that it yields an unbiased estimator of the original tensor. We demonstrate significant advantages in compression ratios when the original data has decomposable tensor representations such as the Tucker, CP, tensor train or Kronecker product forms. We apply MTS to tensorized neural networks where we replace fully connected layers with tensor operations. We achieve nearly state of art accuracy with significant compression on image classification benchmarks.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Alternate Title:Multi-dimensional Tensor Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations
Additional Information:The authors would like to thank Jean Kossaifi for providing TRL code and Mikus Grasis for providing writing suggestions. Yang Shi is supported by Air Force Award FA9550-15-1-0221.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-15-1-0221
Record Number:CaltechAUTHORS:20190327-085821224
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94183
Deposited By: George Porter
Deposited On:28 Mar 2019 15:10
Last Modified:03 Oct 2019 21:01

Repository Staff Only: item control page