Algorithmes de type homotopiques pour la minimisation des moindres carrés régularisés par la "norme" $\ell_0$

Cette communication concerne la conception d'algorithmes d'approximation parcimonieuse pour les problemes inverses mal conditionnes. Les algorithmes heuristiques proposes sont concus pour minimiser des criteres mixtes 2-0 du type min_x J (x; λ) = || y − Ax ||^2 + λ || x ||_0. Ce sont des algorithmes gloutons " bidirectionnels " definis en tant qu'extensions d'Orthogonal Least Squares (OLS). Leur developpement est motive par le tres bon comportement empirique d'OLS et de ses versions derivees lorsque le dictionnaire A est une matrice mal conditionnee. Nous presentons dans un premier temps l'algorithme Single Best Replacement (SBR) pour minimiser J (x; λ) a λ fixe [1], en mettant en avant ses proprietes de convergence. Nous proposons ensuite deux algorithmes permettant de minimiser J pour un continuum de valeurs de λ, ce qui conduit a estimer le chemin de regularisation L0 [2]. Ces algorithmes sont inspires de l'algorithme d'homotopie pour la regularisation L1 [3, 4] et exploitent le caractere constant par morceaux du chemin de regularisation L0. Continuation Single Best Replacement (CSBR) est base sur des appels a SBR pour des valeurs decroissantes de λ, calculees de manieere adaptative. L'algorithme plus sophistique L0-regularization Path Descent (L0-PD) effectue une reconstruction (sous-optimale) du chemin de regularisation en maintenant (i) une liste de supports candidats pour des valeurs decroissantes de λ; et (ii) une liste de valeurs critiques de λ autour desquelles la solution change. Les simulations numeriques montrent l'efficacite des deux algorithmes pour des problemes inverses difficiles comme la deconvolution impulsionnelle par un filtre passe-bas. Nous montrons finalement que les algorithmes proposes peuvent etre avantageusement couples avec des methodes de selection d'ordre comme le MDL (Minimum Description Length) afin de selectionner automatiquement l'une des solutions parcimonieuses obtenues.