Ph. D. Project : Sparse algorithms for inverse problems involving highly resolved signals and images
Dates :  2016/10/01  2019/09/30  
Student:  Thi Thanh NGUYEN  
Manager(s) CRAN:  ElHadi DJERMOUNE  
Other Manager(s):  IDIER Jérôme (jerome.idier@irccyn.ecnantes.fr)  
Full reference:  Background  This PhD thesis is about illposed inverse problems regularized by sparsity. In the last decade, the signal and image processing community has witnessed a tremendous interest in sparse representations, and many sparse inversion algorithms were proposed. However, most algorithms have strong limitations when dealing with highly resolved signals, because the dictionary then becomes highly redundant. In such a case, more involved algorithms need to be proposed. In the French ANR BECOSE project, the proposed algorithms will be assessed in the context of tomographic Particle Image Velocimetry (PIV), a rapidly growing imaging technique giving rise to a difficult 3D nonnegative image reconstruction problem. In this application, a main bottleneck is to design effective algorithms capable of reconstructing highly resolved images for various sparsity levels. Objectives  Sparse regularization consists of representing the signal or image of interest by means of a limited number of atoms belonging to some overdetermined dictionary A. Sparse reconstruction can be formulated as a minimization problem of the form: (1) min_x {  yAx _2^2 + lambda  x _0 }, where the l_0"norm"  x _0 counts the number of nonzero elements in vector x. This problem is combinatorial per se, the main difficulty being to find the support of x. Moreover, the l_0 minimization problem is wellknown to be NPhard. We can distinguish two types of suboptimal algorithms: 1. Greedy l_0 techniques (e.g., OMP, OLS and their "forwardbackward" extensions) aim to solve (1) by selecting or deselecting one atom per iteration. They are usually wellsuited to very sparse problems, where  x _0 is expected to be low, and lambda is set to a large value. 2. The approaches relying on an approximate formulation of (1), where  x _0 is replaced by some continuous sparsity measure sum_i phi(x_i) that is nondifferentiable at 0. This strategy is usually better suited to moderate sparse regularization levels. Recently, several authors have shown that both formulations are equivalent for some classes of nonconvex functions phi. These findings call for new algorithmic breakthrough, since the exact l_0 minimization can be addressed using effective continuous nonconvex optimization algorithms. Three complementary objectives will be pursued in this PhD thesis. I. Continuation  The first is about the continuation concept. Continuation algorithms aim to address (1) for a continuum of lambda's. We have recently proposed forwardbackward greedy continuation algorithms (CSBR, l_0Path Descent), and shown that the continuation approach facilitates the unsupervised estimation of the sparsity level  x _0. Our objective will be to propose algorithms dedicated to moderately sparse regularization, using continuous relaxations of the l_0norm. II. Sparsity and nonnegativity  A second objective is to handle nonnegativity constraints on top of sparse regularization. This does not raise strong algorithmic difficulties when the sparsity measure is continuous. On the contrary, the design of nonnegative greedy algorithms (extensions of OMP or OLS) is much harder, and several authors have recently proposed dedicated solutions. Our goal is to propose fast implementations of nonnegative versions of forwardbackward which will be compatible with the continuation strategy. III. Discrete vs. continuous dictionaries  The dictionary A is usually induced by a discretization of atoms over a finite grid. For instance, a 3D grid is considered for the volume reconstruction problem in PIV tomography. The choice of the grid is critical, because the difficulty of the inverse problem is directly related to the grid resolution. Indeed, both the number of unknowns and the condition number of the dictionary (and of related subdictionaries) dramatically increase for highly resolved grids. The continuous dictionary approach (i.e., the dictionary becomes a continuum of atoms) is a promising alternative to avoid these numerical problems related to discretization. Very recently, some algorithms were proposed as extensions of discrete algorithms for sparse deconvolution and Fourier synthesis problems. The third objective of the PhD thesis is to understand whether the continuous dictionary approach can indeed lead to a substantial gain of effectiveness and efficiency with respect to the discrete algorithms we have proposed so far. We will further propose new algorithms working for continuous dictionaries. 

Keywords:  Inverse problems, sparsity, high resolution, image reconstruction, tomography  
Department(s): 


Publications:  hal00948313, hal00443842, hal00680714 + CRAN  Publications 