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

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

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 the memory hierarchy, which is the main bottleneck in modern computing environments and architectures. In this paper, we review recent advances in randomization for the 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 the best and most promising algorithms.

Introduction

In the contemporary landscape of big data, information is increasingly multidimensional. Tensors—multidimensional generalizations of matrices—serve as the primary data structure for complex datasets ranging from video streams to multi-sensor internet-of-things (IoT) networks. To extract latent patterns and reduce dimensionality, the Tucker decomposition (and its variant, the Higher Order SVD or HOSVD) is a fundamental tool.

However, as tensor sizes scale into billions of entries, traditional deterministic algorithms encounter a severe "communication bottleneck." The time required to move data between memory hierarchies or across distributed nodes often dwarfs the actual computational time. Deterministic methods frequently exceed RAM limits or exhibit prohibitive latency when processing "out-of-core" datasets. Randomized algorithms have emerged as a transformative solution, offering significant speedups and reduced memory footprints by sketching large tensors into manageable forms.

Methodological Framework

The landscape of randomized Tucker decomposition can be categorized into four primary algorithmic families, each offering unique advantages in terms of accuracy, speed, and memory efficiency.

Overview of randomized approaches for Tucker decomposition.
  1. Random Projection: This approach involves multiplying the large data matrix (unfolded from the tensor) by a smaller random matrix, such as a Gaussian matrix. This process "squashes" the data into a lower-dimensional subspace while preserving its essential geometric structure, allowing for efficient computation on the sketch.
  2. Sampling: Rather than processing the entire tensor, sampling algorithms intelligently select specific "fibers" or columns based on probability distributions, such as leverage scores. This creates a representative sketch that maintains the statistical properties of the original data.
  3. Count-Sketch: A hashing-based technique that avoids the computational overhead of dense matrix multiplications. By using sign-flipping and summation, it reduces dimensionality with minimal arithmetic operations.
  4. Random Least-Squares: This method is typically integrated into iterative frameworks like the Higher-Order Orthogonal Iteration (HOOI) to solve underlying optimization problems more efficiently.

A critical distinction in these methods is the number of passes over the data. Multi-pass algorithms refine accuracy through repeated iterations, while single-pass (or pass-efficient) algorithms read the data only once—a necessity for streaming data or datasets stored on high-latency storage media.

Experimental Evaluation

The performance of these randomized frameworks was rigorously benchmarked against deterministic baselines using a variety of datasets:

  • Synthetic Tensors: Including random low-rank, sparse, Hilbert, and function-based tensors to test algorithmic limits in controlled environments.
  • COIL-100: A library of 7,200 color images of 100 different objects, used for image compression and feature extraction tasks.
  • NELL-2: A massive real-world sparse tensor (12,092 x 9,184 x 28,818) containing over 76 million non-zero elements, representing a significant challenge for traditional methods.
  • Video Data: Grayscale video sequences were utilized to evaluate reconstruction accuracy and compression ratios.

Key Insights and Results

The primary advantage of randomization is the drastic reduction in data movement. By sketching the tensor early in the pipeline, algorithms avoid the costly transfer of terabytes of data across system buses.

Performance Leaders: The Randomized Sequentially Truncated HOSVD (R-STHOSVD) emerged as a particularly robust algorithm. By truncating dimensions sequentially rather than simultaneously, it maintains smaller intermediate data sizes, further optimizing memory usage.

Speed and Scalability: In noiseless synthetic environments, randomized THOSVD achieved speedups of up to 17.96x compared to deterministic counterparts. Notably, the speedup factor often increases with the target rank of the decomposition, making these tools increasingly valuable as the complexity of the data grows.

Accuracy and Robustness: Despite the stochastic nature of these algorithms, the error introduced is often negligible. In tests with 20 dB of noise, randomized methods maintained a 90% fit, matching the accuracy of deterministic methods at a fraction of the cost. Crucially, for the NELL-2 dataset, randomized algorithms were the only viable option, as deterministic methods failed entirely due to memory exhaustion.

Conclusion and Future Directions

Randomized algorithms have matured into essential tools for big data tensor analysis. While they offer massive gains in efficiency, challenges remain in automated rank estimation and preserving the sparsity of tensors during projection steps. Future research is directed toward better integration of these sketches into distributed, multi-node computing environments to further push the boundaries of large-scale data science.

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 the memory hierarchy, which is the main bottleneck in modern computing environments and architectures. In this paper, we review recent advances in randomization for the 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 the best and most promising algorithms.
BibTeX
@inproceedings{ahmadiasl2021randomized,
  author = {Salman Ahmadi-Asl and Andrzej Cichocki and Anh Huy Phan and Ivan V. Oseledets and Stanislav Abukhovich and Toshihisa Tanaka},
  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