Représentations parcimonieuses et apprentissage de dictionnaire

Représentations parcimonieuses et apprentissage de dictionnaire

Transformer un signal, de façon a le représenter dans un autre espace grace a quelques coe cients seulement, a de quoi seduire. Cette nouvelle representation du signal est alors dite parcimonieuse, car basee sur quelques coe cients non nuls seule ment. Quant a ce nouvel espace de représentation, il est de ni par une matrice nommée dictionnaire, dont les colonnes sont communément appelées atomes.

On de nit ainsi les representations parcimonieuses comme des representations de signaux, sous formes de vecteurs, par des combinaisons lineaires de quelques atomes seulement dun diction naire. Les methodes traitant et utilisant ce type de representation, cherchant a obtenir une solution la plus parcimonieuse possible, se sont considerablement developpees pour faire des representations parcimonieuses aujourdhui un sujet de recherche tres actif.

Elles sont ainsi utilisees dans de nombreux domaines tels que le debruitage, linpainting (consistant a remplir la partie manquante dune image), la super-resolution (permettant daugmenter la resolution dune image), la classi cation ou encore la compression. Dans ce premier chapitre, nous commencerons par presenter les representations parcimonieuses ainsi que quelques algorithmes de decomposition parcimonieuse per mettant de resoudre ce probleme.

Nous nous interesserons ensuite au cas de lappren tissage de dictionnaire, de facon a apprendre un nouvel espace de representation adapte aux donnees pour rendre les decompositions plus parcimonieuses et plus e caces. Enn, nous insisterons sur plusieurs applications pratiques des representations parcimonieuses et de lapprentissage de dictionnaire, dont certaines seront developpees dans le cadre de cette these.

Representations parcimonieuses

Les representations parcimonieuses consistent a representer un signal comme une combinaison lineaire de quelques colonnes, dites atomes, dun dictionnaire, souvent sur-complet. Des algorithmes de decomposition parcimonieuse dits gloutons ont ete developpes a n de resoudre ce probleme en utilisant di erentes normes pour forcer la  parcimonie. Recemment, des algorithmes utilisant la notion de parcimonie structuree ont egalement fait leur apparition.

Formulation du probleme Le probleme des representations parcimonieuses est de decomposer un signal y Rn sur un dictionnaire D Rn K avec une contrainte de parcimonie sur la representation, cest-a-dire une contrainte sur le nombre de colonnes de D choisies dans la decomposition (Fig. 1.1).

On recherche ainsi en theorie la solution du probleme suivant : min x x 0 sous la contrainte y = Dx (1.1) ou x RK est la representation parcimonieuse de y. x 0 represente la norme l0 de x et correspond au nombre de valeurs non nulles de x (ce nest en realite pas une norme). Le dictionnaire D est compose de K colonnes dk k = 1 K, appelees atomes, chacune delles supposee normalisee, cest-a-dire de norme l2 unitaire : dk 2 = 1 k = 1 K.

Le dictionnaire est en general sur-complet : il comporte davantage datomes que la dimension de chaque atome quil contient (K > n). Si K < n, on dira que le dictionnaire est sous-complet, et complet si K = n