An Efficient Two-Sided Sketching Method for Large-Scale Tensor Decomposition Based on Transformed Domains

Zhiguang Cheng, Gaohang Yu, Xiaohao Cai, Liqun QiarXiv 2024 · DOI · arXiv

In the era of big data, we aren't just dealing with tables of numbers; we are dealing with tensors—multidimensional arrays that capture complex relationships in everything from hyperspectral imagery to scientific simulations. But as these tensors grow to massive scales, traditional decomposition methods (the mathematical tools we use to compress and understand them) hit a computational wall.

A recent paper titled "An Efficient Two-Sided Sketching Method for Large-Scale Tensor Decomposition Based on Transformed Domains" introduces a clever way to bypass this wall using randomized "sketching" and smart mathematical transforms.

TL;DR

The authors propose a "two-sided sketching" framework that uses randomized projections to drastically reduce the size of large tensors before performing decomposition. By leveraging the $\star_L$-product (a generalized tensor-tensor product) and the Discrete Cosine Transform (DCT), they achieve a low-rank approximation that is significantly faster than traditional methods while maintaining high accuracy.

What Problem Does This Paper Address?

Tensor decomposition is the multidimensional equivalent of Principal Component Analysis (PCA) or Singular Value Decomposition (SVD). It allows us to find the "low-rank" structure hidden within massive datasets, making them easier to store and analyze.

However, standard algorithms like the t-product (which relies on the Fast Fourier Transform) have a major drawback: they often require complex arithmetic, which is computationally expensive and memory-intensive for real-valued data. Furthermore, "one-sided" sketching methods—which only look at the data from one perspective—often miss critical information, leading to poor approximations. The challenge is to find a way to compress these tensors from "both sides" (rows and columns, effectively) without losing the underlying signal.

Methods

The researchers introduce a novel two-sided sketching method built on the $\star_L$-product framework. Here’s the breakdown of their approach:

  1. Two-Sided Sketching: Instead of just projecting the tensor once, they generate four random linear maps to capture the "range," the "co-range," and a "core sketch." This "core" acts as a bridge, providing extra information that refines the estimation of singular values.
  2. Transformed Domains ($\star_L$): Unlike previous methods that were locked into the Fourier domain, this framework allows for any invertible linear transform. The authors specifically highlight the Discrete Cosine Transform (DCT). Because DCT works entirely with real numbers, it avoids the overhead of complex arithmetic found in Fourier-based methods.
  3. Power Iteration (PI): To further boost accuracy, they incorporate a "power iteration" step. By repeatedly applying the tensor and its transpose during the sketching phase, they "sharpen" the singular values, making the method much more effective for data where the "signal" isn't immediately obvious.

Datasets

The authors validated their algorithms using a mix of synthetic and real-world data:

  • Synthetic Tensors: Tensors with "PolyDecay" (slow and fast decaying spectra) to test how the algorithm handles different mathematical structures.
  • Color Images: Two high-resolution images—an HDU campus scene ($1200 \times 1800 \times 3$) and a large London cityscape ($4775 \times 7155 \times 3$).
  • Grayscale Video: The "hall monitor" video clip ($144 \times 176 \times 30$), a standard benchmark in computer vision.

Key Insights and Ideas

  • The "Core" is Key: The inclusion of a core sketch (Equation 3.16 in the paper) is the "aha moment." It allows the algorithm to reconstruct the most important parts of the tensor more accurately than methods that only consider the range and co-range.
  • Real Math is Faster Math: By using the DCT instead of the DFT (Fourier), the authors show that you can achieve similar (or better) accuracy while significantly cutting down on CPU time because you aren't juggling imaginary numbers.
  • Power Iteration as a Precision Tool: The results show that even a single power iteration ($q=1$) can dramatically lower the relative error for noisy or complex data, representing a very favorable trade-off between a tiny bit of extra computation and a massive gain in precision.

Key Results

The proposed DCT-Gaussian-Sketch and its Power Iteration version (DCT-Gaussian-Sketch-PI) were compared against state-of-the-art methods like T-Sketch and rt-SVD.

  • Speed: In the London image test, the proposed method was nearly 15x faster than the truncated-t-SVD (the gold standard for accuracy) while maintaining a very high Peak Signal-to-Noise Ratio (PSNR).
  • Accuracy: On the "hall monitor" video, the two-sided method achieved a PSNR of 22.78 dB, significantly outperforming the standard T-Sketch (16.90 dB) at the same sketch size.
  • Denoising: The method showed a surprising ability to act as a denoiser. When Gaussian noise was added to a QR code image, the DCT-Gaussian-Sketch-PI actually produced a result with a higher PSNR than the original noisy image, effectively "cleaning" the data during decomposition.

Limitations and Future Work

While the results are impressive, the paper notes a few areas for further exploration:

  • Higher-Order Tensors: The current work focuses on third-order tensors (3D arrays). Extending this two-sided sketching logic to N-order tensors (4D, 5D, etc.) is a logical next step but mathematically more complex.
  • Optimal Transform Selection: While DCT performed best here, the $\star_L$ framework allows for any transform. Future work could involve "learning" the optimal transform for a specific dataset (data-driven transforms) to squeeze out even more efficiency.
  • Sketching Operator Variety: The authors tested Gaussian, SRHT, and Count Sketch operators, but there may be other randomized projection types that work better for specific sparse data types.

Summary updated

Abstract

Large tensors are frequently encountered in various fields such as computer vision, scientific simulations, sensor networks, and data mining. However, these tensors are often too large for convenient processing, transfer, or storage. Fortunately, they typically exhibit a low-rank structure that can be leveraged through tensor decomposition. However, performing large-scale tensor decomposition can be time-consuming. Sketching is a useful technique to reduce the dimensionality of the data. In this paper, we propose a novel two-sided sketching method based on the $\star_{L}$-product decomposition and transformed domains like the discrete cosine transformation. A rigorous theoretical analysis is also conducted to assess the approximation error of the proposed method. Specifically, we improve our method with power iteration to achieve more precise approximate solutions. Extensive numerical experiments and comparisons on low-rank approximation of synthetic large tensors and real-world data like color images and grayscale videos illustrate the efficiency and effectiveness of the proposed approach in terms of both CPU time and approximation accuracy.
BibTeX
@misc{cheng2024efficient,
  author = {Zhiguang Cheng and Gaohang Yu and Xiaohao Cai and Liqun Qi},
  title = {{An Efficient Two-Sided Sketching Method for Large-Scale Tensor Decomposition Based on Transformed Domains}},
  year = {2024},
  eprint = {2404.16580},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.16580},
}
Figure