DS0704 - Fondements du numérique

Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés – BECOSE

Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés

BECOSE a pour objectif de développer et d'analyser des algorithmes<br />basés sur le concept de parcimonie pour traiter des problèmes inverses<br />mal conditionnés. L'enjeu de ces traitements numériques est majeur<br />dans différents secteurs d'applications de la mécanique des fluides<br />comme l'industrie automobile, l'aéronautique et l'environnement.

Enjeux et objectifs

La reconstruction parcimonieuse consiste à minimiser la fonction de<br />comptage (la «norme« L0) sous des contraintes imposées par le modèle<br />d'observation. Ce problème est connu pour être NP-difficile, et de<br />nombreux algorithmes sous-optimaux ont été proposés, en particulier<br />dans le cadre de l'échantillonnage compressé. Une stratégie populaire<br />consiste à relaxer la norme L0 par la norme L1, et de traiter le<br />problème de minimisation convexe résultant en ayant recours à des<br />algorithmes d'optimisation non-différentiable. Bien qu'une panoplie<br />d'analyses théoriques ont été proposées pour caractériser le succès et<br />la stabilité des méthodes de minimisation convexe, elles ne sont plus<br />valides pour des problèmes mal-conditionnés. Ces dernières années, un<br />nombre croissant de chercheurs reconnaissent que l'approche convexe<br />est souvent moins précise que les alternatives non-convexes. En<br />revanche, les algorithmes non-convexes les plus efficaces sont lents,<br />et ne possèdent généralement pas de garanties théoriques de succès. Le<br />but du projet BECOSE est de proposer des solutions algorithmiques<br />efficaces et des nouveaux outils théoriques dédiés à l'analyse des<br />algorithmes non-convexes de reconstruction parcimonieuse. Les<br />solutions algorithmiques proposées sont testées dans le cadre<br />applicatif de la PIV tomographique, où un volume 3D de particules en<br />mouvement doit être reconstruit à partir d'un nombre limité de<br />projections 2D. La principale difficulté est liée à la grande<br />dimension de ce problème inverse. Le nombre d'inconnues approche<br />typiquement le million de voxels, alors que l'information physique<br />contenue est de nature très parcimonieuse. Les algorithmes de<br />minimisation convexe ont été testés, et couplés avec d'autres<br />contraintes en plus de la parcimonie, comme la positivité des<br />voxels. Nous nous intéresserons aux approches non-convexes, qui<br />doivent conduire à une amélioration de la qualité des volumes<br />reconstruits.

Nouveaux algorithmes. Les problèmes inverses exploitant la nature
parcimonieuse de la solution conduisent à traiter le problème de
minimisation L0. Ce problème étant NP-difficile, de nombreuses
méthodes de résolution sous-optimales ont été proposées. La conception
de nouveaux algorithmes repose sur des formulations non convexes avec
des dictionnaires discrets ou continus. La littérature récente
souligne la pertinence de l'approche non-convexe pour des problèmes
inverses difficiles et le potentiel des algorithmes reposant sur des
dictionnaires continus. Proposer des algorithmes à la fois efficaces
et rapides reste un enjeu important pour les problèmes de grande
dimension.

Analyse théorique. L'analyse théorique vise à caractériser la
performance des algorithmes de reconstruction parcimonieuse. Les
conditions au pire cas sont connues pour être pessimistes car elles
reflètent mal le comportement moyen des algorithmes. Nous proposons de
revisiter certains algorithmes gloutons bien connus et leurs
conditions théoriques de reconstruction exacte dans le contexte des
dictionnaires continus. Nous proposons aussi d'améliorer la
compréhension au pire cas des algorithmes gloutons standards, et de
caractériser leur comportement en moyenne.

Cadre applicatif. Les algorithmes proposés seront appliqués à la PIV
tomographique. Cette technique a pour but de déterminer le déplacement
3D de particules ensemencées dans un fluide à partir de l'acquisition
d'un nombre limité d'images caméra 2D. Les méthodes actuelles de
reconstruction 3D sont restreintes à de petits volumes ce qui
constitue, avec les limites de précision et de résolution, les
principaux verrous à lever. L'approche parcimonieuse est la clé pour
aborder les problèmes de plus grande dimension. Les solutions
proposées seront validées grâce à des simulateurs réalistes et des
données réelles expérimentales.

1. Conception de nouveaux algorithmes de minimisation L0 sous
contrainte de positivité. L'article [Nguyen et al, Gretsi 2017] propose de
nouveaux algorithmes gloutons qui sont des améliorations de l'algorithme
Non-Negative Orthogonal Matching Pursuit (NNOMP), avec une
implémentation efficace basée sur l'algorithme de contraintes actives pour
résoudre des sous-problèmes de moindre carrés sous contrainte de
positivité.

2. Proposition de nouvelles techniques de « safe screening » pour le
problème de sélection de variables formulé comme un problème de
minimisation L1 (LASSO). Ces techniques visent à éliminer des variables
qui sont exclues de l'optimisation, tout en garantissant l'optimalité de la
solution [Herzet et Malti, ICASSP 2016].

3. Proposition de nouvelles conditions de reconstruction exacte du support
d'une représentation parcimonieuse pour les algorithmes OMP et OLS
[Herzet et al, IEEE TIT, 2016]. Ces conditions étendent les conditions
classiques de reconstruction exacte basées cohérence mutuelle aux
représentations parcimonieuses avec des coefficients décroissants, en
étant moins restrictives. Ce sont des conditions suffisantes mais aussi
nécessaires dans le cas non bruité.

4. Application de méthodes récentes de reconstruction parcimonieuse à
la reconstruction de volume en PIV tomographique [Barbu et Herzet, MST
2016]. La reconstruction de volume est abordée sous contrainte de
parcimonie (liée au nombre de particules ensemencées) et de positivité
des voxels. La reconstruction 3D est formulée comme un problème
d'optimisation convexe non-différentiable de grande dimension, et résolue
à l'aide de l'algorithme ADMM.

5. Organisation d'une session spéciale « Compressed sensing et inversion »
au colloque Gretsi 2017 (colloque français de traitement du signal et des
images).

Workpackage 1 «conception de nouveaux algorithmes«. Les perspectives à
court terme concernent la préparation d'un article de journal
contenant les nouveautés algorithmiques liées à la minimisation L0
sous contrainte de positivité.

Workpackage 2 «Analyse théorique des algorithmes«: le post-doctorant
recruté à l'INRIA Rennes en octobre 2017 travaillera sur plusieurs
axes de recherche :

- revisiter certains algorithmes gloutons bien connus et leurs
conditions théoriques de reconstruction exacte dans le contexte de
dictionnaires continus.

- améliorer la compréhension au pire cas des algorithmes gloutons
standards, et caractériser leur comportement en moyenne : quelle est
leur probabilité de reconstruire le support de la représentation
parcimonieuse étant donné une distribution des coefficients non-nuls ?


Workpackage 3 «cadre applicatif« : le doctorant recruté à l'ONERA en
octobre 2017 commencera par évaluer les méthodes de minimisation L0
dans le contexte de la PIV tomographique, puis s'intéressera aux
techniques de «screening« (aussi appelées «pruning«) visant à réduire
la dimension du dictionnaire dans les méthodes d'approximation
parcimonieuse, en étendant les méthodologies connues pour des
formulations convexes aux formulations non-convexes de type
minimisation L0.

Journaux internationaux.

1. C. Herzet, Drémeau et C. Soussen, Relaxed recovery conditions for
OMP/OLS by exploiting both coherence and decay, IEEE Trans. Inf. Theory ,
vol. 62, no. 1, pp. 459-470, jan. 2016.

2. I. Barbu et C. Herzet, A new approach for volume reconstruction in
TomoPIV with the alternating direction method of multipliers, Measurement
Science and Technology, vol. 27, no. 10, pp. 104002, oct. 2016.

Conférence internationale.

1. C. Herzet et A. Malti, Safe screening tests for LASSO based on firmly non-
expansiveness, in Proc. IEEE ICASSP , Shanghai, mars 2016, pp.
4732-4736.

Conférence nationale.

1. T. T. Nguyen, C. Soussen, J. Idier et E.-H. Djermoune, An optimized
version of NNOMP, in Proc. Gretsi, Juan-les-Pins, sept. 2017.

Au cours de la dernière décennie, la communauté du traitement du signal et des images a connu un intérêt immense pour le concept de représentation parcimonieuse. L'une des principales raisons est l'émergence de l'échantillonnage compressif (compressive sensing), un nouveau paradigme défiant les limites théoriques établies soixante ans plus tôt par Shannon. De nombreux chercheurs se sont intéressés à la prise en compte de la parcimonie pour résoudre des problèmes inverses relativement bien conditionnés. C'est le cas de l'échantillonnage compressif où les mesures sont indépendantes et aléatoires. Dans de nombreuses applications, le dictionnaire reliant les observations au signal inconnu est déterministe et mal conditionné. Les algorithmes les plus classiques ne donnent alors pas satisfaction, ni les outils d'analyse théorique. Le projet BECOSE propose d'étendre le spectre des techniques parcimonieuses bien au delà du contexte des dictionnaires aléatoires et bien conditionnés. Trois types de résultats sont attendus.

1. Conception de nouveaux algorithmes

Les problèmes inverses exploitant la nature parcimonieuse de la solution conduisent à traiter le problème de la minimisation L0. Ce problème étant NP-complet dans la plupart des situations, de nombreuses méthodes de résolution sous-optimales ont été proposées. La conception de nouveaux algorithmes pour les problèmes inverses mal conditionnés reposera sur des formulations non convexes avec des dictionnaires discrets ou continus. La littérature récente souligne en effet la pertinence de l'approche non-convexe pour des problèmes inverses difficiles et le potentiel des algorithmes reposant sur des dictionnaires continus. Proposer des algorithmes à la fois efficaces et rapides reste un enjeu important pour les problèmes de grande dimension.

2. Analyse théorique des algorithmes.

L'analyse théorique vise à caractériser la performance des algorithmes heuristiques de reconstruction parcimonieuse. Les conditions au pire cas sont connues pour être pessimistes car elles reflètent mal le comportement moyen des algorithmes. Néanmoins, des conditions nécessaires et suffisantes ne sont pas encore disponibles pour un certain nombre d'algorithmes de minimisation L0. Nous nous intéresserons aux algorithmes gloutons bidirectionnels (forward-backward) qui sont très bien adaptés aux problèmes mal conditionnés. Ils conduiront vraisemblablement à des garanties de bonne reconstruction largement plus intéressantes que les algorithmes de minimisation L0 plus simples. Nous proposons ensuite de mener une analyse en moyenne des algorithmes gloutons pour les dictionnaires déterministes, qui reste un problème ouvert majeur.

3. Cadre applicatif.

Les algorithmes proposés seront appliqués à la PIV tomographique (Particle Image Velocimetry), une technique de mécanique des fluides en pleine expansion dont l'impact sera crucial dans différents secteurs industriels comme l'environnement et les industries automobile et aéronautique. Cette technique a pour but de déterminer le déplacement 3D de particules ensemencées dans un fluide à partir de l'acquisition d'un nombre limité d'images caméra 2D. Ce problème inverse met en jeu des données de grande dimension. En effet, une séquence temporelle de volumes 3D hautement résolus doit être reconstruite. Les méthodes actuelles de reconstruction 3D et de suivi de fluide sont restreintes à de petits volumes ce qui constitue, avec les limites de précision et de résolution, les principaux verrous à lever. L'approche parcimonieuse est la clé pour aborder les problèmes de plus grande dimension. Les solutions proposées seront validées grâce à des simulateurs réalistes et des données réelles expérimentales.

Coordination du projet

Charles SOUSSEN (Centre de Recherche en Automatique de Nancy)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

ONERA Office National d'Etudes et de Recherches Aérospatiales
IRSTEA (EX CEMAGREF) - CENTRE RENNES Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture
INRIA RENNES - BRETAGNE ATLANTIQUE INRIA CENTRE RENNES - BRETAGNE ATLANTIQUE
IRCCyN Institut de Recherche en Communications et Cybernétique de Nantes
CRAN Centre de Recherche en Automatique de Nancy

Aide de l'ANR 490 462 euros
Début et durée du projet scientifique : décembre 2015 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter