MIMOSA is a currently ongoing research project funded by Agence Nationale de la Recherche from 2017 to 2021 (young researchers / JCJC program, no. ANR-16-CE33-0005-01). MIMOSA 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 difficult L0-norm-based sparse approximation problems encountered in various signal processing applications.

Objectives of the MIMOSA project

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 (e.g., inverse problems, compressed sensing, denoising, inpainting). Sparse approximation addresses the problem of approximately fitting a data set by a linear combination of elementary components involving as few elements as possible (with the lowest L0 “norm”). It essentially formulates a combinatorial optimization problem, which is usually considered too difficult for practical instances. Therefore, most methods in the literature either consider the continuous relaxation of the L0 norm, or rely on partial exploration strategies. However, in the case of many ill-posed inverse problems, such methods usually fail in locating the global optimizer.

The MIMOSA project addresses exact optimization of sparse approcimation criteria through mixed integer programming (MIP) methods. By exact, we mean that the obtained solution is guaranteed to be a global minimizer of the L0-norm problem. The computational cost for such strategies is obviously much higher than for standard, suboptimal, methods. Preliminary works have shown, however, that such a strategy may be feasible for limited size but difficult problems.

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, global optimization methods, based on branch-and-bound / branch-and cut tree search exploration strategies. 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 sparse deconvolution, sparse unmixing for hyperspectral imaging, and sparse spectral analysis of time series;
  • the delivery of efficient optimization codes to the scientific community, in order to ensure a high dissemination level, and the valorization of the works through integration in off-the-shelf MIP software. Conversely, it is expected that MIMOSA’s methodological contribution will improve software efficiency on new classes of MIP problems.