🔢 mathematics

Efficient Sketching-Based Summation of Tucker Tensors

This paper introduces efficient sketching-based methods for summing Tucker tensors that leverage algebraic structures to perform compressed arithmetic directly on factor matrices and core tensors, thereby avoiding large intermediate computations while maintaining high accuracy and reducing computational costs across various numerical applications.

Original authors: Rudi Smith, Mirjeta Pasha, Andrés Galindo-Olarte, Hussam Al Daas, Grey Ballard, Joseph Nakao, Jing-Mei Qiu, William Taitano

Published 2026-03-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Rudi Smith, Mirjeta Pasha, Andrés Galindo-Olarte, Hussam Al Daas, Grey Ballard, Joseph Nakao, Jing-Mei Qiu, William Taitano

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

The Big Problem: The "Pile of Papers" Disaster

Imagine you are a librarian trying to organize a massive library. Instead of books, you are dealing with Tensors. Think of a tensor as a giant, multi-dimensional spreadsheet (a 3D cube, a 4D hyper-cube, etc.) that holds complex data.

In scientific computing (like simulating weather, plasma physics, or quantum mechanics), these "spreadsheets" get so huge that they would fill up every hard drive on Earth. To solve this, scientists use a trick called Tucker Decomposition.

The Analogy:
Instead of storing the whole giant spreadsheet, you store a tiny "Core" (the main idea) and a few "Factor Matrices" (the instructions on how to rebuild the spreadsheet). It's like storing a recipe and a list of ingredients instead of the entire cake. This saves massive amounts of space.

The Bottleneck:
Now, imagine you need to add 100 of these "recipes" together to get a final result.

The Old Way (Deterministic): You take 100 recipes, mix them all together on a giant table, and then try to clean up the mess to make it small again.
The Disaster: When you mix them, the "Core" (the recipe) explodes in size. It grows so big that your computer's memory (RAM) bursts. It's like trying to mix 100 cakes in a single bowl; the bowl shatters, and you lose everything. Even if you throw away the extra mess later, you had to build the mess first, which is too expensive.

The Solution: The "Sketching" Magic Trick

The authors of this paper propose a new way to add these tensors together without ever making the giant mess. They call it Sketching.

The Analogy:
Imagine you have 100 different paintings, and you want to know what the "average" painting looks like without actually gluing them all together on a wall.

The Old Way: You glue them all together, creating a massive, heavy mural. Then you try to cut it down to size.
The New Way (Sketching): You take a quick, blurry photo of each painting from a specific angle. You add up these blurry photos. Because the photos are small and low-resolution, you can add them instantly without running out of space. Then, you use math to reconstruct the "average" painting from those blurry photos.

This is Sketching: compressing high-dimensional data into a lower-dimensional "surrogate" so you can do math on the small version, not the giant one.

How They Did It: The "Structure" Secret

The paper introduces two specific ways to do this sketching, using some fancy math terms that we can simplify:

Khatri-Rao Product (The "Team-Up" Method):
Imagine you have a team of workers. Instead of asking every worker to talk to every other worker (which is chaotic), you pair them up in specific, efficient teams. This method ensures that when you add the tensors, you don't accidentally create a "fat" sketch that is too big. It's great when the data is balanced.
Kronecker Product (The "Grid" Method):
Imagine a grid of lights. This method treats the data like a grid where every light interacts with every other light in a structured way. It's powerful, but if the grid is very lopsided (one side huge, one side tiny), it can get inefficient.

The "Smart" Part:
The authors realized that just guessing how big your "blurry photo" (the sketch) should be is risky. If it's too small, you lose details. If it's too big, you waste time.
They created a Smart Estimator. Before they start sketching, they do a quick "energy check" to see how much information is actually in the data. This tells them exactly how big the sketch needs to be to be accurate but still fast.

Real-World Tests: Where Did They Try It?

The team tested their method on three difficult problems:

The "Cookie" Problem (Parametric PDEs):
Imagine baking cookies where the dough has different ingredients in different spots, and you are testing 100 different recipes at once. The "Cookie" problem is a math simulation of heat flowing through a shape with holes (like a cookie).
- Result: Their method was 11 times faster than the old way and just as accurate. It handled the "lopsided" nature of the data perfectly.
The "Traffic Flow" Problem (Linear Transport):
Imagine tracking millions of particles (like gas molecules) moving through space. You need to add up their movements at every tiny step of time.
- Result: As the simulation got more complex (finer grids, higher accuracy), their method got 30 times faster. The old method would have crashed the computer.
Synthetic Tests:
They made up fake data to prove the math works. Even when adding 100 tensors together, their method stayed fast and didn't lose accuracy.

Why Should You Care?

In the world of supercomputing, time is money and memory is a limit.

Old Way: You hit a wall. You can't solve the problem because the computer runs out of memory when you try to add things up.
New Way: You can solve problems that were previously impossible. You can simulate complex physics, design better materials, or model climate change faster and cheaper.

The Takeaway

This paper is like inventing a new way to do laundry.

Before: You had to wash 100 shirts one by one, dry them, fold them, and then try to stuff them into a suitcase. The suitcase was too small, so you had to buy a bigger one, then a bigger one, until you couldn't fit them all.
Now: You put all 100 shirts in a bag, shake them (sketching) to see how much space they really take up, and then compress them directly into a small, perfect suitcase without ever needing a giant drying room.

The authors have given scientists a "magic suitcase" that allows them to add up massive amounts of complex data without running out of space, making high-level science simulations much faster and more efficient.

1. Problem Statement

The paper addresses a critical bottleneck in large-scale scientific computing involving Tucker tensor decompositions: the efficient summation of multiple tensors while maintaining low-rank structure.

The "Curse of Dimensionality" & Rank Explosion: In iterative algorithms (e.g., GMRES for parametric PDEs or time-stepping for transport equations), tensors must be summed repeatedly. In standard arithmetic, the rank of a sum is the sum of the ranks of its constituents. For $d$ tensors of rank $r$ , the naive sum has rank $dr$.
The Truncation Dilemma: To prevent memory explosion, standard practice involves "rounding" (truncating) the tensor after every addition. However, this creates two major issues:
1. Memory Bottleneck: The intermediate step requires forming a dense core tensor of size $(dr)^N$ (where $N$ is the tensor order) before truncation, which often exceeds available RAM even if the final result is compact.
2. Accuracy Loss: Truncating too frequently (eager rounding) can destroy small but physically significant signals if they are masked by large intermediate noise components that cancel out later in the summation process.
Current Limitations: Existing methods either form these massive intermediate tensors (intractable for high dimensions) or rely on repeated, expensive truncations that degrade accuracy.

2. Methodology

The authors propose a randomized sketching framework that performs summation and truncation implicitly, avoiding the explicit formation of high-rank intermediate tensors. The approach leverages the algebraic structure of Khatri-Rao (KRP) and Kronecker products.

Core Components:

Structure-Preserving Sketching:
Instead of summing full tensors, the method applies random sketching operators directly to the factor matrices of the Tucker decomposition.
- Khatri-Rao Sketching (KRP): Uses the KRP of random matrices to project factor matrices. This allows the sketching operator to be applied to individual factors before the Kronecker product is ever formed.
- Kronecker Sketching: Uses the Kronecker product of random matrices.
- Key Identity: By utilizing identities like $(A \otimes B)(C \odot D) = (AC) \odot (BD)$ , the method computes the sketched unfolding of the sum using only small matrix multiplications, bypassing the $O((dr)^N)$ memory cost.
Effective Rank Estimation (Heuristic):
A critical challenge is determining the optimal sketch dimension (how much to compress). The authors introduce a spectral-based heuristic:
- Construct an energy-weighted concatenation of factor matrices ( $V_n$ ) from all summands.
- Compute the Gram matrix $B_n = V_n^T V_n$ and analyze its eigenvalue decay.
- Estimate the effective rank ( $er_n$ ) by truncating eigenvalues below a relative threshold.
- Determine sketch dimensions ( $s$ ) using a closed-form heuristic that distributes sketching capacity inversely proportional to mode ranks, ensuring high-rank modes are not over-compressed.
Algorithm Workflow:
- Stage 1: Estimate effective ranks and sketch dimensions.
- Stage 2: Generate random test matrices and compute sketched unfoldings of the summands.
- Stage 3: Perform a QR decomposition on the sketched sum to find an orthonormal basis for the sum's principal subspace.
- Stage 4: Project the original summands onto this new basis to form a compressed core tensor.
- Stage 5: Apply a final Sequentially Truncated HOSVD (ST-HOSVD) to ensure the output meets the user-specified tolerance.

3. Key Contributions

Implicit Summation: The primary contribution is an algorithm that merges summation and truncation into a single procedure, eliminating the need to materialize the massive $(dr)^N$ intermediate core tensor.
Algebraic Exploitation: The method uniquely exploits the structure of Kronecker and Khatri-Rao products to apply sketching directly to factor matrices, reducing computational complexity from polynomial in the number of summands ( $d$ ) to linear.
Robust Rank Estimation: The introduction of the energy-weighted Gram matrix heuristic allows for dynamic, data-driven selection of sketch dimensions, preventing both under-sketching (loss of accuracy) and over-sketching (wasted computation).
Theoretical Complexity Analysis: The paper provides a rigorous asymptotic complexity analysis showing that the randomized approach scales as $O(d)$ (linear in summands) compared to the $O(d^{N+1})$ scaling of deterministic methods.

4. Results

The authors validated their approach on four distinct problems:

Synthetic Low-Rank Summation:
- Setup: Summing 100 tensors where the true latent rank is small (10), but the naive rank grows to 1000.
- Result: The sketching methods (KronSum-Tucker and KRPSum-Tucker) were ~100x faster than the deterministic baseline at $d=100$ . Accuracy was preserved at machine precision ( $\sim 10^{-15}$ ).
Synthetic "Eager Rounding" Failure Case:
- Setup: Summing tensors with large, canceling noise components.
- Result: Deterministic "eager rounding" (truncating after every step) catastrophically failed, destroying the underlying signal due to dynamic range shifts (relative error $\sim 1$ ). The sketching methods preserved the signal perfectly (error $\sim 10^{-11}$ ) while avoiding the intermediate rank swelling.
Parametric "Cookie" Problem (Elliptic PDE):
- Setup: Solving a parameter-dependent heat equation with 4 parameters using Tucker-GMRES.
- Result: KRPSum-Tucker achieved up to 11x speedup over the deterministic baseline with high accuracy ( $10^{-5}$ ).
- Observation: Kronecker sketching struggled here due to highly skewed mode dimensions (spatial vs. parameter), highlighting the need for the KRP approach in such geometries.
1D Linear Transport Problem (NDG):
- Setup: Solving a kinetic transport equation using Nodal Discontinuous Galerkin (NDG) methods, requiring repeated tensor summation.
- Result: The sketching methods provided 5x to 30x speedups depending on the basis order and parameter grid resolution, with no loss in convergence order or accuracy.

5. Significance

Scalability: This work enables the solution of high-dimensional problems (e.g., parametric PDEs, kinetic equations) that were previously intractable due to memory constraints during iterative tensor operations.
Accuracy Preservation: By avoiding intermediate truncation, the method prevents the accumulation of rounding errors and the loss of small-scale physical features, which is crucial for long-time simulations.
General Applicability: The framework is applicable to any domain relying on Tucker decompositions and iterative linear solvers, including quantum computing, signal processing, and machine learning.
Practical Impact: The results demonstrate that randomized numerical linear algebra (RandNLA) can be effectively adapted to structured tensor arithmetic, offering a viable path forward for exascale computing applications involving high-dimensional data.