Ph. D. Project
Sparse algorithms for inverse problems involving highly resolved signals and images
2016/10/01 - 2019/11/18
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
Biology, Signals and Systems in Cancer and Neuroscience