A practical one-pass algorithm for tensor decomposition

We describe a practical one-pass algorithm for Tucker decomposition. The algorithm forms a linear sketch of the tensor and uses this sketch to construct approximations of low or fixed Tucker rank. The linear sketch is easy to compute online or using distributed computing resources, which enables Tucker decomposition of extremely large scale tensors, even those too large to fit in memory. Applications include compression of PDE simulations, large scale sensor networks, and video. We provide the first rigorous theoretical guarantees for any one pass Tucker decomposition method when the linear sketch is formed from a random Gaussian matrix. We also propose to use a lower memory sketch, the Tensor Dimension Reduction Map, which achieves similar approximation error in experiments and significantly reduces memory and storage costs.