🔢 mathematics

A Practical Mode-parallel Implementation of the (H-)Tucker Decomposition via Randomization

This paper proposes a novel mode-parallel implementation of Tucker and H-Tucker tensor decompositions using randomization techniques to significantly reduce computational time, memory usage, and energy consumption for high-dimensional data while maintaining accuracy.

Original authors: Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, multi-dimensional library of data. Instead of just a list of books (1D) or a shelf of books (2D), imagine a library where every book has a color, a texture, a smell, a sound, and a feeling associated with it. This is a tensor. It's a way to store complex data (like a video, a medical scan, or weather patterns) all in one neat package.

The problem? These libraries get huge very quickly. Trying to analyze them is like trying to read every single page of every book in the world simultaneously. It takes forever, costs a fortune in electricity, and requires a storage room bigger than a city.

To solve this, mathematicians use a technique called decomposition. Think of it like taking a giant, messy puzzle and realizing it's actually made of a few smaller, simpler puzzle pieces that fit together perfectly. This is the Tucker and H-Tucker decomposition. It breaks the giant data monster down into a "core" (the essential story) and a few "factor matrices" (the rules for how the story is told).

However, the old ways of doing this were like trying to build a bridge by first building a full-scale model of the entire ocean. You had to copy the whole dataset into memory just to process a tiny part of it. This was slow and memory-hungry.

The New Solution: "Mode-Parallel" with Random Sampling

This paper introduces a clever new way to do this: Mode-Parallel Decomposition via Randomization. Let's break it down with some analogies.

1. The Old Way: The "Copy-Paste" Disaster

Imagine you are a team of chefs trying to taste a giant soup to figure out its ingredients.

The Old Method: To taste the soup, every single chef had to bring a copy of the entire pot of soup to their own station. If you have 8 chefs, you need 8 giant pots. This is impossible if the pot is the size of the ocean.
The Bottleneck: You can't taste the soup until everyone has their own copy, and you can't make the copies fast enough.

2. The New Method: The "Sampling" Strategy

The authors propose a smarter way using Randomization and Parallelism.

The "Fiber Sampling" (The Tasting Spoon):
Instead of bringing the whole pot, imagine you just need to dip a spoon in to get a sample.

The new algorithm doesn't build the whole "unfolded" matrix (the giant pot). Instead, it randomly picks a few "fibers" (think of these as single strands of spaghetti or specific rows of data) from the original tensor.
Analogy: Instead of copying the whole library, you randomly pick 100 books from different shelves. If the library is well-organized (which most real-world data is), those 100 random books tell you almost everything you need to know about the whole library.
The Benefit: You don't need 8 giant pots anymore. Each chef only needs a tiny cup of soup. This saves massive amounts of memory.

The "Mode-Parallel" (The Team of Chefs):

The Old Way: Even with random sampling, many old algorithms still made the chefs work one by one. Chef 1 tastes the soup, then Chef 2, then Chef 3.
The New Way: Because we aren't copying the whole pot, all 8 chefs can work at the exact same time. Chef 1 tastes the "color" dimension, Chef 2 tastes the "texture" dimension, and so on. They all work in parallel.
The Result: The job gets done 8 times faster (or even more) because everyone is working simultaneously without waiting for the others.

3. The "Range-Finder" (The Smart Filter)

Once the chefs have their tiny cups of soup (the samples), they need to figure out the main ingredients.

The paper uses a technique called Randomized Range-Finding. Imagine the chefs have a magic filter that instantly separates the "flavor" from the "water."
Even though they only tasted a tiny sample, this filter helps them reconstruct the entire flavor profile of the soup with high accuracy. It's like a detective who can solve a crime by looking at just a few clues because they know exactly how to connect the dots.

Why This Matters

Speed: The new method is 10 times faster than the best existing methods in many cases.
Memory: It doesn't need to store the whole dataset in memory. It works with tiny slices. This means you can analyze data on a standard computer that previously would have required a supercomputer.
Scalability: The authors tested this on a supercomputer (Leonardo at Cineca). They showed that as they added more processors (more chefs), the speed increased almost perfectly. It scales beautifully.
Accuracy: Despite using random samples, the results are just as accurate as the slow, memory-hungry methods.

The H-Tucker Twist

The paper also applies this to a more complex structure called H-Tucker (Hierarchical Tucker).

Analogy: If Tucker is a flat puzzle, H-Tucker is a puzzle with a tree structure (like a family tree).
The authors built a version of their random sampling method for this tree structure too. They showed that even for these complex, tree-like data structures, you can break them down quickly and in parallel without needing to build the whole tree first.

The Bottom Line

This paper is like inventing a drone delivery system for data analysis.

Before: You had to drive a massive truck (the old algorithm) to every single house to deliver a package. It was slow and clogged the roads.
Now: You send out a swarm of tiny drones (the random samples) that fly to specific houses, grab the necessary info, and bring it back instantly. They all fly at once (parallel), they don't clog the roads (low memory), and they get the job done in record time.

It's a practical, energy-efficient, and incredibly fast way to unlock the secrets hidden inside our biggest, most complex datasets.

1. Problem Statement

Tensors are essential for representing multidimensional data, and low-rank factorizations (like Tucker and Hierarchical Tucker) are crucial for uncovering hidden structures and compressing data. However, computing these decompositions for high-dimensional tensors faces two major bottlenecks:

Computational Cost: Traditional algorithms (e.g., High-Order SVD or HOSVD) require computing Singular Value Decompositions (SVDs) on large tensor matricizations (unfolding the tensor into matrices). The size of these matrices grows exponentially with the number of modes ( $d$ ), leading to prohibitive computational complexity ( $O(d n^{d+1})$ ).
Memory Demand: To perform these SVDs, standard algorithms require assembling full tensor matricizations. Storing a single matricization often requires memory equivalent to the entire original tensor. This makes mode-parallel implementations (where operations along different modes are performed simultaneously on different nodes) impractical, as each node would need to store a full copy of the tensor.

Existing randomized approaches (like R-HOSVD) reduce computational time by using Randomized SVD (RSVD) but still require forming the full matricizations, failing to solve the memory bottleneck for mode-parallel execution.

2. Methodology

The authors propose a novel framework that combines fiber sampling and randomized range-finding to enable true mode-parallel decomposition without ever constructing full tensor matricizations.

A. Subsampled Randomized HOSVD (Sub-R-HOSVD) for Tucker Decomposition

Instead of computing the SVD of the full mode- $k$ unfolding $X^{(k)}$ , the algorithm proceeds as follows for each mode $k$ :

Fiber Sampling: Instead of forming $X^{(k)}$ , the algorithm randomly selects $s_k$ fibers (columns of the unfolding) directly from the tensor $X$ . This creates a small matrix $Y_k \in \mathbb{R}^{n_k \times s_k}$ where $s_k \ll \prod_{j \neq k} n_j$ .
Randomized Range-Finding: A Gaussian sketch matrix $\Omega_k$ is applied to $Y_k$ to compute an orthonormal basis $U_k$ that approximates the column space of the full unfolding $X^{(k)}$ .
Core Computation: Once all factor matrices $\{U_k\}$ are computed, the core tensor $S$ is obtained via tensor-times-matrix (TTM) products.

Key Innovation: By avoiding the construction of $X^{(k)}$ , the memory requirement drops from storing the full tensor to storing only a small subset of fibers. This allows each computational node in a parallel setting to handle a different mode independently without needing a full copy of the data.

B. Subsampled Randomized RtL-HT for H-Tucker Decomposition

The authors extend this logic to the Hierarchical Tucker (H-Tucker) format, specifically the Root-to-Leaves (RtL) algorithm:

Leaf Factors: The leaf factor matrices are computed using the Sub-R-HOSVD method described above.
Internal Nodes: For internal nodes in the dimension tree, the algorithm samples fibers corresponding to the specific mode set of that node, constructs a small matrix, and applies the randomized range-finder to approximate the basis.
Transfer Tensors: Transfer tensors are computed between the approximated bases of parent and child nodes.

3. Key Contributions

True Mode-Parallelism: The paper presents the first practical mode-parallel implementation of Tucker and H-Tucker decompositions that does not require storing $d$ copies of the full tensor. This is achieved by eliminating the need for full matricizations.
Subsampling Strategy: The introduction of a fiber sampling step that bypasses the expensive rearrangement of tensor data into matrices.
Theoretical Error Bounds: The authors derive rigorous probabilistic error bounds for the Sub-R-HOSVD algorithm. They prove that the expected error of the approximation is bounded by a factor dependent on the oversampling parameter and the coherence of the tensor's row space, similar to standard randomized SVD bounds.
Scalability: The method is designed specifically for High-Performance Computing (HPC) environments, demonstrating strong scaling properties.

4. Numerical Results

The authors evaluated their methods on synthetic data and real-world datasets (COIL-100 images and meteorological data) using the Leonardo HPC system (Intel Xeon CPUs and NVIDIA A100 GPUs).

Accuracy: The Sub-R-HOSVD and Sub-R-RtL-HT algorithms achieve approximation errors comparable to deterministic methods (HOSVD, ST-HOSVD) and other randomized baselines (R-HOSVD, SI-HOSVD).
Speed: The proposed methods are consistently one order of magnitude faster than state-of-the-art randomized techniques.
- For synthetic tensors with order $d=8$ , the method achieved speedups of $10\times$ or more.
- Remarkably, the method works with extremely small sampling parameters (e.g., using only 0.00005% of the data columns) without significant loss of accuracy.
Parallel Scaling:
- Tucker: The method showed excellent strong scaling (near-linear speedup) when increasing the number of processes from 1 to 8. The serial component (final TTM) was negligible.
- H-Tucker: While the RtL approach allows parallel computation of all SVDs, the authors noted that load balancing is critical. The serial construction of the root transfer tensor and the varying costs of SVDs at different tree levels can limit speedup if not managed carefully. Parallelizing the fiber index generation further improved performance.
Memory Efficiency: The approach drastically reduces memory footprint, making it feasible to decompose high-order tensors on nodes that cannot hold full matricizations.

5. Significance

This work addresses a critical barrier in tensor numerical linear algebra: the trade-off between parallelism and memory consumption.

Practical Impact: It enables the decomposition of massive, high-dimensional datasets on modern HPC clusters where memory is the primary constraint.
Algorithmic Shift: It moves the paradigm from "randomize the SVD of a full matrix" to "sample the data first, then randomize," which is more efficient for distributed memory systems.
Future Directions: The authors identify the need for a finite precision analysis to explain why their error accumulation scales better with dimension $d$ than deterministic methods, and they call for a formal error analysis of the randomized H-Tucker scheme, which remains an open challenge.

In summary, the paper provides a robust, memory-efficient, and highly scalable solution for tensor decompositions, making advanced data analysis feasible for high-dimensional problems previously considered computationally intractable.