Synthése d'un article scientifique.

Introduction

Ce rapport est basé sur l'analyse d'un article scientifique nommé : K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation, publié par Michal Aharon, Michael Elad, et Alfred Bruckstein en Novembre 2006.
Michal Aharon est manager de recherche au sein du laboratoire Yahoo de Haifa. Il est chargé d'élaborer et d'améliorer des algorithmes qui contrôlent la sélection d'annonces personnalisées afin de maximiser les revenus de l'entreprise. Il a effectué son PHD à l'institut de technologie de Technion en Israël de 1998 à 2006 dans le domaine informatique.
Michael Elad est professeur au département d'informatique du Technion - Israël Institute of Technology. Ses domaines d’expertises sont : le traitement du signal, le traitement de l'image et la vision par ordinateur, l'analyse numérique, l’algèbre linéaire numérique et l’algorithmes d'apprentissage automatique.
Alfred Bruckstein est professeur au département d'informatique du Technion - Israël Institute of Technology. Ses domaines d’étude comprennent le traitement d'images, analyse d'images, la vision par ordinateur et infographie, la reconnaissance de formes, la géométrie appliquée et la théorie de l'estimation en traitement du signal et de l'image.
L'article a été publié dans la revue IEEE TRANSACTIONS ON SIGNAL PROCESSING. Selon son propre site officiel, elle est la revue leader dans les domaines informatique, ingénierie électrique, robotique, énergie et contrôle. Elle est dirigée par un groupe diversifié de membres bénévoles élus et nommés. La structure de gouvernance comprend des conseils pour les zones opérationnelles ainsi que des organes représentant les membres des 46 sociétés et conseils techniques et des dix régions géographiques du monde.
Dans ce rapport, je commencerai, tout d’abord, par détailler le contexte scientifique de l'article. Ensuite, j'exposerai les différentes solutions proposées aux problèmes scientifiques abordés dans la partie positionnement. Puis, j’énoncerai les contributions de l'auteur à cette problématique. Arrive après la partie expérience, où j'analyserai les expérimentations menées et les résultats obtenus par l'auteur en utilisant la méthode proposée. Enfin, dans une brève conclusion, j’émettrai un avis critique sur la méthode utilisée.

Contexte de l'article

Le traitement d'information et de données est, depuis plusieurs années, une problématique scientifique majeur touchant multiples domaines d'applications. De nombreux chercheurs se sont intéressés à l'analyse et à la représentation des signaux, comme Joseph Fourrier, un des plus célèbre, ou plus récemment, Yves Meyer, respectivement instigateur de la transformé de Fourrier et de la décomposition en ondelette. Ce type de représentation peut être perçu comme étant "classique", car bien que le signal subit une transformation, il reste défini sur une base unique. Malgré son utilité dans plusieurs cas, elle semble connaitre certaines limites. C’est pourquoi, depuis quelques années, la communauté scientifique pense à une autre manière de représenter un signal. La représentation parcimonieuse est l'une des alternatives connue. Elle consiste en la décomposition du signal sur un dictionnaire comprenant un nombre d’éléments (ou atomes) très supérieur à la dimension du signal. Cette décomposition va introduire dans la nouvelle représentation du signal un grand nombre de valeurs nulles.
y=Dx (1)
y : le signal à analyser de dimensions Nx1.

x : le signal parcimonieux obtenu de dimensions Kx1.

D : le dictionnaire (nouvelle base du signal x) de dimensions NxK, en notant que chaque colonne de la matrice D est appelé atome.
Généralement K>>N, ce qui implique que (1) a une infinité de solutions. Le but de la représentation parcimonieuse est de maximiser le nombre de valeurs nulles contenues dans le signal x, tout en respectant l'égalité (1), ou du moins une certaines erreur prédéfinie "e".

y-Dx<e (2)

Ce type de représentation est utilisé dans plusieurs domaines. Les principaux étant la compression de données, la reconstruction d'images (problèmes inverses) afin de palier aux problèmes de flou, ou de perte de données dans les images et l’analyse des caractéristiques des signaux.[1]

Positionnement

Comme énoncé précédemment, la représentation parcimonieuse des signaux fournit, dans la majorité des cas, une infinité de solutions. Le critère principal pour choisir la solution la plus optimale, réside dans l'obtention d’un signal x avec le plus de coefficients nuls possible. Seulement, ce problème d'optimisation est considéré comme NP-complet, donc trop difficile à résoudre.
Il existe, aujourd'hui, différentes méthodes pour calculer les coefficients de x de manière efficace, comme les algorithmes de poursuites. Ces derniers se basent sur une connaissance de D et de y. Les plus connus sont :
· matching pursuit[1].
· orthogonal matching pursuit[1].
· focal underdetermined system solver (FOCUSS)[1].
Ces algorithmes sont très efficaces dans le cas d’un grand nombre de coefficients nuls au sein de x. Ils sont appelés « algorithmes gloutons ». Ils calculent séquentiellement le coefficient du signal x.
Ce qui nous amène au sujet principal de l'article, la formation des dictionnaires.
Afin de calculer les coefficients du signal x, nous émettons l’hypothèse de la connaissance du dictionnaire D. Or D est inconnu et doit être choisi parmi une infinité de solutions de la façon la plus optimale possible.
Il y a alors différentes manières pour déterminer D. La première, la plus simple, est de piocher parmi les nombreux dictionnaires existants dans la littérature qui sont calculés par des fonctions préétablies (fonction cosinusoïdale, gaussienne....). Bien que simple, cette méthode n'est pas très flexible et ne s'adapte pas à la dynamique du signal étudié. La seconde, est de calculer le dictionnaire D en se basant sur des méthode d'apprentissage. Cette dernière est celle proposée par l’auteur. Elle se base, comme la majorité des solutions de ce type, sur le principe de la généralisation de l'algorithme du K-means. K-means peut être perçu comme un cas particulier de la représentation parcimonieuse, avec la spécificité d'avoir un seul atome non nul et un coefficient correspondant à cet atome dans x qui soit égal à un.
Les différente méthode de calcule des dictionnaires:

  1. Méthode du maximum de vraisemblance :
    Cette méthode introduit un bruit blanc dans l'expression de base de la représentation parcimonieuse (1) et traite le problème de recherche du dictionnaire D de manière probabiliste. Ceci, en approximant la fonction de répartition p(x) par une laplacienne après le développement de la solution qui tend à devenir un problème de maximum de vraisemblance. "Ainsi, la solution tendra à augmenter les valeurs des entrées des dictionnaires pour permettre aux coefficients de se rapprocher de zéro. Cette difficulté a été gérée en limitant l'anomalie de chaque élément de base, de sorte que la variance de sortie des coefficients soit maintenue à un niveau approprié."[1]
  2. Méthode MOD :
    Avant d'utiliser cette méthode, il faut d'abord calculer, à l'aide d'algorithmes de poursuites (OMP ou FOCCUS), les coefficients x (en utilisant un dictionnaire fixe), puis, trouver le bon D qui minimise la matrice erreur obtenu par :
    E=Y-DX (3)
    Ou Y : représente l'ensemble des exemples de signal en notre possession.
  3. Méthode du maximum à postériori MAP :
    Cette méthode ressemble fortement à la première méthode, mais une information supplémentaire y est ajoutée, un apriori sur le dictionnaire D. "Ce cas permet à différentes colonnes d'avoir des valeurs de normes différentes. En conséquence, les colonnes ayant de faibles valeurs de normes ont tendance à être sous-utilisées, car les coefficients dont elles ont besoin sont plus grands et donc plus pénalisés."[1]
    Les méthodes de construction de dictionnaires sont, selon les auteurs, jugées sur trois critères : flexibilité, simplicité et efficacité. Or aucune des méthodes, précédemment citées, ne remplient les trois critères à la fois.