Randomized Algorithms for Computation of Tucker Decomposition and Higher Order SVD (HOSVD)

Salman Ahmadi-Asl, Stanislav Abukhovich, Maame G. Asante-Mensah, Andrzej Cichocki, Anh-Huy Phan, Toshihisa Tanaka, Ivan V. Oseledets

TL;DR

This paper provides a comprehensive review of randomized algorithms designed to compute Tucker decompositions and Higher Order SVD (HOSVD) for massive datasets. By shifting from deterministic to probabilistic methods—such as random projections and sketching—these algorithms achieve order-of-magnitude speedups and reduced memory footprints with negligible loss in accuracy.

What Problem Does This Paper Address?

As we move into the era of "Big Data," multidimensional arrays (tensors) have become ubiquitous in fields like deep learning, signal processing, and computer vision. However, traditional deterministic algorithms for tensor decomposition, such as the standard HOSVD, face a "curse of dimensionality."

The primary bottlenecks are not just raw floating-point operations, but communication costs: moving massive amounts of data between different levels of memory hierarchy or across a network. Deterministic methods often require multiple passes over the data and high memory overhead, making them prohibitive for tensors that don't fit in RAM (out-of-core) or are distributed across clusters.

Methods

The authors categorize randomized approaches into four main pillars:

  1. Random Projection: Multiplying the data tensor by a random matrix (e.g., Gaussian) to capture the "range" of the data in a much smaller subspace.
  2. Sampling: Selecting a subset of "fibers" (columns/rows) from the tensor based on probability distributions like leverage scores or uniform sampling.
  3. Count-Sketch: Using hashing and signing to generate linear combinations of columns without the expensive matrix multiplications required by standard projections.
  4. Random Least-Squares: Using sketching techniques to solve the overdetermined least-squares problems that arise in iterative methods like Higher-Order Orthogonal Iteration (HOOI).

A key highlight is the Sequentially Truncated HOSVD (STHOSVD) and its randomized variants. Unlike standard HOSVD, which processes all modes of the original large tensor, STHOSVD reduces the size of the tensor mode-by-mode, significantly lowering the computational cost of subsequent steps.

Datasets

The authors evaluate these algorithms using a mix of synthetic and real-world benchmarks:

  • Synthetic Tensors: Random low-rank tensors (noiseless and noisy), random sparse tensors, Hilbert tensors (notoriously difficult due to slow singular value decay), and function-based tensors.
  • COIL-100: A library of 7,200 color images of 100 objects under different rotations.
  • NELL-2: A massive, real-world sparse tensor representing knowledge-base relations.
  • Video Data: A grayscale video tensor of size $2200 \times 1080 \times 1980$, used to test compression and reconstruction.

Key Insights and Ideas

  • Communication is the Bottleneck: The most "elegant" algorithms are Pass-Efficient (like R-PET). These algorithms pass over the original data tensor as few times as possible (sometimes only once), which is critical for data stored on slow disks or distributed systems.
  • The Power of STHOSVD: The sequential approach is almost always superior to the "all-at-once" HOSVD. By shrinking the tensor at each step, the randomized SVDs in later steps become much faster.
  • EVD vs. SVD: For computing factor matrices, the authors find that Eigenvalue Decomposition (EVD) of the Gramian matrix is often significantly faster than performing a direct SVD on the unfolding matrices.
  • Structure Preservation: While many randomized methods lose the sparsity or non-negativity of the original data, certain sampling-based methods (like R-ST) can preserve these properties in the factor matrices.

Key Results

The simulations demonstrate that randomized algorithms are "nearly optimal" in terms of accuracy while being vastly faster:

  • Speedups: On a $1000^3$ noiseless tensor, randomized STHOSVD showed a ~17x speedup over deterministic SVD-based versions (Figure 4).
  • Accuracy: In almost all tests (Table 2), the relative error of randomized methods was within a tiny fraction of the deterministic counterparts (e.g., $10^{-13}$ vs $10^{-12}$).
  • Scalability: For the massive NELL-2 dataset, deterministic algorithms often failed due to memory limits, whereas randomized STHOSVD successfully decomposed the tensor in roughly 200–2000 seconds depending on the target rank.
  • Visual Fidelity: In video and image reconstruction (COIL-100), the randomized methods produced images indistinguishable from deterministic ones to the human eye, despite the massive reduction in computation time.

Limitations and Future Work

  • Rank Estimation: Most current randomized algorithms require the user to provide a target rank $(R_1, R_2, \dots, R_N)$ upfront. Estimating this rank automatically in a randomized framework remains a challenge.
  • Preserving Structure: Many projection-based methods destroy sparsity. Developing "structure-aware" randomized algorithms that maintain non-negativity or specific sparsity patterns throughout the decomposition is an active area of research.
  • Dynamic/Streaming Data: While "single-pass" algorithms exist, more work is needed for truly "online" tensor decomposition where the tensor grows over time (e.g., real-time sensor feeds).

Summary updated

Abstract

Big data analysis has become a crucial part of new emerging technologies such as the internet of things, cyber-physical analysis, deep learning, anomaly detection, etc. Among many other techniques, dimensionality reduction plays a key role in such analyses and facilitates feature selection and feature extraction. Randomized algorithms are efficient tools for handling big data tensors. They accelerate decomposing large-scale data tensors by reducing the computational complexity of deterministic algorithms and the communication among different levels of memory hierarchy, which is the main bottleneck in modern computing environments and architectures. In this article, we review recent advances in randomization for computation of Tucker decomposition and Higher Order SVD (HOSVD). We discuss random projection and sampling approaches, single-pass and multi-pass randomized algorithms and how to utilize them in the computation of the Tucker decomposition and the HOSVD. Simulations on synthetic and real datasets are provided to compare the performance of some of best and most promising algorithms.
BibTeX
@inproceedings{ahmadiasl2021randomized,
  author = {Salman Ahmadi-Asl and Stanislav Abukhovich and Maame G. Asante-Mensah and Andrzej Cichocki and Anh-Huy Phan and Toshihisa Tanaka and Ivan V. Oseledets},
  title = {{Randomized Algorithms for Computation of Tucker Decomposition and Higher Order SVD (HOSVD)}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=nSplPuGUCN},
}

Loading related content...

Figure