Practical Operator Sketching Framework for Accelerating Iterative Data-Driven Solutions in Linear Inverse Problems

Abstract We propose a new operator sketching paradigm for designing efficient iterative data-driven reconstruction (IDR) schemes, such as plug-and-play algorithms and deep unrolling networks. These IDR schemes are the state-of-the-art solutions for imaging inverse problems. However, for high-dimensional imaging tasks, such as X-ray CT, PET and MRI imaging, these IDR schemes typically become inefficient in terms of computation, due to the need to compute the high-dimensional forward and adjoint operators multiple times. In this work, we introduce a universal dimensionality reduction framework for accelerating IDR schemes in solving imaging inverse problems, based on leveraging the sketching techniques from stochastic optimization. Using this framework, we derive several accelerated IDR schemes, including the plug-and-play multistage sketched gradient (PnP-MS2G) and sketching-based primal–dual (LSPD and SkLSPD) deep unrolling networks. Meanwhile, to fully accelerate PnP schemes when the denoisers are computationally expensive, we further propose novel stochastic lazy denoising schemes (Lazy-PnP and Lazy-PnP-EQ), leveraging the ProxSkip scheme in optimization and equivariant image denoisers, to significantly enhance the practicality and efficiency of PnP algorithms. We provide theoretical analysis for recovery guarantees of instances of the proposed framework. Our numerical experiments on natural image processing and tomographic image reconstruction demonstrate the remarkable effectiveness of our sketched IDR schemes.