Iterative Operator Sketching Framework for Large-Scale Imaging Inverse Problems

Junqi Tang, Subhadip Mukherjee, Carola-Bibiane SchönliebICASSP 2025 · DOI

TL;DR

This paper introduces a novel "operator sketching" framework to significantly accelerate iterative methods for large-scale imaging inverse problems. By reducing the dimensionality of both the image and measurement domains, their proposed methods, PnP-MS2G and SkLSPD, achieve comparable reconstruction quality to existing state-of-the-art techniques but with substantially reduced computational cost.

What Problem Does This Paper Address?

Many modern imaging applications, such as medical imaging (X-ray CT, MRI, PET), involve solving "inverse problems." These problems aim to reconstruct a high-dimensional image (e.g., a 3D scan) from limited, noisy measurements. Iterative data-driven reconstruction (IDR) schemes, including plug-and-play (PnP) algorithms and deep unrolling networks, have shown impressive results. However, their practical application is often hindered by significant computational demands, especially for large-scale problems. This is primarily because these methods require repeatedly computing high-dimensional forward and adjoint operators, which can be computationally expensive. This paper tackles this challenge by proposing a method to make these powerful IDR schemes more computationally efficient without sacrificing reconstruction quality.

Methods

The core innovation is a "doubly-sketched" framework that reduces dimensionality in two key areas:

  • Image Domain Sketching: The framework introduces a sketching operator (e.g., downsampling) that creates a lower-dimensional representation of the image. This allows for computations on a smaller image space.
  • Measurement Domain Sketching: Random sketching or subsampling is applied to the measurement data. This effectively creates a smaller, representative subset of the measurements for computation.

By combining these, the authors derive two main accelerated IDR schemes:

  • PnP-MS2G (Plug-and-Play Multi-Stage Sketched Gradients): This method adapts PnP algorithms by incorporating multi-stage sketching. It starts with aggressive sketching for rapid initial convergence and then progressively reduces the sketching effect in later stages to refine the reconstruction.
  • SkLSPD (Sketched Learned Primal-Dual): This approach integrates the sketching framework into deep unrolling networks, specifically building upon the Learned Primal-Dual (LPD) network. It applies sketching to the forward and adjoint operators within the unrolling process, leading to significant computational savings.

The paper also mentions that off-the-shelf down-sampling algorithms (like bi-cubic interpolation) and random subsampling masks are sufficient for their sketching operators.

Datasets

The paper uses the Mayo-Clinic dataset for X-ray CT experiments. This dataset contains 3D CT scans, and the authors utilize 2111 slices (from nine patients) for training and 118 slices (from one patient) for testing. They simulate fan beam projection data with Poisson noise, mimicking low-dose CT conditions.

Key Insights and Ideas

  • Dimensionality Reduction is Key: The fundamental idea that reducing the dimensionality of both the image and measurement spaces can drastically speed up iterative reconstruction is a central theme.
  • Coarse-to-Fine Strategy: The multi-stage sketching approach, starting with aggressive reduction and gradually becoming less aggressive, is an effective strategy for balancing speed and accuracy. This allows for a "warm-start" by prioritizing low-frequency components early on.
  • Generality of the Framework: The sketching framework is presented as a generic tool that can be applied to various IDR schemes, including both PnP and deep unrolling methods, highlighting its broad applicability.
  • Surprising Efficiency Gains: The paper demonstrates that even with sketching, the methods achieve comparable reconstruction quality to full-batch methods, suggesting that the sketched operators capture sufficient information for effective reconstruction.

Key Results

  • Computational Speedup: The proposed methods (PnP-MS2G, LSPD, and SkLSPD) achieve significant reductions in computational time. For instance, in X-ray CT reconstruction, their methods reduce reconstruction time by 40% to 60% compared to the full-batch LPD network.
  • Reconstruction Quality: The sketched methods achieve reconstruction quality (measured by PSNR and SSIM) that is comparable to their unsketched counterparts (e.g., LPD).
  • Efficiency per Iteration: PnP-MS2G is shown to be more computationally efficient per iteration than PnP-SGD, and it also demonstrates a better convergence rate.
  • Reduced Operator Calls: For example, their LSPD and SkLSPD networks with 12 layers require only three calls on the forward and adjoint operators, compared to 12 calls for the full-batch LPD.

Limitations and Future Work

  • Approximation of Operators: The paper acknowledges that the sketched operators are approximations of the true operators. While effective, the theoretical guarantees for convergence might be more complex than for unsketched methods.
  • Hyperparameter Tuning: The multi-stage sketching approach involves parameters like the number of stages and sketch sizes, which might require careful tuning for optimal performance.
  • Future Work: The authors suggest that their framework can be extended to accelerate other methods, such as MCMC schemes for uncertainty quantification in imaging, including PnP-ULA and NF-ULA, which leverage generative models. They also hint at potential applications in other areas beyond imaging.

Summary updated

BibTeX
@inproceedings{tang2025iterative,
  author = {Junqi Tang and Subhadip Mukherjee and Carola-Bibiane Schönlieb},
  title = {{Iterative Operator Sketching Framework for Large-Scale Imaging Inverse Problems}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2025},
  doi = {10.1109/icassp49660.2025.10890355},
}
Figure