🔢 mathematics

Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration

This paper introduces the Randomized Tensor Global GMRES (RTG-GMRES) method, which utilizes sketched Einstein products and mode-wise random projections to efficiently solve large-scale multilinear systems for image and video restoration by significantly reducing the computational cost of orthogonalization while maintaining convergence.

Original authors: Achraf Badahmane

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Achraf Badahmane

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 are trying to restore a beautiful, old family photo that has been smudged by rain and covered in static noise. Or perhaps you are trying to fix a blurry, shaky video of a soccer game. This is what Image and Video Restoration is all about: taking a messy, damaged picture and using math to guess what the original, perfect one looked like.

For a long time, computers have tried to solve this by turning the picture into a giant, flat list of numbers (like unrolling a 3D ball of yarn into a single long string). But this destroys the natural structure of the image (like forgetting that the red channel is separate from the blue channel) and makes the math incredibly slow and heavy.

This paper introduces a clever new way to do this math faster, using a concept called "Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product."

That is a mouthful! Let's break it down into a simple story with analogies.

1. The Problem: The "Giant Library" Analogy

Imagine your image is a massive, multi-story library.

The Old Way (Classical Methods): To find a specific book (the solution), a librarian has to walk through every single aisle on every single floor, checking every single book to make sure they are organizing them perfectly. This is accurate, but it takes forever. If the library is huge (like a 4K video), the librarian gets exhausted before they even finish the first floor.
The "Tensor" Part: Instead of unrolling the library into a long hallway, this paper keeps the library as a 3D building. It respects the floors, the wings, and the sections. This is much more efficient, but checking every book in the 3D building is still too slow.

2. The Solution: The "Sketching" Shortcut

The authors propose a new method called "Sketching."

Imagine you are a detective trying to solve a crime in that giant library. Instead of interviewing every single person in the building, you hire a team of random sketch artists.

These artists don't look at everyone. They quickly glance at random groups of people and draw a rough, quick "sketch" of the crowd's general vibe.
The Magic: Even though the sketches are small and rough, they capture the essential shape of the crowd. You can solve your mystery using these small sketches instead of interviewing thousands of people.

In the paper, this is the "Randomized Sketching." It takes the giant, complex math problem and projects it onto a much smaller, simpler version of itself. It's like taking a high-resolution photo and shrinking it down to a thumbnail to do your calculations, then zooming back out to get the result.

3. The "Einstein Product": The Special Glue

To make this work with 3D images (like color photos or videos), the math needs a special way to multiply things together.

Standard Math: Usually treats everything as a flat sheet.
Einstein Product: Think of this as a special 3D glue. It allows the computer to multiply the image layers (Red, Green, Blue, and time for video) together in a way that keeps their 3D relationships intact. It ensures that the "Red" part of the image stays connected to the "Red" part of the blur, rather than getting mixed up with the "Blue."

4. The New Algorithm: The "Fast-Forward" Button

The paper combines these ideas into a new algorithm (called RTG-GMRES).

How it works: Instead of walking through the whole library (the full math), the algorithm uses the "sketch artists" (random projections) to build a tiny, manageable model of the library.
The Result: It solves the restoration problem on this tiny model. Because the model is so small, the computer finishes the job in seconds instead of minutes.
Does it lose quality? Surprisingly, no. The paper proves that even though we are using "sketches," the final restored image is just as sharp and clear as if we had done the slow, full calculation. In fact, in their tests, the "sketch" method was often faster and produced slightly better results because it avoided getting stuck in the noise.

The Real-World Impact

Why should you care?

Faster Restoration: If you have a blurry video from a security camera or a damaged old home movie, this method can fix it in half the time.
Better Quality: It handles "ill-posed" problems (where the damage is so bad the answer isn't obvious) very well, using a technique called Tikhonov Regularization (think of this as a "stabilizer" that prevents the computer from guessing wild, crazy solutions).
Efficiency: It saves battery life on your laptop and allows scientists to process huge datasets (like satellite images or medical scans) that were previously too slow to handle.

Summary

The authors of this paper invented a smart shortcut. They realized that to fix a blurry, noisy 3D image, you don't need to do every single calculation perfectly. You just need to do a few "random sketches" of the math that capture the most important parts.

The Analogy:

Old Way: Reading every page of every book in a library to find a quote.
New Way: Asking a group of random people to summarize the books, then finding the quote in their summaries.
Outcome: You get the quote just as fast, but you spent 60% less time doing it.

This makes restoring our precious memories (photos and videos) faster, cheaper, and more accessible for everyone.

1. Problem Statement

The paper addresses the challenge of solving large-scale multilinear systems arising in image and video restoration (e.g., deblurring, denoising). These problems are modeled as linear tensor equations of the form:
$\Phi(X) = C$
or the least-squares variant:
$\min_X \| \Phi(X) - C \|_F$
where:

$X$ is the unknown high-dimensional tensor (e.g., a color image or video sequence).
$C$ is the observed degraded data.
$\Phi$ is a linear tensor operator (often involving blurring or subsampling) defined via the Einstein product ( $*_N$ ).

The Core Challenge:
Classical tensor Krylov subspace methods (like Tensor Global GMRES or Golub–Kahan) rely on the Frobenius inner product and full orthogonalization. For high-order tensors (e.g., $N \times N \times 3$ for RGB images or higher dimensions for video), the computational cost of orthogonalization and inner product calculations becomes prohibitive due to the massive dimensionality ( $n = \prod I_k$ ). Furthermore, vectorizing these tensors destroys their intrinsic multidimensional structure, leading to memory bottlenecks.

2. Methodology

The authors propose a Randomized Tensor Krylov Subspace Method that integrates sketching (randomized dimensionality reduction) directly into the Einstein product framework.

A. Sketched Einstein Inner Product

Instead of computing the exact Frobenius inner product $\langle X, Y \rangle_F$ , the method introduces a sketched inner product $\langle X, Y \rangle_\Theta$ :
$\langle X, Y \rangle_\Theta = \langle S(X), S(Y) \rangle_F$
where $S(\cdot)$ is a random tensor embedding operator.

Mechanism: The operator $S$ applies random projection matrices ( $\Theta_k$ ) mode-wise to the tensor $X$ , compressing it into a lower-dimensional space while preserving the subspace geometry with high probability.
Theoretical Guarantee: Under the assumption of $\epsilon$ -subspace embedding, the sketched product approximates the true inner product such that:
$(1-\epsilon)\|X\|_F^2 \leq \|S(X)\|_F^2 \leq (1+\epsilon)\|X\|_F^2$
This ensures that singular values and orthogonality are preserved within a bounded error.

B. Randomized Tensor Global Arnoldi Process

The paper develops a Sketched Global Arnoldi algorithm to construct an orthonormal basis for the tensor Krylov subspace.

Process: In each iteration, the tensor operator $\Phi$ is applied, and the result is immediately sketched ( $S(\Phi(V_j))$ ).
Orthogonalization: The Gram-Schmidt process uses the sketched inner product $\langle \cdot, \cdot \rangle_\Theta$ instead of the Frobenius product.
Result: This generates a reduced Hessenberg matrix $\tilde{H}_m$ that approximates the action of $\Phi$ on the subspace, significantly lowering the cost of tensor-tensor products and orthogonalization.

C. Sketched Tikhonov Regularization

To handle ill-posed problems (noise), the method incorporates Tikhonov regularization within the reduced subspace:
$\min_y \| \beta e_{m+1} - \tilde{H}_m y \|_2^2 + \mu \|y\|_2^2$
The regularization parameter $\mu$ is selected using Generalized Cross-Validation (GCV) on the small projected problem, avoiding the need to solve the full high-dimensional system.

D. Block Algorithms

The framework is extended to Block Krylov Subspace Methods, specifically:

Sketched Einstein Block GMRES: For solving linear tensor equations.
Sketched Einstein Block Golub–Kahan: For solving least-squares problems (bidiagonalization).
Both algorithms utilize the sketched inner product for all orthogonality checks and norm computations.

3. Key Contributions

Novel Framework: Introduction of the Randomized Tensor Global GMRES (RTG-GMRES) and Sketched Block Golub–Kahan methods, which are the first to combine Einstein products with randomized sketching for tensor equations.
Complexity Reduction: The method drastically reduces the computational complexity of orthogonalization and inner product calculations by projecting tensors into lower-dimensional spaces without vectorization.
Theoretical Analysis: The paper provides rigorous proofs for:
- Tensor Subspace Embedding: Establishing bounds on the approximation error of the sketched inner product.
- Singular Value Bounds: Proving that the singular values of the sketched tensor unfoldings remain close to the original.
- Residual Bounds: Deriving error bounds for the projected Tikhonov solution.
Preservation of Structure: Unlike vectorization-based methods, this approach preserves the multilinear structure of the data (e.g., spatial and channel correlations in images), leading to more accurate modeling.

4. Numerical Results

The methods were tested on RGB image deblurring and video restoration tasks under Gaussian blur and additive Gaussian noise.

Performance Metrics: Relative Error (RE) and Peak Signal-to-Noise Ratio (PSNR).
Comparison: The proposed sketched methods were compared against classical Tensor GKB (without sketching) and standard Einstein Block GMRES.
Findings:
- Accuracy: The sketched methods achieved comparable or slightly better PSNR and Relative Error compared to non-sketched methods. For example, at a noise level of $10^{-3}$ , Sketched Block Golub-Kahan achieved a PSNR of 24.42 vs. 24.22 for Classical GKB.
- Efficiency: The most significant gain was in CPU time. Sketched methods reduced computation time by 40–60%.
  - Example: Sketched Block Golub-Kahan took 3.32s vs. 18.45s for Classical GKB at low noise levels.
- Scalability: The speed-up was consistent across different noise levels, making the method highly suitable for large-scale, time-sensitive applications.

5. Significance

This paper presents a breakthrough in large-scale tensor computations for imaging applications.

Practical Impact: It enables the restoration of high-resolution color images and video sequences that were previously computationally intractable due to memory and time constraints.
Algorithmic Innovation: By successfully integrating randomized sketching with tensor algebra, the authors demonstrate that one can sacrifice a negligible amount of precision (controlled by $\epsilon$ ) to gain massive computational efficiency.
Future Applications: The framework is not limited to image restoration; it offers a generalizable tool for solving high-dimensional PDEs, hyperspectral imaging, and other multidimensional inverse problems where preserving tensor structure is critical.

In conclusion, the proposed Sketched Einstein Block Krylov methods offer an excellent trade-off between efficiency and accuracy, providing a robust, scalable solution for modern multidimensional data restoration challenges.