Fast and Flexible Solvers for Inverse Problems
Lead Research Organisation:
University of Bath
Department Name: Mathematical Sciences
Abstract
Inverse problems are ubiquitous in many applications, and essentially arise every time that one wants to recover the cause of an observed effect. This happens, for instance, when one can only acquire indirect measurements of a quantity of interest: notable examples are the deblurring of images (in this setting, the quantity of interest is a sharp image of an object and the measurements are a blurred version thereof) and tomography (in this setting, the quantity of interest is the inside of an object and the measurements are projections thereof).
Once a mathematical model of the physical process linking the cause and the observed effect (for instance, a mathematical model of the measurement process) is established, one can proceed by "inverting" this model, i.e., by solving the inverse problem. This can rarely be achieved without recurring to a computer, after the original continuous mathematical model has been discretised. If the model is linear (as in many image deblurring and tomography applications), the task of solving the discrete inverse problem ultimately amounts to the solution of a linear system of equations. Despite this apparent simplicity, discrete inverse problems are typically very challenging to solve numerically, for at least two reasons: first, the size of the discretised problem is often huge and, second, the solution is very sensitive to the unavoidable perturbations (or noise) that affect the data. In other words, straightforwardly using a numerical solver for linear systems will not work in this setting, for at least two reasons: first, this may be unaffordable in terms of computing time and resources and, second, the solution is totally dominated by perturbations and therefore meaningless.
To fix these issues, first one should employ some form of regularisation, i.e., one should replace the original discretised problem with one that is less sensitive to perturbations; then one should devise suitable algorithms that can solve the regularised problem in an efficient way. This project mainly focuses on the latter important task, i.e., the derivation and the mathematical justification of new and fast numerical methods for the solution of regularised linear inverse problems.
Every successful regularisation method should incorporate a right amount of prior information about the unknown. This often leads to the introduction of nonlinearities, so that involved optimisation methods are used instead of simple linear solvers (indeed, many optimisation methods often require the solution of a sequence of intermediate linear systems arising within the nonlinear scheme). One of the main goals of this project is to remove nonlinearities by introducing adaptive and flexible terms, so that only one linear system needs to be solved (instead of a sequence thereof), thereby guaranteeing massive computational savings with respect to the available strategies, without penalising the quality of the solution. The new methods will be supported by strong mathematical principles and will be made available to the wider scientific community by producing free software that can be potentially used for a variety of computational tasks, even beyond regularisation methods.
The findings of this project can generate great impact in a variety of applications, with specific focus on tomography. In the medical context, many tomographic technologies are useful to diagnose health problems without a need for more invasive techniques. In the industrial context, a variety of tomographic approaches are employed to monitor the quality of production systems, allowing for improved safety of products and reduced economical costs. The new methods can play a dramatic role in making all these technologies computationally more affordable, assuring tangible impact on the society and the economy. Collaborations with academic groups in engineering will be pursued to make this happen.
Once a mathematical model of the physical process linking the cause and the observed effect (for instance, a mathematical model of the measurement process) is established, one can proceed by "inverting" this model, i.e., by solving the inverse problem. This can rarely be achieved without recurring to a computer, after the original continuous mathematical model has been discretised. If the model is linear (as in many image deblurring and tomography applications), the task of solving the discrete inverse problem ultimately amounts to the solution of a linear system of equations. Despite this apparent simplicity, discrete inverse problems are typically very challenging to solve numerically, for at least two reasons: first, the size of the discretised problem is often huge and, second, the solution is very sensitive to the unavoidable perturbations (or noise) that affect the data. In other words, straightforwardly using a numerical solver for linear systems will not work in this setting, for at least two reasons: first, this may be unaffordable in terms of computing time and resources and, second, the solution is totally dominated by perturbations and therefore meaningless.
To fix these issues, first one should employ some form of regularisation, i.e., one should replace the original discretised problem with one that is less sensitive to perturbations; then one should devise suitable algorithms that can solve the regularised problem in an efficient way. This project mainly focuses on the latter important task, i.e., the derivation and the mathematical justification of new and fast numerical methods for the solution of regularised linear inverse problems.
Every successful regularisation method should incorporate a right amount of prior information about the unknown. This often leads to the introduction of nonlinearities, so that involved optimisation methods are used instead of simple linear solvers (indeed, many optimisation methods often require the solution of a sequence of intermediate linear systems arising within the nonlinear scheme). One of the main goals of this project is to remove nonlinearities by introducing adaptive and flexible terms, so that only one linear system needs to be solved (instead of a sequence thereof), thereby guaranteeing massive computational savings with respect to the available strategies, without penalising the quality of the solution. The new methods will be supported by strong mathematical principles and will be made available to the wider scientific community by producing free software that can be potentially used for a variety of computational tasks, even beyond regularisation methods.
The findings of this project can generate great impact in a variety of applications, with specific focus on tomography. In the medical context, many tomographic technologies are useful to diagnose health problems without a need for more invasive techniques. In the industrial context, a variety of tomographic approaches are employed to monitor the quality of production systems, allowing for improved safety of products and reduced economical costs. The new methods can play a dramatic role in making all these technologies computationally more affordable, assuring tangible impact on the society and the economy. Collaborations with academic groups in engineering will be pursued to make this happen.
Planned Impact
WHAT IMPACT?
(a) New knowledge on the formulation, analysis and implementation of fast solvers for inverse problems.
(b) New public-domain software implementing the new algorithms.
(c) Enhanced training of the next generation of researchers in inverse problems (mainly PhD students), with a particular focus on the derivation, analysis, and implementation of numerical methods for the solution thereof.
(d) Applications of this new knowledge in tomography, with particular emphasis on motion estimation.
WHO MIGHT BENEFIT FROM THE RESEARCH?
(a) The large community of academic beneficiaries listed above.
(b) Engineers and practitioners working on technologies and applications of tomographic imaging (in both a medical and an industrial setting).
(c) Members of the EPSRC Research Network in the Mathematics of Inverse Problems.
(d) The UK maintaining at the forefront of areas of numerical linear algebra, optimisation, and inverse problems.
HOW MIGHT THEY BENEFIT FROM THIS RESEARCH?
(a) The benefits for the academic community are described above.
(b) The public-domain implementations of the new methods will be available globally.
(c) A specialistic workshop will be organised.
(d) A software training day will be organised and open to all the interested scientists; videos of lectures will be available globally.
(a) New knowledge on the formulation, analysis and implementation of fast solvers for inverse problems.
(b) New public-domain software implementing the new algorithms.
(c) Enhanced training of the next generation of researchers in inverse problems (mainly PhD students), with a particular focus on the derivation, analysis, and implementation of numerical methods for the solution thereof.
(d) Applications of this new knowledge in tomography, with particular emphasis on motion estimation.
WHO MIGHT BENEFIT FROM THE RESEARCH?
(a) The large community of academic beneficiaries listed above.
(b) Engineers and practitioners working on technologies and applications of tomographic imaging (in both a medical and an industrial setting).
(c) Members of the EPSRC Research Network in the Mathematics of Inverse Problems.
(d) The UK maintaining at the forefront of areas of numerical linear algebra, optimisation, and inverse problems.
HOW MIGHT THEY BENEFIT FROM THIS RESEARCH?
(a) The benefits for the academic community are described above.
(b) The public-domain implementations of the new methods will be available globally.
(c) A specialistic workshop will be organised.
(d) A software training day will be organised and open to all the interested scientists; videos of lectures will be available globally.
People |
ORCID iD |
| Silvia Gazzola (Principal Investigator) |
Publications
Alqahtani A
(2021)
On the block Lanczos and block Golub-Kahan reduction methods applied to discrete ill-posed problems
in Numerical Linear Algebra with Applications
Downing S
(2023)
Optimisation of seismic imaging via bilevel learning
Gazzola S
(2020)
An inner-outer iterative method for edge preservation in image restoration and reconstruction *
in Inverse Problems
Gazzola S
(2019)
Krylov Methods for Low-Rank Regularization
Gazzola S
(2021)
Regularization by Inexact Krylov Methods with Applications to Blind Deblurring
in SIAM Journal on Matrix Analysis and Applications
Gazzola S
(2020)
Krylov Methods for Low-Rank Regularization
in SIAM Journal on Matrix Analysis and Applications
Gazzola S
(2021)
Flexible Krylov Methods for Edge Enhancement in Imaging.
in Journal of imaging
Gazzola S
(2020)
Krylov methods for inverse problems: Surveying classical, and introducing new, algorithmic approaches
in GAMM-Mitteilungen
| Description | 1. We have extended the available solvers based on (flexible) Krylov methods to incorporate low-rank constraints on the solutions, either explicitly (enforcing a truncated-rank expression) or implicitly (including nuclear-norm penalisation). In the framework of imaging inverse problems (tomography, deblurring, image inpainting) we have also considered a variety of regularisers that can enhance edges in the reconstructions: in particular, one of such regularisers was never introduced in the literature, and all the considered regularises can be efficiently employed within solvers based on (flexible) Krylov methods. We have also devised a solver, based on flexible conjugate gradient, that incorporates box constraints into the solution. 2. We have analysed the theoretical convergence properties of new and available regularisation methods based on flexible Krylov methods, regarding them as specific instances of majorisation-minimisation methods. 3. We have proposed a novel framework for regularisation based on so-called inexact Krylov methods, allowing for uncertainty in the forward operator modelling the considered inverse problem. The new methods have been theoretically analysed and successfully applied to solve blind deblurring problems. 4. We have generated new software (mainly iterative solvers) to extend the MATLAB package IR Tools. This is published and maintained on github. 5. We have employed the so-called generalised Krylov subspace methods in the framework of a novel bilevel learning optimisation problem, where hyperparameters defining the variational regularsation methods are optimally learned using a set of training data. |
| Exploitation Route | 1. The theoretical investigation of flexible Krylov methods allows for principled extensions to a wide class of regularisers that are commonly used in imaging applications, potentially incorporating machine learning tools. Further theoretical investigations of the present flexible Krylov methods may include the analysis of the iteration-dependent regularisation parameter setting, possibly leveraging similarities with analogous approaches in proximal splitting methods. 2. The promising results on the use of inexact Krylov methods for blind image deblurring allow for a broader investigation of inexact Krylov solvers for use within variable projection methods for separable nonlinear inverse problems (arising in applications such as calibration or training of neural networks). Moreover, an analysis of the currently available `Generalised Krylov Subspace' methods in the framework of inexact Krylov methods may shed additional light on the properties and performance of the former. 3. Conversion of the MATLAB package IR Tools to Python may increase its accessibility. |
| Sectors | Digital/Communication/Information Technologies (including Software),Education,Healthcare |
| Description | Automatic balancing parameter selection for Tikhonov-TV regularisation |
| Organisation | University of Tehran |
| Country | Iran, Islamic Republic of |
| Sector | Academic/University |
| PI Contribution | I was involved in providing a mathematical justification for a novel regularisation parameter choice technique that was derived starting from Applied Statistics principles and was observed to work well in practice on linear inverse problems arising in Geophysics. In particular, I contributed to refine the mathematical formulation of the problem, and to derive some of its mathematical properties. |
| Collaborator Contribution | I collaborated with Prof Ali Gholami, from the Department of Geophysics, who came up with a practical rule to set a regularisation parameter in problems involving a mixture of 2-norm and TV regularisers. Such rule performed very well experimentally on a variety of linear inverse problems, but lacked any mathematical justification. |
| Impact | This collaboration resulted in a paper on `Automatic balancing parameter selection for Tikhonov-TV regularization', published in BIT. |
| Start Year | 2021 |
| Description | Edge-preserving regularization for image deblurring and tomography problems |
| Organisation | Tufts University |
| Country | United States |
| Sector | Academic/University |
| PI Contribution | I contributed to derive (theoretical justification and implementation) some regularization parameter choice strategies that could be used in the framework of a novel inner-outer iteration scheme for edge preservation when solving image deblurring and tomography problems. |
| Collaborator Contribution | My collaborators came up with a novel regulariser, which allowed for much improved edge reconstruction when considering problems arising in image deblurring and tomography applications. |
| Impact | A publication, with title `An inner-outer iterative method for edge preservation in image restoration and reconstruction', appeared in the journal `Inverse Problems'. |
| Start Year | 2019 |