# Exact resolution of l0-norm sparsity-constrained inverse problems through mixed integer programming

Sébastien Bourguignon, LS2N, Ecole Centrale de Nantes

mardi 11 juillet 2017 à 13h30

B014

Sparse approximation of data y in dictionary A aims at finding a vector x having as few non-zero components (the lowest l0 "norm") as possible, such that Ax approximates y. It formulates a bi-objective optimization problem, where both a misfit function and the sparsity measure are minimized. Optimization is essentially combinatorial and is often tackled either through convex relaxation of the l0 norm, or by heuristic combinatorial exploration techniques. Optimality conditions then rely on prior structural assumptions on A and on sufficient sparsity of the solution x. In many inverse problems, such conditions are not satisfied and the aforementioned methods clearly fail in locating the global minimum. We study global optimization methods of the original l0-norm sparse approximation problem based on solving mixed integer programming problems, which involve both continuous and integer variables. Different problem formulations are proposed, which are studied in terms of computational efficiency. We show that exact optimization of such problems is possible on certain moderate size inverse problems, whereas usual methods fail in locating sparsest solutions and exhaustive enumeration remains prohibitive. Applications to sparse deconvolution and spectral unmixing are presented, for which more accurate results are achieved compared to standard sparse approximation algorithms.

Page web de Sébastien Bourguignon : http://www.irccyn.ec-nantes.fr/ bourguignon/