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 Oseledets

Introduction

In the era of "Big Data," multidimensional arrays, or tensors, have become ubiquitous across fields such as deep learning, signal processing, and computer vision. However, traditional deterministic algorithms for tensor decomposition, like the standard Higher Order SVD (HOSVD), increasingly struggle with the "curse of dimensionality." The primary bottleneck in modern computing is not merely raw floating-point operations but the communication costs associated with moving massive datasets across memory hierarchies or networks. This review explores how randomized algorithms address these challenges by shifting from deterministic to probabilistic frameworks, facilitating efficient dimensionality reduction for feature selection and extraction.

Methodological Pillars of Randomization

Randomized algorithms for Tucker decomposition typically leverage four core techniques to reduce computational complexity and memory overhead while maintaining high accuracy. These methods accelerate the decomposition of large-scale data tensors by reducing the communication among different levels of memory hierarchy, which is often the main bottleneck in modern computing architectures.

Overview of the four main pillars of randomized Tucker decomposition algorithms.
  1. Random Projection: Data tensors are multiplied by random matrices (e.g., Gaussian) to capture the essential "range" of the data within a significantly smaller subspace. This effectively reduces the size of the problem before applying standard decomposition techniques.
  2. Sampling: Instead of processing the entire tensor, algorithms select a subset of "fibers" (columns or rows) based on probability distributions like leverage scores or uniform sampling. This approach can help preserve structures like sparsity in the resulting factor matrices.
  3. Count-Sketch: This technique uses hashing and signing to generate linear combinations of columns, avoiding the expensive matrix multiplications required by standard projections. It is particularly useful for very large, sparse tensors.
  4. Random Least-Squares: Sketching techniques are applied to solve the overdetermined least-squares problems inherent in iterative methods like Higher-Order Orthogonal Iteration (HOOI), significantly speeding up the convergence of these algorithms.

A significant advancement discussed is the Sequentially Truncated HOSVD (STHOSVD). Unlike the standard HOSVD, which processes all modes of the original large tensor simultaneously, STHOSVD reduces the tensor size mode-by-mode. Randomized variants of STHOSVD further accelerate this process by ensuring that later stages operate on already-compressed data, leading to substantial computational savings.

Key Insights and Performance

The review highlights several critical findings from simulations on synthetic and real-world datasets, including the NELL-2 knowledge base, the COIL-100 image library, and high-resolution video data:

  • Communication Efficiency: "Pass-efficient" algorithms, such as R-PET, are essential for distributed or out-of-core datasets. These algorithms minimize the number of times the original data is read from disk, which is critical for performance in modern hardware environments.
  • Speed vs. Accuracy: Randomized STHOSVD can achieve up to a 17x speedup over deterministic counterparts on large tensors ($1000^3$) with negligible loss in precision. Relative errors are often within a tiny fraction of deterministic results (e.g., $10^{-13}$ vs $10^{-12}$).
  • Scalability: For massive datasets like NELL-2, where deterministic methods often fail due to memory constraints, randomized approaches successfully complete decompositions in reasonable timeframes (200–2000 seconds depending on rank).
  • Visual Fidelity: In applications like video compression and image reconstruction, the outputs of randomized methods are often indistinguishable from those of deterministic algorithms to the human eye, despite the massive reduction in computation time.

Future Directions

While randomized tensor decompositions offer a powerful solution for big data, several challenges remain. Future research is needed to automate rank estimation within randomized frameworks, as most current methods require target ranks to be predefined. Additionally, developing "structure-aware" algorithms that preserve properties like sparsity or non-negativity—which are often lost during random projections—remains a priority. Finally, as data increasingly arrives in streams, the development of truly "online" randomized tensor decomposition methods is a vital next step for real-time sensor feeds and dynamic data analysis.

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 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},
}
Figure