Ph. D. Project
Sparse algorithms for inverse problems involving highly resolved signals and images
2016/10/01 - 2019/09/30
Other supervisor(s):

This PhD thesis is about ill-posed 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 non-negative image reconstruction problem. In this application, a main bottleneck is to design effective algorithms capable of reconstructing highly resolved images for various sparsity levels.


Sparse regularization consists of representing the signal or image of interest by means of a limited number of atoms belonging to some over-determined dictionary A. Sparse reconstruction can be formulated as a minimization problem of the form:

(1) min_x { || y-Ax ||_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 well-known to be NP-hard. We can distinguish two types of sub-optimal algorithms:

1. Greedy l_0 techniques (e.g., OMP, OLS and their "forward-backward" extensions) aim to solve (1) by selecting or de-selecting one atom per iteration. They are usually well-suited 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 non-differentiable 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 forward-backward greedy continuation algorithms (CSBR, l_0-Path 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_0-norm.

II. Sparsity and non-negativity

A second objective is to handle non-negativity 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 non-negative 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 non-negative versions of forward-backward 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 sub-dictionaries) 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.
Inverse problems, sparsity, high resolution, image reconstruction, tomography
The 3-year PhD thesis (Oct 2016 -> Sept. 2019) is granted by the French ANR project BECOSE: "BEyond COmpressive SEnsing: Sparse approximation algorithms for ill-conditioned inverse problems".

Required skills:
The candidate needs a Master or Engineering degree. He/she should have a strong background in mathematics and signal and image processing. He/she will have excellent programming skills (Matlab, C/C++, etc.) and good skills in English, both written and oral.

The PhD thesis will be co-supervised by Charles Soussen (CRAN, PhD supervisor), El-Hadi Djermoune (CRAN) and Jérôme Idier (IRCCyN). It will take place at CRAN (Nancy), with several stays at IRCCyN (Nantes).

Please contact Charles Soussen ( and send your CV, covering letter, one (at least) reference letter and your last academic results with rankings, when applicable.
Biology, Signals and Systems in Cancer and Neuroscience
French National Agency (ANR), BECOSE project: : BEyond COmpressive SEnsing