🔢 mathematics

Randomized Tucker-Sketched GMRES

This paper proposes two randomized sketched GMRES algorithms, RHOSVD-Tucker sGMRES and MLN-Tucker sGMRES, to efficiently solve large-scale tensor-structured linear systems by preventing the unbounded growth of multilinear ranks in Krylov basis vectors, thereby enabling memory-efficient and stable solutions for inverse problems.

Original authors: Alberto Bucci, Martina Iannacito, Mirjeta Pasha, Rudi Smith

Published 2026-08-12

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Alberto Bucci, Martina Iannacito, Mirjeta Pasha, Rudi Smith

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 are trying to solve a massive, multi-dimensional puzzle. In the world of science and engineering, these puzzles often come in the form of "tensors"—think of them as hyper-cubes of data that stretch across many directions at once, far beyond the flat sheets of a spreadsheet or the simple columns of a database. These tensors are the secret language of everything from simulating how quantum particles dance to reconstructing blurry medical images. But here's the catch: as you add more dimensions to your puzzle, the number of pieces explodes. A 3D image might be manageable, but a 4D or 5D version can contain so much data that it would fill up every hard drive on Earth. This is the "curse of dimensionality."

To tame these giants, scientists use a trick called "low-rank approximation." Imagine trying to describe a complex painting not by listing the color of every single pixel, but by describing a few brushstrokes and how they combine. This compresses the data, making it possible to crunch the numbers. However, when you try to solve these puzzles using a popular method called GMRES (a step-by-step detective that builds a list of clues), something weird happens. Every time the detective adds a new clue to their list, the "complexity" of that clue grows. The detective's notebook starts filling up with increasingly complicated descriptions until, eventually, the notebook becomes too heavy to carry, and the computer runs out of memory. The detective gets stuck, unable to solve the case because they are drowning in their own notes.

This paper introduces a clever new way to keep the detective's notebook light and manageable. The authors, a team of mathematicians from the UK and the US, propose two new "sketched" algorithms. Instead of writing down the full, heavy description of every clue, these new methods take a quick, randomized "snapshot" or "sketch" of each clue. It's like taking a photo of a complex sculpture instead of measuring every curve with a ruler. By using these snapshots, the detective can solve the puzzle much faster and with far less memory. They tested these methods on three different types of problems: a classic physics equation (the Poisson equation), a tricky fluid flow problem (convection-diffusion), and a real-world image deblurring task. In every case, their new "snapshot" detectives solved the problems more efficiently than the old, heavy-handed methods, and in the image deblurring case, the act of taking the snapshot itself helped clean up the noise, acting like a built-in filter to reveal the true picture.

The Problem: The Detective's Overloaded Notebook

Imagine you are a detective trying to solve a mystery by building a "Krylov subspace." In plain English, this is just a growing list of clues. You start with one clue, then use a rule (the linear operator) to generate a second clue, then a third, and so on. To find the solution, you need to make sure all these clues are different from each other—a process called "orthogonalization."

In the world of tensors (multi-dimensional data), this process hits a wall. As you add more clues to your list, the mathematical "rank" of each clue (a measure of its complexity) tends to grow. It's like trying to describe a simple shape, but every time you add a new detail, the shape becomes a fractal with infinite layers. Soon, your computer's memory is completely filled with these increasingly complex descriptions, and the process grinds to a halt. This is the fundamental bottleneck the paper addresses: standard methods get too heavy to carry.

The Solution: Taking Snapshots Instead of Measurements

The authors propose two new strategies to solve this, both based on a concept called "sketching." Instead of keeping the full, heavy description of every clue, they take a compressed, randomized "sketch" of it. Think of it like this: if you wanted to compare two huge paintings, you wouldn't measure every pixel. Instead, you might take a quick photo of each with a slightly blurry camera and compare the photos. If the photos are similar enough, you know the paintings are similar. This saves a massive amount of time and space.

The paper introduces two specific ways to do this for tensor puzzles:

1. The "Smart Estimator" (RHOSVD-Tucker sGMRES)
This method uses a technique called Randomized Higher-Order Singular Value Decomposition (RHOSVD). Imagine you have a stack of complex 3D blocks. Instead of trying to count every single block, you shake the stack and look at how the light passes through it to guess how many blocks are really there. This method is "adaptive," meaning it figures out on the fly how much detail it needs to keep. It's robust and works well for a wide variety of problems, but it still keeps a full list of the clues, just with a smarter way of compressing them.

2. The "Streaming Streamer" (MLN-Tucker sGMRES)
This is the more radical approach. It uses something called the "Multilinear Nyström" approximation. Imagine a conveyor belt bringing in clues one by one. Instead of storing every single clue in a giant warehouse, this method takes a quick snapshot of the clue, does its math, and then throws the heavy original away, keeping only the tiny snapshot. It's "streamable," meaning it can handle a never-ending stream of data without running out of memory.

The Magic Trick: The authors found that the "snapshot" needed to solve the math problem is actually a free bonus that comes with the compression process. They don't need to take a second photo; the first one does the job twice.
Memory Saving: They even added a "memory-efficient" mode. If the computer is really low on space, it can throw away even more of the snapshot details, keeping only the most essential parts, without ruining the final answer.

The Results: Faster, Lighter, and Cleaner

The team tested these new detectives on three different challenges:

The Physics Puzzle (Poisson Equation): They solved a 3D heat equation. The new methods were faster and more robust than the old standard methods, especially when they needed very high precision.
The Fluid Puzzle (Convection-Diffusion): This is a trickier, non-symmetric problem where the clues don't behave as nicely. Here, the "streaming" method (MLN) shined. It managed to solve the problem in about half the time of the old methods, using significantly less memory. Even when they forced the old methods to use fewer "clues" to save memory, the new methods still performed better.
The Image Deblurring Mystery: This was the most exciting test. They tried to take a blurry, noisy 3D image (like a video of a hollow bar phantom) and make it sharp.
- The Surprise: The act of compressing the blurry image into a low-rank format (taking the snapshot) actually acted as a "regularizer." In simple terms, the compression naturally threw away the high-frequency noise (the grainy static) while keeping the important details. It was like the detective's camera lens naturally filtering out the fog.
- The Result: By combining this natural filtering with a smart mathematical adjustment (Tikhonov regularization), they could reconstruct the image clearly without needing to know exactly how much noise was in the picture beforehand. The new methods produced stable, clear images where the old methods would have failed or produced garbage.

Why It Matters

The paper shows that you don't need to carry the whole world in your backpack to solve a big problem. By using randomized "snapshots" and smart compression, you can solve massive, multi-dimensional puzzles that were previously impossible due to memory limits. The authors demonstrated that these methods are not just theoretical; they work in real simulations, solving problems in seconds that would take minutes or hours for older methods, and they do it while using a fraction of the computer memory.

Most importantly, for inverse problems like image deblurring, they showed that the compression itself is a powerful tool for cleaning up data. This suggests a new way to handle noisy, messy real-world data: don't just try to measure everything perfectly; compress it smartly, and the noise might just disappear on its own.

Technical Summary: Randomized Tucker-Sketched GMRES

Problem Statement

The paper addresses the challenge of solving large-scale linear tensor equations of the form $\mathcal{L}(\mathcal{X}) = \mathcal{B}$ , where $\mathcal{X}$ and $\mathcal{B}$ are $d$ -dimensional tensors and $\mathcal{L}$ is a linear operator expressible as a sum of separable terms (Kronecker products). Such equations arise in high-dimensional PDE discretizations, quantum simulations, uncertainty quantification, and inverse problems like image deblurring.

Standard iterative solvers, particularly the Generalized Minimal RESidual (GMRES) method, face a fundamental bottleneck when applied to tensor-structured systems: the rank growth of Krylov basis vectors. As iterations proceed, the multilinear ranks of the basis tensors increase, causing the computational cost of orthogonalization and storage requirements to explode, often rendering the method intractable for problems with millions of unknowns. While low-rank formats like Tucker decomposition are used to mitigate storage, the accumulation of rank during the Arnoldi process and the need for full orthogonalization remain prohibitive.

Methodology

The authors propose two novel randomized algorithms within the sketched GMRES (sGMRES) framework, specifically adapted for the Tucker tensor format. These methods replace the expensive full Arnoldi orthogonalization with short recurrences and utilize randomized projections to approximate the solution.

1. RHOSVD-Tucker sGMRES

This method extends the existing RHOSVD-Tucker GMRES approach [72] by integrating it into the sGMRES architecture.

Mechanism: It employs Randomized Higher-Order Singular Value Decomposition (RHOSVD) combined with a Khatri-Rao structured sketching technique (RoundSum) to handle tensor summations and operator applications efficiently without forming dense intermediates.
Orthogonalization: Instead of full orthogonalization, it uses a short-recurrence strategy, orthogonalizing the new basis vector only against the $k_{trunc}$ most recent basis vectors.
Rank Handling: It utilizes an adaptive heuristic to estimate the effective rank of the sum at each iteration, dynamically determining the sketch size to balance accuracy and cost.
Residual Tracking: Since the basis is not fully orthogonal, the standard least-squares problem is replaced by a sketched least-squares problem. A correction factor is introduced to the stopping criterion to prevent premature termination due to residual underestimation.

2. MLN-Tucker sGMRES

This method leverages the Multilinear Nyström (MLN) approximation, offering a distinct approach focused on streamability and fixed-rank constraints.

Mechanism: It uses a streamable Tucker compression strategy where the full Krylov basis is never stored. Instead, only the "sketches" (compact representations) of the basis tensors are retained.
Fixed Rank: Unlike the adaptive approach, this method fixes the target rank $r$ and sketch size $r+p$ a priori. This fixed-rank constraint acts as an implicit regularizer, restricting iterates to a manifold of bounded multilinear rank and suppressing high-frequency noise.
Efficiency: The Khatri-Rao sketching required for the sGMRES least-squares problem is obtained as a byproduct of the MLN compression phase, incurring no additional cost.
Memory Efficiency: A specific variant allows for the downsampling of stored sketches based on the expected solution rank ( $r_{sol}$ ), significantly reducing memory footprint for long iterations without altering convergence behavior.

Regularization for Inverse Problems

For ill-posed inverse problems (e.g., image deblurring), the authors incorporate adaptive projected Tikhonov regularization directly into the Krylov iteration.

The regularization parameter $\lambda_k$ is selected automatically at each iteration using Generalized Cross-Validation (GCV).
This approach eliminates the need for oracle-based stopping criteria and provides stable reconstructions even when the noise level is unknown.
The low-rank Tucker constraint itself serves as an implicit regularizer, while the explicit Tikhonov penalty handles residual noise amplification.

Key Contributions

Algorithmic Innovation: The introduction of two Tucker-based sGMRES variants (RHOSVD-Tucker and MLN-Tucker) that overcome the rank-growth and memory bottlenecks of standard tensor GMRES.
Memory Efficiency: The MLN-Tucker sGMRES method enables streaming computations by storing only sketches of older basis vectors, allowing for higher iteration counts or larger ranks within fixed memory budgets.
Implicit Regularization: The paper demonstrates that the fixed-rank constraint in the MLN approach, combined with data compression, acts as an effective implicit regularizer for inverse problems.
Adaptive Parameter Selection: The integration of automatic GCV-based parameter selection for Tikhonov regularization within the randomized Krylov framework.
Benchmarking: Comprehensive numerical experiments comparing the proposed methods against state-of-the-art solvers (RHOSVD-Tucker GMRES, TK-SS-SD) on symmetric (Poisson), non-symmetric (convection-diffusion), and inverse (image deblurring) problems.

Results

The numerical experiments, conducted on a 3D Poisson equation, a 3D convection-diffusion problem, and a 3D image deblurring inverse problem, yield the following findings:

Performance: Both proposed methods outperform standard low-rank Tucker solvers in terms of computational time and memory usage.
Symmetric vs. Non-Symmetric: In symmetric settings (Poisson), the methods are competitive with or faster than specialized Conjugate Gradient (CG) variants. In non-symmetric settings (convection-diffusion), they demonstrate robust convergence where standard methods struggle with rank accumulation.
Inverse Problems: In the image deblurring task, the methods successfully reconstruct the solution from noisy data. The combination of low-rank compression and adaptive Tikhonov regularization yields stable reconstructions with monotonic error reduction, avoiding the semi-convergence typical of unregularized iterative methods.
Memory Savings: The MLN-Tucker sGMRES (Memory Efficient) variant achieves substantial memory reductions (e.g., storing only sketches of size $r_{sol}$ instead of full sketches) while maintaining accuracy comparable to the full-resolution version.

Significance and Claims

The paper claims to be the first work to demonstrate that compressed tensor decompositions can serve as an effective regularizer in the context of iterative methods for inverse problems. It highlights that the interplay between explicit Tikhonov penalization and implicit low-rank truncation creates a framework particularly well-suited for large-scale, ill-posed tensor inverse problems.

Furthermore, the authors emphasize that the sGMRES architecture simultaneously addresses the dual bottlenecks of memory storage and orthogonalization costs that have historically limited the application of Krylov subspace methods to high-dimensional tensor equations. By replacing full orthogonalization with short recurrences and utilizing randomized projections, the proposed methods make previously intractable large-scale tensor problems computationally accessible.