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:
- 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.
- Sampling: Selecting a subset of "fibers" (columns/rows) from the tensor based on probability distributions like leverage scores or uniform sampling.
- Count-Sketch: Using hashing and signing to generate linear combinations of columns without the expensive matrix multiplications required by standard projections.
- 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