Archives de catégorie : [:fr]optimisation[:en]optimization

Axe 6 : Algorithme d’optimisation : méthodes déterministes et stochastiques

En géométrie de l’information, les données statistiques prennent leurs valeurs dans des ensembles munis d’une structure de variété riemannienne, de dimension finie ou infinie. Les estimateurs de quantités relatives à ces données sont des moyennes, des médianes, ou plus généralement des p-moyennes de ces données. Des algorithmes stochastiques pour trouver ces p-moyennes sont très utiles pour toutes les applications pratiques qui ont été développés dans les publications citées ci-dessous. On peut en particulier citer des applications au traitement des signaux radar stationnaires. Un enjeu très important est de pouvoir considérer des signaux non stationnaires. Pour cela il faut pouvoir travailler sur des espaces de chemins dans des variétés riemanniennes, et développer une bonne notion de métrique, de distance, et de moyenne pour ces chemins.

Des nouveaux algorithmes stochastiques de type Robbins-Monro sont également proposés afin d’estimer plus efficacement les paramètres inconnus de modèles de déformation. Ces procédures d’estimation sont mises en oeuvre sur des données réelle d’ECG afin de détecter des problèmes d’arythmie cardiaque.

Les méthodes proximales ont connu un très grand succès en traitement d’images pour proposer des algorithmes efficaces pour calculer les solutions des problèmes considérées. Un thème majeur de l’équipe est l’étude de la convergence de tels algorithmes, de leur vitesse, et de leur robustesse aux erreurs.

Convergence de FISTA

Charles Dossal a démontré avec Antonin Chambolle en 2015 la convergence d’un algorithme extrêmement populaire depuis son introduction en 2008 par Beck et Teboulle (car étant extrêmement performant en pratique), l’algorithme FISTA (Fast Iterative Shrinkage Algorithm). La convergence de cet algorithme est restée un problème ouvert dans les communautés optimisation/compressed sensing/traitement d’images/machine learning pendant 7 ans, jusqu’au travail de Charles Dossal.

Relaxations de fonctionnelles non-convexes

Nous étudions différentes relaxations pour minimiser des fonctionnelles non convexes qui apparaissent en traitement d’images. Des problèmes comme la segmentation d’image peuvent en effet s’écrire comme un problème de minimisation d’une certaine fonctionnelle, le minimiseur représentant la segmentation recherchée.

Différentes méthodes ont été proposées pour trouver des minima locaux ou globaux de la fonctionnelle non convexe du modèle de Mumford-Shah constant par morceaux à deux phases. Certaines approches utilisent une relaxation convexe qui permet d’obtenir des minima globaux de la fonctionnelle non convexe. On rappelle et compare certaines de ces méthodes et on propose un nouveau modèle par bande étroite, qui permet d’obtenir des minima locaux tout en utilisant des algorithmes robustes qui proviennent de l’optimisation convexe. Ensuite, on construit une relaxation convexe d’un modèle de segmentation à deux phases qui repose sur la comparaison entre deux histogrammes donnés et les histogrammes estimés globalement sur les deux régions de la segmentation.

Des relaxations pour des problèmes multi-étiquettes à plusieurs dimensions comme le flot optique sont également étudiées. On propose une relaxation convexe avec un algorithme itératif qui ne comprend que des projections qui se calculent exactement, ainsi qu’un nouvel algorithme pour une relaxation convexe sur chaque variable mais non convexe globalement. On étudie la manière d’estimer une solution du problème non convexe original à partir d’une solution d’un problème relaxé en comparant des méthodes existantes avec des nouvelles.

Etude des méthodes parcimonieuse pour la tomographie

Dans le cadre de la tomographie avec un nombre limité d’angles, le problème inverse résultant est mal conditionné. Les algorithmes « classiques », analytiques et algébriques, produisent de nombreux artefacts. Les méthodes d’optimisation permettent de résoudre ce problème à l’aide d’une régularisation. Dans mes travaux, je suppose les images parcimonieuses ou parcimonieuses dans une représentation donnée. Une image parcimonieuse est une image qui possède peu de composantes non nulles. Pour promouvoir cette parcimonie, je vais régulariser le problème avec une norme \ell^1 et résoudre l’un des deux problèmes équivalents ci dessous.

(1)   \begin{equation*} \underset{x\in \mathbb{R}^n}{\text{min}}\ \|x\|_1 \text{ s.t. } \|\mathbf{A}x-y\|_2\le \delta \end{equation*}

(2)   \begin{equation*} \underset{x\in \mathbb{R}^n}{\text{min}}\ \frac{1}{2}\|\mathbf{A}x-y\|_2 + \lambda \|x\|_1 \end{equation*}

Mon travail consiste à évaluer les limites théoriques de ces problèmes tout en étant le plus proche de la réalité. De récents travaux [3] ont mis en lumière des conditions suffisantes assurant la reconstruction de l’image par minimisation \ell^1 et fournissent une erreur de cette reconstruction [1]. Ces conditions nécessitent l’existence d’un vecteur particulier appelé certificat dual. Selon les applications, il peut être possible de calculer un candidat qui sous condition sera un certificat dual [2,4].

Mes travaux couvrent essentiellement la construction de tels candidats. Je propose, dans mes travaux, une approche gloutonne de calculer un candidat qui est un certificat dual pour presque toutes les images « reconstructibles » et minimisant l’erreur théorique de reconstruction.

[1] Charles Dossal and Remi Tesson. Consistency of l1 recovery from noisy deterministic measurements. Applied and Computational Harmonic Analysis, 2013.

[2] Jean-Jacques Fuchs. Recovery of exact sparse representations in the presence of bounded noise. Information Theory, IEEE Transactions on, 51(10) :3601–3608, 2005.

[3] Markus Grasmair, Otmar Scherzer, and Markus Haltmeier. Necessary and sufficient conditions for linear convergence of l1-regularization. Commun. Pure and Appl. Math., 64(2) :161–182, 2011.

[4] Samuel Vaiter, Gabriel Peyré, Charles Dossal, and Jalal Fadili. Robust sparse analysis regularization. 2011.