Orateur
Description
The past decade has witnessed a tremendous interest in the concept of sparse representations in signal and image processing. Inverse problems involving sparsity arise in many application fields such as nondestructive evaluation of materials, electroencephalography for brain activity analysis, biological imaging, or fluid mechanics, to name a few. In this lecture, I will introduce well-known greedy algorithms and show how they can be used to address ill-posed inverse problems regularized by sparsity. Orthogonal greedy algorithms are popular iterative schemes for sparse signal reconstruction. Their principle is to sequentially select atoms in a given dictionary and to update the sparse approximation coefficients by solving a least-square problem whenever a new atom is selected. Two classical greedy algorithms will be put forward, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Their popularity relies on the fact that fast solvers are available, since least-square problems can be solved recursively. I will then introduce stepwise extension of greedy algorithms, where an early wrong atom selection can be counteracted by its further removal from the active set. I will also address non-negative extension of greedy algorithms for inverse problems regularized by both sparsity and non-negativity. In the latter algorithms, a series of non-negative least-squares subproblems are solved. I will then discuss how orthogonal greedy schemes can be adapted, and show that fast implementations are still possible, based on more involved strategies for recursively solving non-negative least-square problems. The last part of my talk will be dedicated to the theoretical analysis of greedy algorithms, aiming to characterize the performance of sparse algorithms in terms of exact recovery guarantees. I will give a flavor of the main concepts behind classical exact recovery analysis techniques.
