# Accelerating Plug-and-Play Image Reconstruction via Multi-Stage Sketched Gradients

arXiv: https://arxiv.org/abs/2203.07308 · HTML: https://mlsanity.com/paper/2203.07308/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 31 references that are in the map.
- First posted on arXiv 14 Mar 2022.

## Builds on (most cited first, 18 of 18)

- [Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising](https://mlsanity.com/paper/1608.03981/) (2016)
- [Deep Convolutional Neural Network for Inverse Problems in Imaging](https://mlsanity.com/paper/1611.03679/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [The Little Engine that Could: Regularization by Denoising (RED)](https://mlsanity.com/paper/1611.02862/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Learned Primal-dual Reconstruction](https://mlsanity.com/paper/1707.06474/) (2017)
- [Regularization by Denoising: Clarifications and New Interpretations](https://mlsanity.com/paper/1806.02296/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [An Online Plug-and-Play Algorithm for Regularized Image Reconstruction](https://mlsanity.com/paper/1809.04693/) (2018)
- [Regularization by Denoising via Fixed-Point Projection (RED-PRO)](https://mlsanity.com/paper/2008.00226/) (2020)
- [Scalable Plug-and-Play ADMM with Convergence Guarantees](https://mlsanity.com/paper/2006.03224/) (2020)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [A Fast Stochastic Plug-and-Play ADMM for Imaging Inverse Problems](https://mlsanity.com/paper/2006.11630/) (2020)
- [The Practicality of Stochastic Optimization in Imaging Inverse Problems](https://mlsanity.com/paper/1910.10100/) (2019)
- [Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares](https://mlsanity.com/paper/1609.09419/) (2016)
- [The Non-uniform Fast Fourier Transform in Computed Tomography](https://mlsanity.com/paper/1605.05231/) (2016)
- [Exploiting the Structure via Sketched Gradient Algorithms](https://mlsanity.com/paper/1705.05348/) (2017)

## Built on by (most cited first, 2 of 2)

- [Provably Convergent Plug-and-Play Quasi-Newton Methods](https://mlsanity.com/paper/2303.07271/) (2023)
- [Operator Sketching for Deep Unrolling Networks](https://mlsanity.com/paper/2203.11156/) (2022)

## Abstract (arXiv)

In this work we propose a new paradigm for designing fast plug-and-play (PnP) algorithms using dimensionality reduction techniques. Unlike existing approaches which utilize stochastic gradient iterations for acceleration, we propose novel multi-stage sketched gradient iterations which first perform downsampling dimensionality reduction in the image space, and then efficiently approximate the true gradient using the sketched gradient in the low-dimensional space. This sketched gradient scheme can also be naturally combined with PnP-SGD methods for further improvement on computational complexity. As a generic acceleration scheme, it can be applied to accelerate any existing PnP/RED algorithm. Our numerical experiments on X-ray fan-beam CT demonstrate the remarkable effectiveness of our scheme, that a computational free-lunch can be obtained using this dimensionality reduction in the image space.