🔢 mathematics

GKB Methods for X-Ray Computed Tomography with an Unmatched Back Projector

This paper proposes the AB and BA Golub-Kahan bidiagonalization (GKB) algorithms as efficient, preconditioned solutions for large-scale X-ray computed tomography problems with unmatched forward and back projectors, demonstrating superior stability against noise and computational effectiveness compared to existing methods.

Original authors: Abdulmajeed Alsubhi

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abdulmajeed Alsubhi

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

The Big Picture: Fixing a Broken Puzzle

Imagine you are trying to solve a massive jigsaw puzzle (reconstructing an X-ray image) based on a set of clues (the X-ray data). In a perfect world, the tool you use to look at the clues and the tool you use to put the puzzle pieces together would be perfect mirrors of each other. If you looked at a piece from the front, the back would match perfectly.

However, in real-world medical imaging (CT scans), these tools often don't match. The "Forward Projector" (how the X-rays travel through the body) and the "Back Projector" (how we try to reconstruct the image) use slightly different math rules. The paper calls this an "unmatched pair."

Because they don't match, the standard math tools used to solve these puzzles (like the Conjugate Gradient method) get confused. They try to force a square peg into a round hole, leading to solutions that look like static on an old TV screen rather than a clear picture.

The Problem: The "Semi-Convergence" Trap

The paper describes a frustrating phenomenon called semiconvergence.

The Good News: At the very beginning, the math works great. The picture starts to look clear.
The Bad News: If you keep going, the picture gets worse and worse. The math starts amplifying the "noise" (the static) instead of the signal. It's like trying to listen to a quiet song, but every time you turn up the volume to hear it better, the static gets louder until you can't hear the music at all.

Previous methods tried to fix this by using a technique called GMRES. It's like a very fast runner who gets to the finish line quickly but trips over the last hurdle (the noise) and falls down.

The New Solution: The "Golub-Kahan" Toolbox

The author, Abdulmajeed Alsubhi, proposes two new methods: AB-GKB and BA-GKB.

Think of the old method (GMRES) as trying to solve the puzzle by looking at a giant, messy, 3D map of every possible piece. It's powerful, but the map gets so big and complex that it's hard to navigate without getting lost in the noise.

The new method (GKB) is like a smart filter. Instead of looking at the whole messy map, it projects the problem onto a much smaller, simpler, and cleaner "shadow" of the puzzle.

The Analogy: Imagine you have a complex sculpture. The old method tries to measure every curve of the sculpture in 3D space. The new method shines a light on it to create a 2D shadow on the wall. This shadow is much simpler (it's a "lower bidiagonal" shape, which is just a fancy way of saying a neat, stepped line).
The Benefit: Because this "shadow" is so simple and sparse (full of empty space), it's much easier to analyze. It allows the computer to find the true picture without getting distracted by the noise as easily as the old methods do.

The Trade-off: Speed vs. Stability

The paper is honest about the cost of this new approach.

The GMRES method is like a sports car: it's very fast and uses less fuel (computing power), but it's prone to crashing (diverging into noise) if the road is bumpy.
The GKB method is like a heavy-duty truck: it takes more fuel and moves a bit slower, but it has better suspension. It handles the bumps (the noise and the unmatched tools) much better and doesn't crash as easily.

The author proves mathematically that the new GKB methods require more "steps" (calculations) to finish the job than the GMRES methods. However, because they are more stable, they produce a clearer, more reliable image before they start to degrade.

How They Know When to Stop

Since these methods can still eventually get noisy if you run them too long, the paper tests two ways to know when to stop the engine:

The Discrepancy Principle (DP): This is like a "noise meter." You tell the computer, "Stop as soon as the error is about as big as the noise we know is in the data." The paper finds this is the best way to stop.
Residual Norm Stagnation (RNS): This is like waiting until the car stops moving forward. The paper finds this is less reliable for the new method.

The Results

The author tested these new methods on three different "puzzles" (CT scan simulations) of increasing size and noise levels.

The Finding: In every test, the new GKB methods (AB-GKB and BA-GKB) produced clearer images that stayed stable for longer. They resisted the "static" much better than the old GMRES methods.
The Catch: They took slightly longer to compute.

Summary

This paper introduces a new way to fix blurry X-ray images when the math tools don't perfectly match. It trades a little bit of speed for a lot more stability. Instead of racing to the finish line and crashing, the new method drives steadily, filtering out the noise to deliver a clearer picture of what's inside the body.

Technical Summary: GKB Methods for X-Ray Computed Tomography with an Unmatched Back Projector

Problem Statement
In large-scale X-ray Computed Tomography (CT), the reconstruction of an image $x$ from measured data $b$ is formulated as a linear inverse problem $Ax \approx b$ . In practical implementations, the forward projector ( $A$ ) and the back projector ( $B$ ) are often generated using different discretization schemes based on physical approximations. Consequently, $B$ is not equivalent to the transpose of $A$ ( $B \neq A^\top$ ), creating an "unmatched projector pair."

This discrepancy leads to inconsistent normal equations. Standard iterative solvers like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES), when applied to the least-squares formulation of these unmatched systems, often fail to produce meaningful reconstructions. While preconditioned GMRES variants (AB-GMRES and BA-GMRES) have been proposed to handle these systems, they suffer from "semiconvergence." In this phenomenon, the solution initially converges toward the true image but subsequently diverges as iterations continue, amplifying noise due to the inclusion of components associated with small singular values. Furthermore, the projected systems in GMRES involve upper Hessenberg matrices, which can be computationally expensive to decompose as the Krylov subspace dimension grows.

Methodology
The paper proposes two new algorithms, AB-GKB and BA-GKB, which adapt the Golub–Kahan Bidiagonalization (GKB) method to handle unmatched projector pairs. Unlike GMRES, which projects the problem onto a subspace yielding an upper Hessenberg matrix, GKB projects the problem onto a lower-dimensional subspace yielding a sparse lower bidiagonal matrix ( $C_k$ ).

The proposed methods function as follows:

AB-GKB: Applies the GKB process to the system $ABx = Bb$ (treating $B$ as a right preconditioner). The solution is recovered via $x = BQ_k u_k$ , where $Q_k$ is an orthogonal basis and $u_k$ is the solution to the projected bidiagonal system.
BA-GKB: Applies the GKB process to the system $BAx = Bb$ (treating $B$ as a left preconditioner). The solution is recovered via $x = Q_k u_k$ .

Both algorithms avoid explicitly forming the composite operators $AB$ or $BA$, instead relying on successive matrix-vector multiplications with $A$ , $B$ , and their transposes. The projected small-scale problems are solved using the Singular Value Decomposition (SVD) of the sparse bidiagonal matrix $C_k$ . The authors investigate two stopping criteria to mitigate semiconvergence: the Discrepancy Principle (DP) and Residual Norm Stagnation (RNS).

Key Contributions

Algorithmic Proposal: The introduction of AB-GKB and BA-GKB as preconditioned forms of GKB specifically designed for CT problems with unmatched back projectors.
Theoretical Complexity Analysis: A detailed comparison of floating-point operations (FLOPS) between the proposed GKB methods and existing AB/BA-GMRES methods. The analysis reveals that while GMRES methods are computationally faster per iteration (requiring fewer operations), GKB methods generate a sparser projected matrix ( $C_k$ ) compared to the Hessenberg matrix ( $H_k$ ) in GMRES. The SVD of the bidiagonal $C_k$ is significantly cheaper ( $O(k^3)$ ) than that of the Hessenberg $H_k$ ( $O(k^4)$ ).
Numerical Validation: Extensive testing on three CT phantom examples (128x128, 180x180, and 256x256) with varying noise levels and system dimensions (underdetermined and overdetermined).
Stopping Criterion Evaluation: A comparative assessment of DP and RNS, demonstrating that DP consistently terminates iterations near the minimum relative reconstruction error (RRE).

Results
Numerical experiments across various CT scenarios yielded the following observations:

Semiconvergence Behavior: The proposed GKB methods demonstrated greater resilience against semiconvergence compared to AB-GMRES and BA-GMRES. While GMRES methods often diverged rapidly after a few iterations (e.g., 7–10 iterations), GKB methods stabilized for a longer duration (e.g., 40–100 iterations) before noise amplification became dominant.
Reconstruction Quality: In terms of Relative Reconstruction Error (RRE), the GKB methods generally achieved lower error rates than GMRES methods, particularly in later iterations, provided the iteration was stopped correctly.
Computational Cost: Consistent with theoretical analysis, GMRES methods were faster in terms of total runtime. For a fixed number of iterations, GMRES required fewer FLOPS. Specifically, AB-GMRES required approximately 3/5 of the cost of AB-GKB, and BA-GMRES required about half the cost of BA-GKB.
Stopping Criteria: The Discrepancy Principle (DP) proved superior to RNS. DP consistently halted iterations near the optimal RRE for all methods, whereas RNS often terminated too early or too late depending on the algorithm, leading to suboptimal reconstruction quality.
System Dimensionality: The relative efficiency of AB vs. BA formulations depended on whether the system was overdetermined ( $m > n$ ) or underdetermined ( $m < n$ ). In overdetermined cases, BA-based methods were generally faster; in underdetermined cases, AB-based methods were more expensive.

Significance and Claims
The paper claims that while the proposed AB-GKB and BA-GKB algorithms incur a higher computational cost per iteration compared to GMRES-based approaches, they offer a distinct advantage in stability and solution quality for unmatched projector problems. By leveraging the sparsity of the bidiagonal matrix generated by GKB, the methods provide a robust alternative that delays the onset of semiconvergence, allowing for more stable reconstructions without sacrificing the accuracy potential of Krylov subspace methods.

The authors emphasize that the effectiveness of these methods relies heavily on the choice of a stopping criterion; the Discrepancy Principle is identified as the most reliable mechanism to terminate iterations before noise corruption degrades the solution. The work concludes that these algorithms are effective for delivering stable solutions in large-scale CT inverse problems where matched projectors are unavailable, though future work may focus on integrating advanced regularization techniques to further enhance efficiency.