Programmation mixte en nombres entiers pour l'optimisation de critères d'approximation parcimonieuse – MIMOSA

Le projet MIMOSA se trouve à l'interface du traitement du signal et de la recherche opérationnelle. Son objectif est de proposer de nouvelles stratégies d'optimisation, basées sur des méthodes de programmation mixte en nombres entiers, pour résoudre de manière exacte des problèmes d'approximation parcimonieuse en norme L0 rencontrés dans différentes applications en traitement du signal.

Le développement de méthodes reposant sur la parcimonie est devenu un domaine de recherche très actif au cours des quinze dernières années, avec des travaux fondamentaux en théorie de l'information, de nombreux algorithmes dédiés et de nombreuses applications en traitement du signal (entre autres, l'échantillonnage compressif, le débruitage, l'inpainting ou les problèmes inverses). L'approximation parcimonieuse consiste à approcher un jeu de données par une combinaison linéaire d'éléments d'un dictionnaire comportant le plus faible nombre de composantes non-nulles (la plus petite "norme" L0). C'est un problème d'optimisation essentiellement combinatoire, généralement considéré trop difficile à résoudre de façon exacte sur des problèmes réels. La plupart des algorithmes existants repose soit sur une relaxation continue de la norme L0 (essentiellement par la norme L1, convexe) permettant une optimisation efficace, soit sur des stratégies heuristiques d'exploration combinatoire partielle, comme les algorithmes gloutons. Cependant, les conditions d'optimalité existantes pour de telles approches vis-à-vis du problème L0 initial reposent sur des hypothèses très restrictives, qui sont loin d'être vérifiées dans de nombreux problèmes réels où le dictionnaire est très corrélé. C'est le cas des problèmes inverses mal posés rencontrés dans différents domaines de la physique, dont ceux abordés dans le projet MIMOSA.

Ce projet s'intéresse aux méthodes de programmation mixte en nombres entiers (MIP) pour l'optimisation exacte de critères d'approximation parcimonieuse, permettant d'obtenir une solution globale du problème en norme L0. Ici, l'optimalité de la solution ne résulte pas d'hypothèses a priori sur la structure du problème, elle est obtenue en sortie de la résolution du problème MIP, ce qui rend ces méthodes applicables de manière garantie à tout problème d'estimation parcimonieuse. De telles méthodes ont évidemment un coût de calcul bien plus élevé que les approches classiques (sous-optimales). Cependant, des résultats préliminaires ont montré qu'elles pouvaient aborder des problèmes de taille limitée mais difficiles, sur lesquels la recherche combinatoire exhaustive reste inenvisageable et pour lesquels les méthodes classiques échouent.

Ce projet vise à étudier différents leviers afin de pouvoir aborder des problèmes d'approximation parcimonieuse de taille plus importante et plus complexes par des algorithmes exacts, ainsi que leur application à différents problèmes réels. Le fil conducteur guidant l'ensemble des travaux réside en l'exploitation de connaissances du problème du point de vue de l'approximation parcimonieuse, afin de construire des méthodes d'optimisation dédiées performantes. Les résultats scientifiques attendus concernent donc :
- le développement de stratégies d'optimisation MIP spécifiques à l'approximation parcimonieuse, pour lesquelles le gain en coût de calcul par rapport aux approches MIP génériques permettra d'aborder des problèmes de plus grande dimension ;
- l'application de ces méthodes à des problèmes concrets de traitement de données dans trois domaines d'expertise du coordinateur : la déconvolution parcimonieuse en contrôle non destructif, le démélange parcimonieux en imagerie hyperspectrale et l'analyse spectrale parcimonieuse de séries temporelles à données manquantes ;
- la mise à disposition de codes informatiques pour l'ensemble de la communauté scientifique afin d'assurer la meilleure diffusion possible des travaux, et leur valorisation à travers leur intégration dans un logiciel d'optimisation MIP générique.