Mixed Integer programming Methods for Optimization of Sparse Approximation criteria – MIMOSA

The MIMOSA project lies at the frontier between signal processing and operations research. It aims to propose new optimization strategies, based on mixed integer programming methods, in order to solve exactly some L0-norm-based sparse approximation problems encountered in various signal processing applications.

Sparsity-inspired methodology has become a prolific field of research over the past fifteen years, giving birth to fundamental works in information theory, many dedicated algorithms and a wide range of signal processing applications (among others, compressed sensing, denoising, inpainting, inverse problems). Sparse approximation addresses the problem of approximately fitting a data set by a linear combination of elementary components (the columns of matrix called dictionary) with as few elements as possible (with the lowest L0-"norm"). It is essentially a combinatorial optimization problem, which is usually considered too difficult to solve exactly in practical instances. Therefore, the very vast majority of algorithms in the literature either consider continuous relaxation of the L0 norm (among which the convex L1-norm has become the gold standard), which leads to more efficient optimization, or rely on heuristic, partial, exploration strategies such as greedy algorithms. However, existing optimality proofs of such methods with respect to the original L0-norm problem rely on very restrictive hypotheses on the structure of the dictionary defining the model. Such sufficient conditions are far from being satisfied in many practical instances where the dictionary columns are highly correlated. This particularly arises with ill-posed inverse problems encountered in different physical contexts, as those addressed in the scope of the MIMOSA project.

MIMOSA focuses on mixed integer programming (MIP) methods in order to perform exact optimization of sparse approximation criteria. By ``exact'', we mean that addressing sparse optimization through the resolution of a MIP problem allows one to obtain a solution which is guaranteed to be a global minimizer of the L0-norm problem. Here, optimality of the solution is not a consequence of prior assumptions on the problem structure, it is obtained as an output of the MIP resolution. Therefore, such methods are applicable, with optimality guarantees, to every sparse estimation problem. The computational cost for such strategies is obviously much higher than that of usual (suboptimal) methods. Preliminary works have shown, however, that such a strategy may be feasible for limited size but difficult problems, whereas exhaustive combinatorial search remains computationally prohibitive and usual strategies fail in locating the global optimizer.

This project aims to study several levers in order to tackle larger and more complex sparse approximation problems with exact algorithms, and then addresses different practical application cases. The common thread running through the proposed research axes relies on exploiting certain knowledge of the problem from the sparse approximation perspective, in order to build efficient, dedicated, optimization methods. Expected scientific results therefore concern:
- the development of MIP-based optimization strategies that are specific to sparse approximation, whose gain in computational efficiency with respect to generic MIP methods will open the possibility to tackle higher-dimensional problems;
- the application of the corresponding methods to real signal processing problems, with a specific focus on three expertise fields of the project coordinator: sparse deconvolution in ultrasonic nondestructive testing, sparse unmixing for hyperspectral imaging, and sparse spectral analysis of time series with missing data;
- the delivery of efficient optimization codes to the scientific community, in order to ensure a high dissemination level of the methodological work, and the valorization of the works through integration in off-the-shelf MIP software.