Sparsity Regularization for Inverse Problems -- Theory, Algorithm and Application

Lead Research Organisation: University College London
Department Name: Computer Science

Abstract

One fundamental task in many scientific and engineering disciplines is to probe the world around us, often in the form of deducing physical laws or determining the parameters therein from experimental data. This gives rise to a wide variety of inverse problems of inferring the cause of observed physical phenomena or determining medium properties of the concerned object from the measured responses. A model based approach to inverse problems assumes a known relation between the unknown physical quantity and the measured responses, in the form of linear or nonlinear equations. Inverse problems are numerically challenging to solve since they are unstable with respect to data noise. One of the most successful and powerful techniques is to incorporate a priori knowledge by means of regularization. This project focuses on one specific regularization technique based on sparsity constraints.

In sparsity regularization, one looks for an approximate solution that has as few nonzero entries (or a small support) as possible. That is, we aim at explaining the physical phenomenon by simply using a small number of parameters. In this project, we study the mathematical theory, computational techniques and practical applications of the approach, especially by using a nonconvex penalty on the sought-for solution. There are several nonconvex penalties proposed in the literature, especially in statistics and machine learning, and we shall consider, for example, the popular l0 penalty, bridge penalty, smoothly clipped absolute deviation, minmax concavity penalty and clipped l1 penalties. Despite their popularity, their use and study in the context of inverse problems remain very limited. The proposed project examines these techniques in the framework of inverse problems theory. Specifically, we focus on the following objectives during the project period: (a) to develop a computational method of primal-dual active set type for efficiently solving the regularized model (with nonconvex penalties) and rigorously establish the convergence of the algorithm; (b) to develop applicable choice rules for the regularization parameter, and to analyze the structural properties of "local" minimizers; (3) to apply the nonconvex approach to tomography imaging, by combining it with an adaptive finite element method.

The computational technique to be developed, primal dual active set algorithm, is widely applicable to many other areas, especially machine learning and statistics, since these nonconvex models have their origins and motivations there. Mathematically, the theory of sparsity regularization will shed valuable lights into the analysis of nonsmooth regularization, which shares common structures with many important mathematical models arising in imaging and signal processing. The specific choice rule for the regularization parameter will enable automatic parameter selection yet with rigorous theoretical justification, and improve the efficiency of the current practice based on tedious trial and error. The research in tomography imaging, i.e., the application of nonconvex penalty and adaptive algorithm, will directly impact the medical imaging community. There are a large group of researchers working on tomography imaging that will benefit directly from the research, and the obtained research results will be presented to them continuously. More generally, it provides guidance for developing efficient algorithms for nonlinear inverse problems for differential equations. In summary, the project will take sparsity regularization for inverse problems to the next level.

Planned Impact

Sparsity regularization is a highly active research area in Inverse Problems, and it has a broad range of applications in biomedical imaging, e.g., magnetic resonance imaging, and industrial process such as geophysical prospecting and remote sensing. The proposed research is likely to significantly expand the scope of inverse problems. The obtained research results will benefit not only researchers specialized in Inverse Problems, but also broader communities, e.g., machine learning, statistics, image and signal processing. Further, the research on the application of the sparsity regularization to tomography imaging will directly impact related medical imaging modalities and hence human well-being in the UK. We discuss these impacts separately below.

1) Sparsity regularization is an important example of nonsmooth regularization (or regularization in Banach spaces), which is widely applied in the broad area of imaging. The mathematical techniques developed might be extended to many other important imaging models, e.g., structural sparsity, leading to better reconstructions and facilitating the use of these models in practice.

2) The nonconvex models discussed in the project were originally proposed in statistical literature and machine learning, and have gained immense interest in statistics. These models are expected to play an important role in analyzing and learning "big data", e.g., the recommendation system of popular Amazon portal and film evaluation at the online movie provider NetFlix, where sparsity represents an important feature. The computational techniques developed will help solve related mathematical models efficiently, and thereby the research will improve the quality of daily life, in addition to promoting the research activities in statistics and machine learning.

3) The software package to the released is applicable to many different model, and potentially adopted in commercial packages (e.g., specialized in medical imaging). Experience indicates that such a practice makes an enormous difference to the impact of new computational methods, because it allows users to test and evaluate the techniques to an unlimited extent. Feedback in terms of bug reports, discussions, and contributed improvements can take place much faster than through formal publication channels, and will lead to strong evidence for confidence via extensive independent testing.

4) In the project, we shall study the application of sparsity regularization to tomography imaging, such as electrical impedance tomography and diffuse optical tomography, by combining it with the adaptive finite element method. The research in this aspect will directly impact medical imaging techniques, either enhancing the reconstruction resolution or improving the computational efficiency. The Center for Medical Image Computing at UCL collaborates intensively with faculties from Department of Medical Physics and Bioengineering, which provides a seamless conduit for transferring latest mathematical developments into practical applications. We expect the techniques we develop to be taken up in several other applications both within biomedical imaging and further, in non-destructive testing, industrial tomography, and in geophysical applications including oil and gas exploration.

We expect that with these developments, the research field of "nonconvex sparsity regularization" is likely to provoke intense interest from mathematicians, physicists, computational scientists, statisticians, and engineers.

Publications

10 25 50

publication icon
Alberti G (2016) The Linearized Inverse Problem in Multifrequency Electrical Impedance Tomography in SIAM Journal on Imaging Sciences

publication icon
Ammari H (2019) Linearized reconstruction for diffuse optical spectroscopic imaging in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

publication icon
Arridge S (2018) Variational Gaussian approximation for Poisson data in Inverse Problems

publication icon
Duan B (2018) Space-Time Petrov-Galerkin FEM for Fractional Diffusion Problems in Computational Methods in Applied Mathematics

publication icon
Ito K (2015) On the sectorial property of the Caputo derivative operator in Applied Mathematics Letters

 
Description 1. A new data analysis tool by exploiting the signal structure has been developed, building on the concept of group sparsity. 2. A new image reconstruction technique for multifrequency electrical impedance tomography has been developed. 3. a novel adaptive finite element method for electrical impedance tomography inversion
4. a new algorithm for sparse recovery (with better convergence). 5. novel numerical analysis of anomalous diffusion 6. new mathematical theory for magnetic particle imaging. 7. novel analysis of randomized Kaczmarz method 8. new approach to handle Poisson data. 9. new analysis of stochastic gradient descent for linear inverse problems. 10. new reconstruction algorithms for discontinuous conductivities in acousto-electric impedance tomography. 11. further developments of stochastic iterative methods for nonlinear inverse problems. 12. new reconstruction method in magnetic particle imaging. 13. adaptive method for inverse conductivity problems with discontinuous coefficients.
Exploitation Route The findings can be extended to many other contexts, especially biomedical imaging and signal processing, e.g., photoacoustic.
The findings on stochastic iterative methods have led to a new research project, funded by EPSRC.
Sectors Digital/Communication/Information Technologies (including Software),Healthcare

 
Description Our work on the multifrequency electrical impedance tomography by the group sparsity approach starts to attract the attention of applied disciplines directly: the engineers now start to understand the potential of multifrequency data. During the last year, we have developed a new mathematical theory for magnetic particle imaging, a newly emerged medical imaging modality. The findings can shed insight into the mechanism of the modality, and it is expected to be picked up by the community. Over the last years, a new theory for regularization has been developed, i.e., stochastic iterative regularization, which is expected to shed important insights into many important problems, including deep neural networks. This research is currently supported by EPSRC for further research, due to its practical and theoretical importance.
First Year Of Impact 2016
Sector Healthcare
Impact Types Cultural

 
Description Stochastic iterative regularization: theory, algorithms and applications
Amount £385,265 (GBP)
Funding ID EP/T000864/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Public
Country United Kingdom
Start 08/2019 
End 08/2022
 
Title group sparse modeling 
Description We developed a novel approach to extract information in the data, in the form that the target signal is clustered and sparse. 
Type Of Material Data analysis technique 
Provided To Others? No  
Impact The approach is provided to the public domain via the release of the related software. 
 
Title iterative soft/hard thresholding continuation 
Description The software package for a new algorithm for sparse recovery with l0 or l1 penalty. A preprint has been made and submitted for publication 
Type Of Material Computer model/algorithm 
Provided To Others? No  
Impact This package is now released in the public domain. 
URL http://www0.cs.ucl.ac.uk/staff/b.jin/companioncode.html
 
Description Adaptive finite element method for inverse problems 
Organisation Shanghai Normal University
Country China 
Sector Academic/University 
PI Contribution This project aims at developing novel adaptive finite element method for inversion. In this first step, we developed a new technique for adaptive inversion. We formulated the problem properly, develop an adaptive strategy, analyzed its convergence, and provided the numerical experiments.
Collaborator Contribution The project partner developed and analyzed the adaptive strategy.
Impact One joint publication at IMA Journal of Numerical Analysis.
Start Year 2015
 
Description High order schemes for anomalous diffusion 
Organisation Hong Kong Polytechnic University
Department School of Nursing
Country Hong Kong 
Sector Academic/University 
PI Contribution In this collaboration, we aim at systematically developing a class of high order schemes for subdiffusion problems. This has been a long challenging issue. Our contribution lies in properly formulating the problem, proposing the strategy and analyzing the strategy.
Collaborator Contribution The partner contributed substantially to the analysis of the schemes.
Impact We have prepared two preprints, and are being considered for possible journal publication.
Start Year 2016
 
Description magnetic particle imaging 
Organisation University of Bremen
Country Germany 
Sector Academic/University 
PI Contribution This is a new project started last year, when Dr. Tobias Kluth from University of Bremen visited me. The project is to develop mathematical models for a new imaging modality, i.e., magnetic particle imaging. I am mainly involved in the mathematical theory and algorithmic developments.
Collaborator Contribution Dr. Kluth provided the relevant mathematical models, and also numerous experiments.
Impact This has resulted in one preprint.
Start Year 2017
 
Description project on multifrequency electrical impedance tomography 
Organisation ETH Zurich
Country Switzerland 
Sector Academic/University 
PI Contribution The new project is concerned with image reconstruction with an emerging imaging modality, multifrequency electrical impedance tomography. In the project, together with the partner, we have developed new reconstruction techniques, and provide theoretical justifications of the approach for handling modeling errors, which represents one of the main challenges in the application of EIT.
Collaborator Contribution In the project, together with our group, the partner have developed new reconstruction techniques, and provide theoretical justifications of the approach for handling modeling errors, which represents one of the main challenges in the application of EIT.
Impact One preprint has been produced from the collaboration.
Start Year 2015
 
Title primal dual active set algorithms for group sparse recovery 
Description the software package accompanies a preprint, for the reproducible research. The preprint is under review with a journal. 
Type Of Technology Software 
Year Produced 2016 
Open Source License? Yes  
Impact none 
URL http://www0.cs.ucl.ac.uk/staff/b.jin/software/gpdasc.zip