Hybrid ABBA-GMRES for Unmatched Backprojectors in Large Scale X-Ray Computerized Tomography

1. Problem Statement

In large-scale X-ray Computed Tomography (CT), image reconstruction is formulated as a linear inverse problem $Ax \approx b$. Due to the massive size of the system matrix $A$, explicit formation is impossible; instead, matrix-vector products are computed using optimized forward projectors ($A$) and backprojectors ($B$).

The Core Challenge:
In practical implementations (e.g., using GPU-accelerated toolboxes like ASTRA or TIGRE), the backprojector $B$ is often an approximation and not the exact mathematical adjoint of the forward projector ($B \neq A^T$). This "unmatched" condition leads to:

• Non-symmetric normal equations: Classical iterative solvers like CGLS or LSQR, which assume $B = A^T$, fail to converge or produce meaningful reconstructions.
• Semi-convergence: Existing solvers designed for unmatched pairs, specifically AB-GMRES and BA-GMRES, exhibit semi-convergence. They initially reduce error by capturing dominant spectral modes but eventually amplify noise and modeling errors as iterations proceed, causing reconstruction quality to deteriorate.
• Stopping Criterion Sensitivity: Determining the optimal stopping point to avoid noise amplification is difficult and highly sensitive to heuristic choices, especially when noise levels are unknown.

2. Methodology

The authors propose Hybrid AB-GMRES and Hybrid BA-GMRES methods. These methods integrate Tikhonov regularization directly into the Krylov subspace iterations, rather than applying it to the full system or relying solely on early termination.

Key Technical Components:

• Projected Regularization: Instead of solving the standard projected least-squares problem at iteration $k$, the hybrid methods solve a small, regularized Tikhonov problem within the Krylov subspace:
  $$y_k^h = \arg \min_y \left\| \begin{pmatrix} H_k \\ \lambda I \end{pmatrix} y - \|r_0\|_2 \begin{pmatrix} e_1 \\ 0 \end{pmatrix} \right\|_2^2$$
  Where $H_k$ is the Hessenberg matrix from the Arnoldi process, and $\lambda$ is the regularization parameter.
• Algorithmic Variants:
  • Hybrid AB-GMRES: Targets underdetermined systems ($m < n$). It applies GMRES to the system $ABu = b$ and updates the solution via $x_k = x_0 + BW_k y_k$.
  • Hybrid BA-GMRES: Targets overdetermined systems ($m \ge n$). It applies GMRES to $BAx = Bb$ and updates via $x_k = x_0 + W_k y_k$.
• Theoretical Distinctions:
  • The authors prove that Hybrid BA-GMRES is algebraically equivalent to Hybrid LSMR when $B=A^T$.
  • However, Hybrid AB-GMRES is NOT equivalent to Hybrid LSQR. This is because these methods follow a "project-then-regularize" strategy, which is not equivalent to "regularize-then-project" in the context of unmatched operators.
• Parameter Selection: The paper investigates automatic strategies for selecting $\lambda$ at each iteration using:
  • L-curve criterion: Balancing residual norm and solution norm.
  • Generalized Cross Validation (GCV): A statistical approach minimizing predictive error without needing noise level estimates.
• Restarting: To manage memory and computational costs in large-scale problems, the authors implement a restarting strategy where the Krylov subspace dimension is capped at $p$ iterations, using the current solution as the new initial guess.

3. Key Contributions

1. Novel Hybrid Formulations: The development of Hybrid AB-GMRES and BA-GMRES that embed Tikhonov regularization directly into the Krylov iteration, specifically designed for unmatched projector pairs.
2. Theoretical Analysis: Clarification of the relationship between these new methods and classical solvers (LSQR/LSMR). The paper establishes that while BA-GMRES aligns with LSMR, AB-GMRES diverges from LSQR in the hybrid setting, highlighting the non-equivalence of "project-then-regularize" vs. "regularize-then-project."
3. Automatic Parameter Strategies: Implementation and analysis of L-curve and GCV strategies for adaptive regularization parameter selection within the hybrid framework.
4. Comprehensive Numerical Evaluation: Extensive testing on synthetic and realistic CT problems (including GPU-accelerated implementations) comparing hybrid vs. non-hybrid methods, different parameter selection criteria, and various stopping rules.

4. Results

The authors conducted experiments on three test problems: a small synthetic toy problem, a 128x128 Shepp-Logan phantom, and a large 1024x1024 Logan phantom.

• Mitigation of Semi-convergence: The hybrid methods successfully eliminated the semi-convergence behavior observed in standard AB/BA-GMRES. The reconstruction error stabilized at a low level rather than deteriorating after a few iterations.
• Reconstruction Quality: Hybrid methods produced higher-quality images (measured by Relative Reconstruction Error - RRE, and Structural Similarity Index - SSIM) compared to non-hybrid counterparts.
• Parameter Selection Performance:
  • L-curve: Consistently provided the most efficient reconstructions and stable convergence across test cases.
  • GCV: Offered a fully automatic alternative with competitive performance, though sometimes slightly less stable than the L-curve in specific scenarios.
• Computational Efficiency:
  • The overhead of solving the small regularized projected problems was negligible compared to the cost of forward/backprojection operations.
  • Restarting significantly reduced memory usage and runtime for large-scale problems without sacrificing image quality.
  • AB-GMRES variants generally outperformed BA-GMRES in terms of time and memory for highly underdetermined systems.
• Stopping Criteria: The study found that Residual Norm Stagnation (RNS) and Discrepancy Principle (DP) worked well with hybrid methods, whereas standard criteria often failed for non-hybrid methods. The explicit regularization made the methods less sensitive to the exact stopping iteration.

5. Significance

This paper provides a robust solution to a critical bottleneck in modern industrial and medical CT imaging: the use of fast, approximate, unmatched backprojectors.

• Practical Impact: It enables the use of highly optimized, hardware-specific (GPU) projectors that sacrifice exact adjointness for speed, without sacrificing reconstruction quality.
• Stability: By moving from "implicit" regularization (relying on early stopping) to "explicit" regularization (Tikhonov within the subspace), the method offers a more stable and reliable reconstruction process that is less dependent on heuristic stopping rules.
• Scalability: The approach is scalable to massive datasets (e.g., 1024x1024 images) and integrates seamlessly with existing matrix-free frameworks like ASTRA and TIGRE.

In conclusion, the proposed Hybrid AB/BA-GMRES framework represents a significant advancement in iterative CT reconstruction, offering a stable, scalable, and high-quality alternative for systems where exact adjoint operators are computationally prohibitive.