Low-Rank Tucker Approximation of a Tensor From Streaming Data

Yiming Sun, Yang Guo, Charlene Luo, Joel A. Tropp, Madeleine Udell

Abstract

This paper introduces a novel, one-pass algorithm for computing low-rank Tucker approximations of massive tensors from streaming or distributed data. By using a specialized "Tucker sketch," the method achieves "quasi-optimal" accuracy—meaning its error is theoretically bounded relative to the best possible approximation—while using storage proportional only to the size of the final compressed output.

Introduction

Tensors (multidimensional arrays) are the natural format for large-scale data in fields like neuroscience, climate modeling, and computer vision. However, these datasets are often so large they cannot fit into a computer's main memory (RAM). Standard compression techniques like the Higher-Order Singular Value Decomposition (HOSVD) typically require multiple passes over the data or require the entire tensor to be stored locally. This is impossible in "streaming" scenarios (where data arrives sequentially and is never stored) or "distributed" settings (where data is spread across many machines). The challenge is to find a way to capture the essential structure of a massive tensor in a single pass using very little memory.

Methods

The authors propose a sketching-based approach. Instead of processing the full tensor, they apply a randomized linear map to the data as it streams by to create a much smaller "sketch."

The Tucker Sketch

The algorithm creates two types of sketches simultaneously: "factor sketches" capture the important directions (subspaces) within each dimension (mode) of the tensor, and a "core sketch" captures the interactions between these dimensions. This procedure, detailed in Algorithm 4.1, uses Dimension Reduction Maps (DRMs) to transform the high-dimensional tensor into a compact representation.

Algorithm 4.1: The Tucker Sketch procedure

Tensor Random Projection (TRP)

To keep the sketching process itself memory-efficient, the authors use Tensor Random Projection (TRP). This technique uses Khatri-Rao products of smaller random matrices, drastically reducing the storage needed for the random maps compared to standard Gaussian matrices. As shown in the table below, TRP offers significant storage advantages over other DRMs.

Comparison of storage and computation costs for different Dimension Reduction Maps (DRMs)

Key Insights

  • Linearity is Key: Because the sketching operation is linear, it "commutes" with data updates. This means you can sketch a tensor slice-by-slice, or entry-by-entry, and the sum of those sketches is identical to the sketch of the full tensor.
  • Separation of Concerns: The Tucker sketch cleverly separates the problem of finding the mode-wise subspaces from the problem of finding the "core" tensor that links them.
  • Quasi-Optimality: Rigorous proofs show that the one-pass method is nearly as good as the best possible Tucker approximation, with error within a factor of $2\sqrt{N}$ of the optimal solution (where $N$ is the number of dimensions).

Evaluation and Results

The researchers evaluated their algorithms on synthetic data and real-world datasets, including global climate simulations (CESM), combustion processes, and a 41.4 GB video dataset.

  • Superior Accuracy: In head-to-head comparisons with the previous leading streaming method (Tucker TensorSketch), the new one-pass algorithm reduced approximation error by more than an order of magnitude for the same storage budget.
  • Massive Compression: On the video dataset, the method achieved successful scene classification using only 1/500th of the original data's storage.
  • Consistent Performance: Numerical experiments showed that the choice of random map (Gaussian, SSRFT, or TRP) had little impact on accuracy, meaning users can choose the most computationally efficient map (TRP) without a penalty.

Conclusion

While the current protocol is designed for offline analysis after all data has been observed, it provides a powerful tool for massive tensor compression. Future work may address real-time monitoring where updated approximations are needed at every time step, and extending tight theoretical bounds to more structured maps like TRP.

Summary updated

BibTeX
@article{sun2020low,
  author = {Yiming Sun and Yang Guo and Charlene Luo and Joel A. Tropp and Madeleine Udell},
  title = {{Low-Rank Tucker Approximation of a Tensor From Streaming Data}},
  journal = {SIAM J. Math. Data Sci.},
  year = {2020},
  url = {https://openreview.net/forum?id=ts3TKgONGRr},
}
Figure