🔢 mathematics

A Tensor Greedy Double-Block Extended Kaczmarz Method for Inconsistent Tensor Linear Systems under the t-product

This paper proposes the Tensor Greedy Double Block Extended Kaczmarz (TGDBEK) method, a novel iterative algorithm that dynamically selects active tensor slices based on residual norms to efficiently solve large-scale inconsistent tensor linear systems under the t-product, demonstrating superior convergence and performance over existing state-of-the-art solvers in both synthetic benchmarks and real-world image deblurring applications.

Original authors: Jérémie Mabiala, Lionel Tondji

Published 2026-09-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jérémie Mabiala, Lionel Tondji

Original paper licensed under CC BY 4.0 (https://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

In the world of modern computing, data rarely comes in neat, flat lists. Instead, it arrives in complex, multi-layered structures: a color photograph is not just a grid of numbers, but a stack of grids representing red, green, and blue light; a medical scan is a volume of slices showing the inside of a body. To make sense of this rich information, scientists use a mathematical framework called the "t-product." Think of this as a specialized set of rules that allows computers to treat these multi-layered data blocks as single, unified objects, much like how we handle individual numbers or simple lists, but with the ability to capture the depth and relationships inherent in three-dimensional data. This approach has become essential for tasks ranging from restoring damaged images to analyzing massive datasets in machine learning.

However, real-world data is rarely perfect. It is often corrupted by noise, missing pieces, or errors introduced during measurement. When scientists try to reverse-engineer the original, clean data from this messy input, they face a difficult mathematical puzzle known as an "inconsistent system." In simpler terms, the equations describing the data do not have a single, perfect solution because the input contains contradictions. Traditional methods for solving these puzzles often work by taking small, random steps, checking one piece of the data at a time and adjusting the answer slightly. While reliable, this step-by-step approach can be incredibly slow, especially when the data is massive, leaving researchers waiting for hours or days for a result that might still be imprecise.

A team of researchers at the African Institute for Mathematical Sciences in Senegal, along with a collaborator from Germany, has developed a new strategy to speed up this process significantly. They introduced a method called the Tensor Greedy Double-Block Extended Kaczmarz method. To understand how it works, imagine a team of workers trying to fix a large, damaged mosaic. Older methods might have the workers pick tiles at random, or follow a fixed, pre-determined order, checking one tile after another. If a tile is heavily damaged, the workers might spend too much time on it, or worse, ignore the most critical errors until the very end. The new method changes the workflow entirely. Instead of picking randomly or following a rigid schedule, the algorithm constantly scans the entire mosaic to find the areas with the most severe damage—the "largest errors." It then groups these critical areas together into dynamic blocks and fixes them all at once.

The researchers call this a "greedy" approach because the algorithm is eager to tackle the biggest problems first. It does not rely on a static map of which tiles to fix; instead, it builds a new plan at every single step based on where the current errors are largest. This allows the system to adapt instantly to the specific shape of the problem. The method also works on two fronts simultaneously: it corrects the data itself while also refining the underlying rules used to interpret that data. By focusing its computational power only on the most informative parts of the data at any given moment, the algorithm avoids wasting time on areas that are already close to being correct.

To test their idea, the researchers ran extensive simulations using both synthetic data and real-world problems. They applied their method to dense mathematical systems, sparse data sets from a large public collection, and practical image restoration tasks. In one experiment involving color image deblurring, where a flower photograph was artificially blurred and filled with noise, the new method was the only one capable of reaching a high level of accuracy within a set time limit. While other methods ran for a thousand steps and still failed to clear the image, the new approach solved the problem in just over five hundred steps. In another test involving a three-dimensional model of a brain scan, the method achieved the same high-quality reconstruction as the best existing techniques but did so in less time.

The results were consistent across different types of data. When solving large, complex systems, the new method required significantly fewer steps to reach a solution compared to the current state-of-the-art techniques. In many cases, it reduced the number of steps needed by a factor of five and cut the total computing time by more than half. The researchers also explored how a specific control setting, which determines how many error groups are fixed at once, affects performance. They found that keeping this setting within a specific range allowed the method to balance speed and efficiency perfectly, avoiding the pitfalls of being too aggressive or too cautious.

This work demonstrates that by shifting from a random or fixed approach to a dynamic, error-focused strategy, it is possible to solve difficult data problems much faster. The method does not just offer a slight improvement; it fundamentally changes how the computer prioritizes its work, ensuring that every calculation contributes directly to eliminating the most significant errors. For fields that rely on processing massive amounts of multi-dimensional data, such as medical imaging and advanced artificial intelligence, this kind of efficiency could mean the difference between a result that takes hours to compute and one that is available in minutes. The researchers have made their code available to the public, inviting others to build upon this new way of thinking about data correction.

Technical Summary: A Tensor Greedy Double-Block Extended Kaczmarz Method for Inconsistent Tensor Linear Systems under the t-product

Problem Statement
The paper addresses the problem of solving inconsistent third-order tensor linear systems of the form $\mathcal{A} * \mathcal{X} = \mathcal{B}$ , where $\mathcal{A} \in \mathbb{R}^{N_1 \times N_2 \times N_3}$ , $\mathcal{B} \in \mathbb{R}^{N_1 \times K \times N_3}$ , and $*$ denotes the t-product introduced by Kilmer and collaborators. In practical applications such as color image recovery and MRI deblurring, the system is often inconsistent due to noise ( $\mathcal{B} = \mathcal{A} * \mathcal{X}^* + \mathcal{E}$ ). The goal is to find the unique minimum-norm least-squares solution $\mathcal{X}^* = \mathcal{A}^\dagger * \mathcal{B}$ . While the Randomized Extended Kaczmarz (REK) method effectively handles inconsistent matrix systems, existing tensor extensions (such as TREK, TREBK, and TREGBK) rely on static, pre-defined partitions of tensor slices, which may not optimally adapt to the specific structure or residual distribution of the problem.

Methodology
The authors propose the Tensor Greedy Double-Block Extended Kaczmarz (TGDBEK) method. This algorithm extends the matrix-based Greedy Double-Block Extended Kaczmarz (GDBEK) to the tensor t-product setting. The core methodology involves two coupled iterative processes at each step $k$ :

Dual Variable Update ( $\mathcal{Z}$ ): The algorithm updates an auxiliary tensor $\mathcal{Z}$ to project the right-hand side $\mathcal{B}$ onto the range of $\mathcal{A}$ . This is done by selecting a block of lateral slices (columns) of $\mathcal{A}$ based on a greedy criterion.
Primal Variable Update ( $\mathcal{X}$ ): The algorithm updates the solution $\mathcal{X}$ using the corrected right-hand side $(\mathcal{B} - \mathcal{Z})$ . This involves selecting a block of horizontal slices (rows) of $\mathcal{A}$ based on the residual of the current estimate.

Key Innovation: Dynamic Greedy Selection
Unlike previous tensor block methods (TREBK, TREGBK, TREABK) that utilize static, pre-partitioned blocks, TGDBEK dynamically constructs the active blocks of row and column slices at every iteration.

Selection Strategy: The algorithm employs a residual-based greedy selection strategy. It identifies slices associated with the largest residual norms.
Threshold Parameter ( $\eta$ ): A single intuitive parameter $\eta \in (0, 1]$ controls the size of the active blocks. A slice index is included in the active block if its normalized squared residual contribution exceeds $\eta$ times the maximum such contribution across all slices. This allows the block size to adapt dynamically to the problem's state without requiring fixed partitioning.

Theoretical Contributions
The paper establishes the linear convergence of the TGDBEK method in the Frobenius norm to the unique minimum-norm least-squares solution.

Convergence Analysis: The authors prove that the sequence of dual iterates $\{\mathcal{Z}^{(k)}\}$ converges linearly to the component of $\mathcal{B}$ orthogonal to the range of $\mathcal{A}$ .
Main Theorem: The sequence of primal iterates $\{\mathcal{X}^{(k)}\}$ is shown to converge linearly. The convergence rate depends on intrinsic geometric parameters of the tensor $\mathcal{A}$ , specifically the tensor block condition number $\kappa_{block}(\mathcal{A})$ and the smallest active block singular value. The proof relies on tensor analogues of the Pythagorean theorem and properties of the t-product, including the relationship between the tensor norm and the Frobenius norm of its block circulant matrix.

Numerical Results
Extensive numerical benchmarks were conducted on synthetic dense and sparse tensor systems, as well as real-world image deblurring problems (color images and 3D volumetric MRI). The TGDBEK method was compared against state-of-the-art solvers: TREK, TREBK, and TREGBK.

Performance Metrics: The study evaluated performance based on iteration count (IT) and CPU running time to reach a relative squared error (RSE) tolerance of $10^{-5}$ .
Dense Systems: TGDBEK consistently required the fewest iterations and least CPU time. For instance, in a dense system with $n=80$ , TGDBEK converged in 44 iterations, whereas TREBK and TREGBK required 247 and 217 iterations, respectively. TREK often failed to converge within the iteration budget.
Sparse Systems: On sparse tensors derived from the SuiteSparse collection, TGDBEK demonstrated superior efficiency, often converging in significantly fewer iterations than competitors.
Image Deblurring: In color image deblurring, TGDBEK was the only method to reach the prescribed tolerance ( $10^{-5}$ ) within 1000 iterations, achieving a final RSE of $1.00 \times 10^{-5}$ in 503 iterations. Other methods failed to reach this tolerance. In MRI deblurring, TGDBEK matched the reconstruction quality (PSNR/SSIM) of other convergent methods but achieved the solution faster in wall-clock time.
Parameter Sensitivity: Experiments varying the threshold $\eta$ indicated that values in the range $[0.1, 0.6]$ offer the best trade-off between convergence speed and per-iteration computational cost.

Significance and Claims
The paper claims that TGDBEK substantially outperforms existing tensor Kaczmarz solvers by eliminating the need for rigid, pre-defined block partitions. By dynamically adapting the active block sizes based on residual energy, the method focuses computational effort where it is most needed. The authors assert that this approach leads to up to a 5-fold reduction in iteration count and up to a 2.5-fold reduction in wall-clock CPU time compared to state-of-the-art methods. The work provides a theoretical foundation for greedy strategies in the t-product setting and demonstrates practical effectiveness in solving large-scale inconsistent tensor systems arising in imaging applications.

Future Directions
The authors identify three potential research directions:

Developing projection-free (pseudoinverse-free) variants using averaging strategies to reduce computational complexity for large block sizes.
Investigating adaptive and dynamic thresholding sequences ( $\eta_k$ ) that evolve based on residual decay.
Generalizing the framework to higher-order tensors ( $p \ge 4$ ) under the generalized tuple t-product.

Technical Summary: A Tensor Greedy Double-Block Extended Kaczmarz Method for Inconsistent Tensor Linear Systems under the t-product

More like this