Approximation gloutonne

En traitement du signal et en théorie de l'approximation, l'approximation gloutonne est le résultat de l'usage d'une famille d'algorithmes gloutons permettant d'obtenir itérativement une approximation d'un signal, d'un vecteur ou d'une fonction.

Ces algorithmes sont utilisés notamment dans le domaine de l'acquisition comprimée^[1] où l'on cherche à reconstruire à partir d'un petit nombre d'observations un signal parcimonieux, c.-à-d. pouvant s'exprimer comme une combinaison linéaire d'un petit nombre d'éléments d'un dictionnaire.

Les algorithmes d'approximation gloutonne consistent à approcher un signal ${\displaystyle s\in H}$ par une combinaison d'éléments choisis itérativement au sein d'un dictionnaire ${\displaystyle D\subseteq H}$. Bien que ces algorithmes aient été étudiés dans le cadre général des espaces de Banach^[2], cet article se limite au cas où ${\displaystyle H}$ est un espace de Hilbert. Le dictionnaire ${\displaystyle D}$ peut être fini ou infini. Ses éléments sont le plus souvent normalisés, c.-à-d. ${\displaystyle \lVert d_{i}\rVert =1}$ pour tout ${\displaystyle d_{i}\in D}$ .

Bien que toute une variété d'algorithmes d'approximation gloutons existent, il partagent une structure commune. Il s'agit d'algorithme itératifs effectuant à chaque itération deux opérations : (1) la sélection d'un nouvel élément du dictionnaire et (2) la mise à jour de l'estimateur en utilisant l'élément du dictionnaire sélectionné.

L'algorithme « matching pursuit » (MP) a été proposé en 1993 par Mallat et Zhang^[3] pour de l'approximation en temps-fréquence.

 Entrée: Signal: ${\displaystyle s}$, dictionnaire ${\displaystyle D}$ (normalisé), nombre d'itérations ${\displaystyle I}$   
 Sortie: Estimateur ${\displaystyle x_{I}}$
  
 ${\displaystyle x_{0}=0}$ 
 Pour ${\displaystyle i=1,\dots ,I}$  
   Trouver ${\displaystyle d_{i}\in D}$ maximisant ${\displaystyle |\langle s-x_{i-1},d_{i}\rangle |}$
   ${\displaystyle x_{i}=x_{i-1}+\langle s-x_{i-1},d_{i}\rangle d_{i}}$
 FinPour
 Retourner ${\displaystyle x_{I}}$

Bien que l'algorithme soit ici écrit pour un nombre fixé ${\displaystyle I}$ d'itérations, il est possible d'utiliser un critère d'arrêt afin de déterminer le nombre d'itérations de manière adaptative.

L'étape de mise à jour de l'estimateur ${\displaystyle x_{i}=x_{i-1}+\langle s-x_{i-1},d_{i}\rangle d_{i}}$ correspond à la meilleure estimation possible dans la direction ${\displaystyle d_{i}}$, dans le sens où

${\displaystyle \langle s-x_{i-1},d_{i}\rangle =\arg \min _{\gamma \in \mathbb {R} }\|s-x_{i-1}-\gamma d_{i}\|_{2}^{2}.}$

L'algorithme « orthogonal matching pursuit » (OMP) suit la même logique de sélection des atomes que l'algorithme matching pursuit, mais diffère en ce que l'estimateur construit à l'itération ${\displaystyle i}$ est le meilleur estimateur du signal dans l'espace engendré par tous les éléments du dictionnaires choisis jusqu'à l'itération ${\displaystyle i}$, là où matching pursuit se contente de chercher le meilleur estimateur dans la direction du dernier élément ${\displaystyle d_{i}}$ choisi^[4],[5].

L'estimateur produit par OMP est donc plus fidèle, au prix du calcul d'une projection orthogonale à chaque itération.

 Entrée: Signal: ${\displaystyle s}$, dictionnaire ${\displaystyle D}$ (normalisé), nombre d'itérations ${\displaystyle I}$   
 Sortie: Estimateur ${\displaystyle x_{I}}$
  
 ${\displaystyle x_{0}=0}$ 
 Pour ${\displaystyle i=1,\dots ,I}$  
   Trouver ${\displaystyle d_{i}\in D}$ maximisant ${\displaystyle |\langle s-x_{i-1},d_{i}\rangle |}$
   ${\displaystyle x_{i}=x_{i-1}+\langle s-x_{i-1},d_{i}\rangle d_{i}}$
   ${\displaystyle x_{i}=\mathop {\rm {argmin}} \limits _{x\in \mathrm {span} (\{d_{1},\dots ,d_{i}\})}\|s-x\|}$
 FinPour
 Retourner ${\displaystyle x_{I}}$

L'algorithme « orthogonal least squares » (OLS) utilise une règle de sélection différente vis-à-vis d'OMP : à chaque itération, l'algorithme sélectionne l'élément du dictionnaire permettant d'obtenir la meilleure approximation après ajout de l'élément en question^[6].

Les algorithmes gloutons construisent par définition une approximation parcimonieuse, et ont été développés et utilisés dans le domaine de l'acquisition comprimée pour la reconstruction de solutions parcimonieuses de systèmes linéaires sous-déterminés.

De nombreuses variantes de ces algorithmes ont par ailleurs été proposées pour la résolution de problèmes d'optimisation convexe^[7].

• Portail de l'analyse