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.
- 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.
- 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.
- 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.
- 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