Algorithmes de type homotopiques pour la minimisation des moindres carrés régularisés par la pseudo-norme L0
Salle de Conférences
le 22 novembre 2016 à 11:00
Cette présentation concerne le développement d'algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés. Les algorithmes heuristiques proposés sont conçus pour minimiser des critères mixtes L2-L0 du type
Ce sont des algorithmes gloutons "bidirectionnels" définis en tant qu'extensions d'Orthogonal Least Squares (OLS). Leur développement est motivé par le très bon comportement empirique d'OLS et de ses versions dérivées lorsque la matrice A est mal conditionnée. Je présenterai dans un premier temps l'algorithme "Single Best Replacement" (SBR) pour minimiser J(x;lambda) à lambda fixé [1], en mettant en avant ses propriétés structurelles. Dans la deuxième partie de la présentation, je présenterai deux algorithmes permettant de minimiser J pour un continuum de valeurs de lambda, ce qui conduit à estimer le chemin de régularisation L0 [2]. Ces algorithmes sont inspirés de l'algorithme d'homotopie pour la régularisaton L1 et exploitent le caractère constant par morceaux du chemin de régularisation L0. Les simulations numériques montrent l'efficacité des deux algorithmes pour des problèmes inverses difficiles comme la déconvolution impulsionnelle par un filtre passe-bas. Je montrerai finalement que les algorithmes proposés peuvent être avantageusement couplés avec des méthodes de sélection d'ordre comme le MDL (Minimum Description Length) afin de sélectionner automatiquement l'une seule solutions parcimonieuses obtenues. [1] C. Soussen, J. Idier, D. Brie et J. Duan, From Bernoulli-Gaussian deconvolution to sparse signal restoration, IEEE Transactions on Signal Processing, vol. 59, no. 10, pp. 4572-4584, oct. 2011. [2] C. Soussen, J. Idier, J. Duan et D. Brie, Homotopy based algorithms for l0-regularized least-squares, IEEE Transactions on Signal Processing, vol. 63, no.13, 3301-3316, juil. 2015