Stochastic Multiresolution Image Sketching for Inverse Imaging Problems
Alessandro Perelli, Carola-Bibiane Schönlieb, Matthias J. Ehrhardt · 2024
Read Stochastic Multiresolution Image Sketching for Inverse Imaging Problems by Alessandro Perelli, Carola-Bibiane Schönlieb, Matthias J. Ehrhardt (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10249.txt.
Introduction
Alessandro Perelli, Carola-Bibiane Schönlieb, and Matthias Ehrhardt sketch images mid solver in a 2024 paper. Inverse imaging problems like CT involve huge images and data. Each solver step that touches the full image costs dearly. Stochastic methods already subsample the data side to save time.
Their algorithm, ImaSk, sketches the image side instead. Each iteration works on a randomly chosen resolution of the image. A saddle point view turns it into a gradient method with stored past gradients. For linear models with strong regularization, they prove linear convergence. CT simulations show the method reaches the target solution faster. More resolution levels cut the computing time further. The idea ports stochastic savings from data space into image space.
Catalog record
| CREATOR | Alessandro Perelli, Carola-Bibiane Schönlieb, Matthias J. Ehrhardt |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-10249
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Multiresolution Image Sketching for Inverse Imaging Problems Thanks: Submitted to the editors of SIIMS. Alessandro Perelli, Carola-Bibiane Schönlieb, Matthias J. Ehrhardt Abstract A challenge in high-dimensional inverse problems is developing iterative solvers to find the accurate solution of regularized optimization problems with low computational cost. An important example is computed tomography (CT) where both image and data sizes are large and therefore the forward model is costly to evaluate. Since several years algorithms from stochastic optimization are used for tomographic image reconstruction with great success by subsampling the data. Here we propose a novel way how stochastic optimization can be used to speed up image reconstruction by means of image domain sketching such that at each iteration an image of different resolution is being used. Hence, we coin this algorithm ImaSk . By considering an associated saddle-point problem, we can formulate ImaSk as a gradient-based algorithm where the gradient is approximated in the same spirit as the stochastic average gradient amélioré (SAGA) and uses at each iteration one of these multiresolution operators at random. We prove that ImaSk is linearly converging for linear forward models with strongly convex regularization functions. Numerical simulations on CT show that ImaSk is effective and increasing the number of multiresolution operators reduces the computational time to reach the modeled solution. keywords Inverse problems, X-ray Computed Tomography, Saddle-point optimization, Multiresolution operators, Stochastic average gradient Funding. The authors acknowledge support from the Royal Academy of Engineering under the RAEng / Leverhulme Trust Research Fellowships programme (award LTRF-2324-20-160), the Leverhulme Trust (ECF-2019-478), the Philip Leverhulme Prize, the Royal Society Wolfson Fellowship, the EPSRC advanced career fellowship EP/V029428/1, the EPSRC programme grant EP/V026259/1, and the EPSRC grants EP/S026045/1, EP/T026693/1, EP/T003553/1, EP/N014588/1, EP/T017961/1, the Wellcome Innovator Awards 215733/Z/19/Z and 221633/Z/20/Z, the European Union Horizon 2020 research and innovation programme under the Marie Skodowska-Curie grant agreement NoMADS and REMODEL, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute. This research was also supported by the NIHR Cambridge Biomedical Research Centre (NIHR203312). The views expressed are those of the author(s) and not necessarily those of the NIHR or the Department of Health and Social Care. † † runningheads: ImaSk: Stochastic Multiresolution Image Domain Sketching / AMS 47A52, 49M30, 65J20, 65N55, 68U10 1 Introduction Inverse problems involving estimating unknown images from noisy measurements arises in many medical and non-medical imaging applications such as X-ray Computed Tomography (CT), Positron Emission Tomography (PET) and Magnetic Resonance Imaging (MRI). If the noise is modeled as Gaussian, then the problem can be mathematically described as \mathbf{b}=\mathbf{K}\mathbf{x}+\mathbf{n} where \mathbf{K}\in\mathbb{R}^{m\times d} represents the physical forward model and \mathbf{n}\in\mathbb{R}^{m} the mean-zero Gaussian noise. Nowadays with the deluge of acquired data and the aim to reconstruct images at fine resolution, an emerging challenge is constituted by reducing the computational cost while preserving the accuracy of the solution [ 2 ] . An established framework for estimating the unknown high-dimensional vector \mathbf{x} from the measurements \mathbf{b} is to solve a model-based optimization problem of the form \min_{\mathbf{x}\in\mathbb{R}^{d}}\frac{1}{2}\|\mathbf{K}\mathbf{x}-\mathbf{b}\|^{2}+R(\mathbf{x}) (1) where R:\mathbb{R}^{d}\to\mathbb{R}_{\infty}:=\mathbb{R}\cup\{\infty\} describes the regularization term which enforce a particular structure on the possible solutions for \mathbf{x} [ 15 ] . Many iterative solvers have been developed to minimize the original model-based cost function [ 18 ] . First-order methods and its accelerated versions generally involve operations like matrix-vector multiplications and evaluations of proximal operators [ 10 ] , which are for many problems in closed form or easy to compute iteratively [ 6 ] . From a computational point of view, a main bottleneck of any iterative solvers used to minimize eq. 1 is the application of the forward operator \mathbf{K} and its adjoint [ 1 , 26 ] . A popular approach to overcome this computational bottleneck is to change the discretisation of the image. E.g. in [ 21 ] chooses a nonuniform triangular grid for PET reconstruction where the resolution is selected a-priori from a second modality. An inexact multi-level version of FISTA is proposed in [ 20 ] . A similar concept was previously exploited by multi-grid reconstruction methods which are based on partitioning the image of interest in order to reduce the computation time and memory required [ 22 ] , since in practical settings often only a specific region of interest needs to be analyzed at full resolution. Alternative methods are based on the multiresolution wavelet structure [ 33 ] which allows to iteratively impose regularization constraints on an hierarchy of fine to coarse resolution images. Recently a wide area of research is constituted by the development of scalable gradient-based algorithms which use only a random subset of the measurements at each iteration; notable methods are stochastic gradient descent (SGD) [ 19 ] and other Stochastic Variance Reduced methods [ 35 , 17 ] such as the improved stochastic average gradient (SAGA) [ 11 ] which can reduce the variance of the stochastic gradient estimator progressively and improve the convergence of SGD methods. Stochastic algorithms have also been applied to saddle-point optimization problems [ 3 , 9 , 14 , 12 ] . Furthermore, different types of dimensionality reduction operators, called sketches, in the measurement domain have been developed within iterative convergent algorithms [ 34 ] . Random sketches are used in second-order method for optimization to perform approximate Newton step using a randomly projected or sub-sampled Hessian [ 27 ] . Randomized algorithms using sketched gradients are leveraged to solve least squares problems or to reduce the computation of proximal algorithms [ 30 ] or optimization using regularization by denoising [ 25 ] . Over the last years, several of the aforementioned algorithms have been applied to imaging problems, most notably to CT and PET, see e.g. [ 14 , 31 , 29 ] but also other imaging modalities like magnetic particle imaging [ 36 ] . For an overview on the field and further references, we refer to [ 13 ] . As in machine learning, all of these approaches randomly sample the data. In contrast, we use a novel random sampling in image space. 1.1 Contribution Inspired by the notion of sketching, we propose a novel algorithm that uses cheaper matrix-vector products essentially by sketching in the image domain. To this end we decompose the forward operator using a family of multiresolution operators and consider the corresponding saddle point formulation. The latter reveals a structure commonly encountered in stochastic optimization which can be approached by various gradient estimators such as SAGA. Note that the original formulation does not the reveal the averaging property that is used for efficient stochastic gradient based solvers. From a computational perspective, this allows to reduce the per-iteration cost of the iterative algorithm and thereby potentially an overall more efficient algorithm. We analyze its linear convergence rate and give sufficient conditions on its parameters for convergence. While this approach is similar to [ 3 ] , our analysis reveals more general conditions and better convergence rates. We also study the behavior of the algorithm for CT image reconstruction in terms of the number of resolutions, step-size, convergence rate and computational time. 2 ImaSk Algorithm In this section we present the proposed algorithm for image reconstruction, i.e., for solving eq. 1 . 2.1 The Idea in