🔢 mathematics

Deterministic and randomized Kaczmarz methods for $AXB=C$ with applications to color image restoration

This paper proposes and analyzes several deterministic and randomized block Kaczmarz methods for solving consistent linear matrix equations of the form $AXB=C$, establishing their convergence properties and demonstrating their effectiveness through numerical tests and applications to color image restoration.

Original authors: Wenli Wang, Duo Liu, Gangrong Qu, Michiel E. Hochstenbach

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wenli Wang, Duo Liu, Gangrong Qu, Michiel E. Hochstenbach

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, complex puzzle. In the world of mathematics, this puzzle is a matrix equation (specifically $AXB = C$). Think of $A$ and $B$ as the rules of the puzzle, $C$ as the picture you want to see, and $X$ as the missing piece you need to find.

This paper introduces a new set of tools to solve these puzzles faster and more efficiently, specifically for problems like restoring blurry color images.

Here is a breakdown of their approach using simple analogies:

1. The Old Way vs. The New Way

The "Direct" Approach (The Heavy Lifter):
Imagine trying to solve the puzzle by looking at every single piece and every single rule at the same time. This is what older, "direct" methods do. It's like trying to lift a whole car to move it. It works, but it's incredibly heavy, slow, and requires a lot of memory. If the puzzle is huge (like a high-resolution photo), this method gets stuck.

The "Kaczmarz" Approach (The Step-by-Step Walker):
The authors use a method called Kaczmarz. Instead of looking at the whole puzzle at once, imagine you are walking through a hallway of doors. Each door represents one rule (or "row") of the puzzle.

You stop at one door, check if your current guess fits that specific rule, and adjust your guess slightly.
Then you move to the next door, check again, and adjust again.
You keep walking down the hallway, making tiny corrections until your guess fits all the doors perfectly.

This is much lighter on your memory because you only need to remember one door at a time, not the whole hallway.

2. The Three Main Strategies

The paper proposes three different ways to walk down that hallway of doors:

A. The "Cyclic Walker" (Deterministic BK)

How it works: You walk down the hallway in a strict order: Door 1, Door 2, Door 3... all the way to the end, then start over at Door 1.
The Analogy: It's like a teacher checking every student's homework in alphabetical order, one by one, every single day.
Pros/Cons: It's predictable. However, if the first few doors are easy and the last few are hard, you might waste time on the easy ones before tackling the hard ones.

B. The "Random Walker" (Randomized BK)

How it works: Instead of walking in order, you close your eyes and point to a random door. You check that one, adjust, and point to another random door.
The Analogy: It's like a teacher picking students to answer questions by drawing names out of a hat.
Pros/Cons: It's often faster than the strict order because you might accidentally hit the "hard" doors early on. But, sometimes you might pick the same easy door twice in a row, which is a bit wasteful.

C. The "Greedy Detective" (The Paper's Big Innovation)

This is where the authors shine. They realized that not all doors are equally important. Some doors have "residuals"—a fancy word for "how wrong your current guess is."

The Strategy: Instead of picking randomly or in order, the Greedy Detective looks at all the doors and asks: "Which one am I getting the most wrong right now?"
The Analogy: Imagine a teacher who looks at the whole class and says, "I see that Student #42 is really confused about this specific rule. Let's focus on them first!"
The Variations:
- GRBK (Greedy Randomized): The detective picks the top 10% of the most confused students, then picks one randomly from that group.
- MWRBK (Max Weighted Residual): The detective picks the single most confused student and fixes them immediately. This is the "deterministic" version of the greedy approach.

3. The Application: Fixing Blurry Photos

The paper tests these methods on color image restoration.

The Problem: You have a blurry, noisy photo (the "C" in the equation). You want to recover the original sharp photo (the "X").
The Setup: The blurring process is like a filter that smears the image. The math equation describes how the blur happened.
The Result: The authors found that the Greedy Detective methods (especially the one that picks the "most wrong" row) were the fastest. They reached a clear, sharp image in fewer steps than the old methods.
- The "Cyclic Walker" was slow because it wasted time on easy parts of the image.
- The "Random Walker" was okay, but sometimes missed the critical blurry spots.
- The "Greedy Detective" zoomed straight to the blurriest parts of the image and fixed them first, saving a lot of time.

4. Key Takeaways

Efficiency: By focusing only on the parts of the problem that are currently "wrong," these new methods solve the puzzle much faster than looking at everything at once.
Flexibility: These methods work whether the puzzle is "overdetermined" (too many rules) or "underdetermined" (too few rules).
The Winner: The MWRBK method (the one that always picks the single worst error to fix) turned out to be the champion in their tests. It was the most consistent and fastest way to restore the images.

In short, the paper teaches us that when solving massive mathematical puzzles, don't just walk in a circle or guess randomly. Instead, look at the whole picture, find the biggest mistake, and fix that first. It's a smarter, faster way to get the job done.

Technical Summary: Deterministic and Randomized Kaczmarz Methods for $AXB = C$

Problem Statement

The paper addresses the solution of consistent linear matrix equations of the form:
$AXB = C$
where $A \in \mathbb{R}^{m \times p}$ , $B \in \mathbb{R}^{q \times n}$ , and $C \in \mathbb{R}^{m \times n}$ . The goal is to find $X \in \mathbb{R}^{p \times q}$ . This equation arises in various engineering applications, including image processing, control theory, and computer vision. A specific application highlighted is the forward model for noise-free color image restoration, expressed as $AXA_c^T = C$ , where $A$ represents within-channel blurring and $A_c$ represents cross-channel blurring.

The authors note that direct approaches for solving this equation have cubic complexity and may fail when the solution is not unique or when noise is present. While existing iterative methods (e.g., Gradient-based Iterative (GI) methods) exist, they often require storing and accessing the entire coefficient matrix at each iteration, leading to high computational costs. The paper focuses on row-action methods, which access only one row of $A$ per iteration, offering advantages in memory utilization and robustness to noise.

Methodology

The paper extends Kaczmarz-type methods, traditionally used for linear systems $Ax=b$, to the matrix equation $AXB=C$. The proposed methods are categorized into deterministic cyclic variants and randomized/greedy variants.

1. Block Kaczmarz (BK) Methods

The authors first propose a deterministic cyclic variant called the Block Kaczmarz (BK) method. Unlike previous extensions that decompose the equation into scalar subsystems, the BK method processes one row of $A$ (and the corresponding row of $C$ ) at a time while utilizing the entire matrix $B$ .

General BK (Algorithm 2): Applicable to any size of $B$ . It updates $X$ using a rank-one update based on the $i_k$ -th row of $A$ . The authors prove convergence to a specific solution $X^*_0 = A^+CB^+ + X_0 - A^+AX_0BB^+$ for any initial guess $X_0$ , provided $0 < \alpha < 2\|B\|^{-2}$ .
BK with Full Column Rank (Algorithm 3): When $B$ has full column rank, the equation is transformed via QR decomposition ($B=QR$) into $AXQ = \tilde{C}$ . This allows for the derivation of a concise matrix formula for a complete cycle (sweep) of the method.
BK with Full Row Rank (Algorithm 4): When $B$ has full row rank, the equation is reformulated as $AX = \hat{C}$ . This is treated as a linear system with multiple right-hand sides. The authors derive a sweep formula and prove convergence properties similar to the standard Kaczmarz method for multiple right-hand sides.
Equivalence: Proposition 3.7 establishes that Algorithms 3 and 4 are equivalent when $B$ is nonsingular.

2. Greedy and Randomized Variants

Building on the BK framework, the authors extend greedy and randomized strategies from linear systems to the matrix equation context:

Greedy Randomized Block Kaczmarz (GRBK, Algorithm 5): Extends the GRK method by selecting rows based on a threshold involving both the maximum and average weighted residual norms.
Relaxed Greedy Randomized Block Kaczmarz (RGRBK, Algorithm 6): Introduces a tunable parameter $\theta \in [0, 1]$ $θ \in [0, 1]$ to balance between the maximum residual strategy and the average residual strategy.
- $\theta = 1/2$ : Coincides with GRBK.
- $\theta = 1$ : Coincides with the deterministic MWRBK.
Maximal Weighted Residual Block Kaczmarz (MWRBK, Algorithm 7): A deterministic method that selects the row with the largest weighted residual at each step.

Convergence Analysis

The paper provides rigorous convergence analysis for all proposed methods:

BK Methods: Proven to converge to the solution $X^*_0$ (or the minimum norm solution $X^* = A^+CB^+$ if $X_0=0$ and specific range conditions are met).
GRBK, RGRBK, MWRBK: Proven to converge in expectation to the unique minimum norm solution $X^*$ for a zero initial matrix.
Convergence Factors: The authors derive upper bounds for the convergence factors. They show that the bounds for the greedy/randomized variants (GRBK, RGRBK, MWRBK) are strictly smaller than or equal to the bound for the standard Randomized Block Kaczmarz (RBK) method. Specifically, the upper bound for RGRBK decreases as $\theta$ increases, suggesting the deterministic MWRBK ( $\theta=1$ ) has the tightest theoretical bound.
Optimal Step Size: The analysis indicates that the convergence factor upper bound is minimized when the relaxation parameter $\alpha = \|B\|^{-2}$ .

Key Contributions

Extension of Kaczmarz Methods: The paper successfully extends deterministic cyclic, greedy randomized, and maximal weighted residual Kaczmarz strategies to the general matrix equation $AXB=C$.
Novel Block Formulations: The authors introduce specific formulations (Algorithms 3 and 4) for cases where $B$ has full column or row rank, enabling the derivation of elegant matrix formulas for complete sweeps.
Theoretical Guarantees: Convergence properties are established for all proposed methods, including explicit error bounds and conditions for convergence to the minimum norm solution.
Complexity Analysis: The proposed methods are shown to have quadratic computational complexity per iteration ( $O(q(p+n))$ or similar), significantly lower than the cubic complexity of the Gradient-based Iterative (GI) method.
Application to Image Restoration: The methods are applied to a noise-free color image restoration model, demonstrating their practical utility.

Numerical Results

The authors validate their theoretical findings through numerical experiments:

Synthetic Data: Tests on various matrix configurations (overdetermined, underdetermined, rank-deficient) confirm the linear asymptotic convergence of the BK methods.
Comparison with RBK: In tests comparing RBK, GRBK, RGRBK, and MWRBK, the greedy variants consistently require fewer iterations and less total CPU time than the standard RBK, despite having slightly higher cost per iteration due to residual calculations.
Image Restoration: Applied to restoring blurred color images (face, bird, mandril), the proposed methods (particularly MWRBK and RGRBK) outperform the GI method in total computation time and outperform the standard BK and RBK methods in terms of iterations required to reach a target error.
Performance Trends: The results indicate that the MWRBK method (deterministic, $\theta=1$ ) often achieves the fastest convergence in terms of both iterations and total time, confirming the theoretical prediction that the convergence bound improves with $\theta$ .

Significance and Claims

The paper claims that the proposed Kaczmarz-type methods offer a computationally efficient alternative to existing iterative solvers for linear matrix equations.

Efficiency: By utilizing rank-one updates and row-action strategies, the methods avoid the expensive matrix-matrix products required by GI methods, reducing complexity from cubic to quadratic.
Robustness: The row-action nature makes the methods suitable for large-scale problems and potentially robust to noise (though the paper focuses on the noise-free case).
Superiority of Greedy Strategies: The numerical experiments suggest that incorporating greedy selection strategies (GRBK, RGRBK, MWRBK) significantly accelerates convergence compared to purely random or cyclic selection, with the deterministic MWRBK emerging as the most attractive option in terms of iteration count and runtime.
Theoretical Insight: The derivation of sweep formulas for specific rank conditions on $B$ provides deeper theoretical insight into the behavior of block Kaczmarz methods.

The authors conclude that while the BK method is valuable for understanding row selection effects, the greedy extensions (especially MWRBK) consistently achieve faster convergence in practice. They note that the study is limited to noise-free equations and suggest that applying these methods to noisy right-hand sides is a direction for future work.