ED Mathématiques et Informatique
Algorithmes non-convexes rapides pour la reconstruction de signaux parcimonieux sans grille
par Pierre-Jean BENARD (IMB - Institut de Mathématiques de Bordeaux)
Cette soutenance a lieu à 10h00 - Salle de conférences Institut de Mathématiques de Bordeaux (IMB) UMR 5251, A33 Université de Bordeaux 351, cours de la Libération - F 33 405 TALENCE
devant le jury composé de
- Yann TRAONMILIN - Chargé de recherche - Institut de mathématiques de Bordeaux, IMB - Directeur de these
- Pierre WEISS - Directeur de recherche - Institut de Recherche en Informatique de Toulouse - Rapporteur
- Jérôme IDIER - Directeur de recherche - Laboratoire des Sciences du Numérique de Nantes - Rapporteur
- Jean-François AUJOL - Professeur - Institut de mathématiques de Bordeaux, IMB - CoDirecteur de these
- Caroline CHAUX - Directrice de recherche - IPAL, CNRS, International Research Lab - Examinateur
- Baudouin DENIS DE SENNEVILLE - Directeur de recherche - Institut de mathématiques de Bordeaux, IMB - Examinateur
- Irène WALDSPURGER - Chargée de recherche - CEREMADE, Université Paris-Dauphine - Examinateur
La reconstruction de signaux parcimonieux en dimension infinie est un problème classique dans le champs des problèmes inverses avec de nombreuses applications. Nous posons $x_{0}$ comme le signal inconnu à reconstruire que l'on modélise comme une somme de $K$ mesures de Dirac sur $mathbb{R}^{d}$. En se basant sur ce modèle, les seules informations nécessaires pour reconstruire $x_{0}$ sont ses amplitudes $a$ et positions $t$ associées. L'observation $y$ correspond à l'acquisition composée de $m$ mesures linéaires. Elle peut être modélisée dans le cas sans bruit par $y = A x_{0}$ avec $A$ un opérateur linéaire d'acquisition. L'une des manière de reconstruire $x_{0}$ à partir de $y$ et $A$ est de trouver le minimiseur d'un problème des moindres carrés non-convexe : $(mathcal{P}) quad x^{*} in argmin_{x in Sigma_{K, epsilon}} | y - Ax |_{2}^{2}$ avec $Sigma_{K, epsilon}$ l'ensemble des signaux de $K$ impulsions avec une contrainte de séparation entre les impulsions. Des garanties théoriques de reconstruction ont été données pour des opérateurs d'acquisition $A$ ayant une propriété d'isométrie restreinte (RIP). Ceci avec d'autres résultats théoriques expliquent en partie le succès d'une méthode gourmande : l'algorithme Continuous Orthogonal Matching Pursuit (COMP) avec descente. Cependant, cette méthode reste coûteuse à cause de ses multiples descentes sur tous les paramètres. Nous introduisons alors l'algorithme COMP sur-paramétré avec descente de gradient projetée (OP-COMP + PGD) pour palier à ce problème. Notre méthode OP-COMP + PGD est composée de deux parties distinctes. La première partie (OP-COMP) est une modification de COMP avec descente, nous supprimons les multiples descente sur tous les paramètres. En sur-paramétrisant le signal, nous compensons le manque de descente. En deuxième partie, PGD effectue une unique descente sur tous les paramètres. Elle réalise aussi une projection qui fusionne les impulsions trop proches les unes des autres. Cela impose au signal estimé de rester dans l'ensemble de solutions $Sigma_{K, epsilon}$. Nous accompagnons ce nouvel algorithme avec une étude théorique sur OP-COMP indiquant que, pour un opérateur linéaire $A$ suivant une RIP, les $K$ premières itérations de OP-COMP initialisent des impulsions proches de celles de $x_{0}$. Avec des travaux sur la taille des bassins d'attraction de $mathcal{P}$, nous assurons qu'avec une bonne initialisation du signal estimé, ce dernier se trouve dans le bassin d'attraction du minimum global et donc OP-COMP + PGD peut reconstruire $x_{0}$ exactement. En termes de résultats expérimentaux, nous comparons OP-COMP + PGD à COMP avec descente sur plusieurs configurations. En somme, la qualité de reconstruction par OP-COMP + PGD est identique à celle de COMP avec descente. Au-delà de $K geq 15$, OP-COMP devient moins coûteux avec un temps total de calcul d'ordre $mathcal{O}(K)$ contre $mathcal{O}(K^{2})$ pour COMP avec descente. En ajout de OP-COMP + PGD, nous développons deux autres techniques d'accélération. Premièrement, la descente par blocs de coordonnées profite de la parcimonie de notre modèle. Cette méthode cherche à réduire les coûts de calculs lors de la descente de gradient projetée. Elle remplace PGD en effectuant de descente que sur les impulsions qui n'ont pas encore convergé. En comparant cette méthode à PGD, nous observons une amélioration du temps de calcul total de $35%$ sans perte de précision. Deuxièmement, le sketching de l'opérateur linéaire consiste à compresser l'observation $y$ pour réduire le nombre total de mesures et donc accélérer les calculs. En compressant avec la transformée de Fourier, nous résolvons une version approximée de $mathcal{P}$. La qualité de la reconstruction obtenue dépend alors du nombre de mesures compressées. En comparant cette méthode avec OP-COMP + PGD, nous obtenons une précision comparable et une accélération du temps de calcul total de $80%$ avec un échantillonnage de $15%$.