🔢 mathematics

A Two-Sided Sketching Algorithm for Low-rank Tensor Train Approximation

This paper proposes a randomized, one-pass sketching algorithm combined with subspace iteration to efficiently compute low-rank Tensor Train approximations, providing rigorous error bounds and demonstrating superior performance on both synthetic and real-world datasets.

Original authors: Gaohang Yu, Yihao Pan, Ailun Jian, Xiaohao Cai

Published 2026-06-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Gaohang Yu, Yihao Pan, Ailun Jian, Xiaohao Cai

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. In the world of mathematics, this is called a tensor. Think of it not just as a flat sheet of paper (a matrix), but as a giant, complex 3D block of information, or even a 4D or 5D hyper-block. These blocks are so huge that trying to read every single page (every number) takes forever and requires a computer with a brain the size of a small city.

However, most of these giant blocks aren't actually full of unique, random information. They have a hidden, simpler structure underneath, like a complex sculpture that is actually made of just a few repeating shapes. Mathematicians call this a low-rank structure. The goal is to find a way to describe this giant block using only those few essential shapes, ignoring the rest. This is called Tensor Train (TT) approximation.

The Problem: The "Heavy Lifting" Bottleneck

Traditionally, to find these hidden shapes, computers use a method called TT-SVD. Imagine trying to organize a library by taking every single book out, reading the entire text of every book, and then re-shelving them. It's accurate, but it's incredibly slow and requires you to hold the entire library in your memory at once. If the library is too big to fit in your memory, this method breaks down.

The Solution: The "Sketching" Shortcut

The authors of this paper propose a new, smarter way to do this called TT-subSKETCH.

Think of Sketching like taking a quick, blurry photo of a crowd to guess how many people are there, rather than counting every single face. Instead of reading every number in the giant data block, the algorithm takes a few "snapshots" (random linear combinations) of the data. This compresses the data into a much smaller, manageable size very quickly.

However, a simple snapshot isn't always perfect. If the data has some "fuzzy" edges (mathematically, slow-decaying singular values), a quick sketch might miss the important details.

The Secret Sauce: "Power Iteration" (The Polishing Step)

To fix the fuzziness, the authors add a step called Subspace Power Iteration.

The Analogy: Imagine you are trying to find the most important voices in a noisy room. A simple sketch is like taking a quick listen. Power iteration is like asking the room to repeat the most important voices a few times. Each time they repeat, the important voices get louder and the background noise gets quieter.
By repeating this "listening" process a few times (controlled by a parameter called $q$ ), the algorithm sharpens the focus on the most important parts of the data, making the final result much more accurate.

The "Two-Sided" Trick

The paper introduces a Two-Sided Sketching technique.

One-Sided: Imagine trying to guess the shape of a statue by only looking at it from the front. You might miss the back.
Two-Sided: The new algorithm looks at the data from both sides simultaneously (using two different random "cameras" or sketches). This ensures that no important information is missed from any angle, even if the data is too big to fit in the computer's memory all at once. It allows the computer to process the data in a single pass, like a conveyor belt, without needing to stop and reload the whole thing.

What Did They Prove?

The authors didn't just build the tool; they proved it works:

Accuracy: They mathematically showed that even with these shortcuts, the error (the difference between the original giant block and their simplified version) stays very small.
Robustness: They proved the method works even if the data is "noisy" (like a photo with static or grain). Even with garbage mixed in, the algorithm can still find the true structure.
Speed: In their experiments, they tested this on synthetic data (made-up numbers) and real-world data (like hyperspectral images of the earth and color videos of cars).
- Result: Their method was much faster than the traditional "read-everything" method (TT-SVD).
- Result: It was more accurate than other fast "random" methods that don't use the "polishing" (power iteration) step.

The Bottom Line

The paper presents a new algorithm, TT-subSKETCH, that acts like a high-speed, high-precision scanner for massive data blocks. It uses a "two-sided sketch" to compress the data quickly and a "polishing" step to ensure the details aren't lost. It allows computers to handle data that is too big to fit in memory, doing it faster than old methods while keeping the results just as accurate.

Technical Summary: A Two-Sided Sketching Algorithm for Low-Rank Tensor-Train Approximation

Problem Statement
Tensor Train (TT) decomposition is a robust method for representing high-dimensional tensors with low-rank structures, finding applications in machine learning, graph analysis, and signal processing. However, the standard deterministic approach, TT-SVD, relies on computing Singular Value Decompositions (SVDs) of large-scale auxiliary unfolding matrices at each step. This process is computationally expensive, often becoming a bottleneck for large datasets. While randomized methods (such as TT-rSVD) have been proposed to accelerate this process, they typically require multiple passes over the data or struggle with matrices exhibiting slow singular value decay. Furthermore, existing randomized approaches often lack rigorous error bounds when applied to noisy data or when constrained to a single pass over the data (streaming scenarios).

Methodology
The authors propose TT-subSKETCH, a randomized algorithm designed to compute low-rank TT approximations efficiently. The methodology integrates three core components:

Two-Sided Sketching: To address the "one-pass" constraint where data cannot be stored entirely in core memory, the algorithm employs a two-sided sketching technique. This involves generating random Gaussian matrices ( $\Omega$ and $\Psi$ ) to project the data from both the row and column spaces, allowing for low-rank approximation without revisiting the original data.
Subspace Power Iteration: To mitigate the issue of slow singular value decay and improve approximation accuracy, the algorithm incorporates subspace power iteration ( $q$ iterations). This step enhances the decay rate of singular values, reducing the "tail energy" of the matrix.
Iterative TT Decomposition: The algorithm applies the sketching and power iteration steps sequentially to the unfolding matrices of the tensor ( $A^{(k)}$ ) from $k=1$ to $d-1$ . At each step, it computes the core tensor $G_k$ and updates the residual tensor for the next iteration.

The algorithm is parameterized by the target TT-rank $r$ , sketch size $l$ , oversampling parameter $p$ , and the number of power iterations $q$ . When $q=0$ , the method reduces to a one-pass sketching algorithm (TT-SKETCH).

Key Contributions

Algorithmic Proposal: The paper introduces TT-subSKETCH, which combines two-sided sketching with subspace power iteration specifically for TT decomposition.
Theoretical Error Bounds:
- The authors derive an expected spectral error bound for the algorithm in the noise-free setting (Theorem 3.1 and 3.2). This bound explicitly relates the approximation error to the tail energy of the unfolding matrices and the number of power iterations.
- A robustness analysis is provided for noisy settings (Theorem 3.3). The paper establishes high-probability error bounds for TT-subSKETCH when the input tensor is corrupted by arbitrary deterministic noise, generalizing previous results from t-product tensors to the TT format.
Complexity Analysis: The computational cost is shown to scale as $O((q+1)r^2 n^d)$ , which offers a substantial theoretical speedup over the $O(n^{d+1})$ complexity of deterministic TT-SVD in typical low-rank scenarios where $r \ll n$ .

Experimental Results
Numerical experiments were conducted on both synthetic data (power function tensors) and real-world datasets (hyperspectral images and color videos), comparing TT-subSKETCH against TT-SVD (deterministic) and TT-rSVD (randomized).

Efficiency: TT-subSKETCH (particularly with $q=1$ or $q=2$ ) demonstrated significantly lower CPU times compared to TT-SVD, often by an order of magnitude, while maintaining comparable accuracy.
Accuracy: In terms of relative error and Peak Signal-to-Noise Ratio (PSNR), TT-subSKETCH with power iteration ( $q \ge 1$ ) achieved results very close to the deterministic TT-SVD, significantly outperforming TT-rSVD and the basic one-pass sketching (TT-SKETCH).
Robustness: Experiments with added Gaussian white noise showed that TT-subSKETCH2 ( $q=2$ ) maintained high approximation quality (high PSNR, low relative error) even in noisy conditions, closely matching the performance of TT-SVD but with much faster execution.

Significance
The paper claims that TT-subSKETCH offers a superior balance between computational efficiency and approximation accuracy for large-scale tensor data. By integrating two-sided sketching with power iteration, the algorithm effectively handles the "curse of dimensionality" and the computational burden of SVDs. The authors emphasize that their method is particularly valuable for scenarios where data is too large to be stored in memory (requiring one-pass processing) or when data is noisy. The provided theoretical error bounds and robustness analysis offer a rigorous foundation for the algorithm's reliability, distinguishing it from heuristic randomized approaches.