L'algorithme des moindre carré moyen (LMS: Least Mean Squares)[modifier | modifier le code]

Cette page est un brouillon appartenant à Kwendyida

Conseils de rédaction

→ N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
→ Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
Indiquez les éléments démontrant la notoriété du sujet (aide).
Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

→ Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

Introduction[modifier | modifier le code]

Les algorithmes des moindres carrés moyens (LMS) sont une classe de filtres adaptatifs utilisés pour imiter un filtre souhaité en trouvant les coefficients de ce dit filtre qui minimise le critère d'erreur (différence entre le signal souhaité et le signal réel) quadratique moyenne EQM $E\left\{|e(n)|^{2}\right\}$ .

Il s'agit d'une méthode de descente de gradient stochastique en ce que le filtre n'est adapté qu'en fonction de l'erreur à un instant donné.

Il a été inventé en 1960 par le professeur de l'Université de Stanford Bernard Widrow [1] et son premier doctorat. étudiant Marcian Hoff.

Définition des symboles[modifier | modifier le code]

$n$ constitue un indice temporel sur le traitement actuel,

$p$ la longueur du filtre,

$\{\cdot \}^{H}$ est une opération de transposition et de conjugaison de matrice,

$\mathbf {x} (n)=[x(n),x(n-1),\ldots ,x(n-p+1)]^{T}$ correspond au vecteur d'entrée de taille p,

$\mathbf {h} (n)=\left[h_{0}(n),h_{1}(n),\ldots ,h_{p-1}(n)\right]^{T}$ correspond au différents coefficients du filtres à estimer, $\mathbf {h} (n)\in \mathbb {C} ^{p}$ ,

$y(n)=\mathbf {h} ^{H}(n)\cdot \mathbf {x} (n)$ est la sortie du système que l'on tente d'extrapoler,

$d(n)=y(n)+\nu (n)$ la sortie bruitée du système que l'on tente d'extrapoler,

${\hat {y}}(n)={\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)$ est l'estimation de la sortie avec le filtre extrapolé,

${\hat {\mathbf {h} }}(n)$ le vecteur des coefficient du filtre estimé après n échantillons,

$e(n)=d(n)-{\hat {y}}(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)$ .

Formulation du problème[modifier | modifier le code]

La réalisation du filtre causal de Wiener ressemble beaucoup à l'estimation

des moindres carrés, sauf dans le domaine du traitement du signal.

La solution des moindres carrés, pour la matrice d'entrée $\mathbf {X}$ et le vecteur de sortie ${\boldsymbol {y}}$ est donnée par :

${\hat {\boldsymbol {\beta }}}=\left(\mathbf {X} ^{\mathrm {T} }\mathbf {X} \right)^{-1}\mathbf {X} ^{\mathrm {T} }{\boldsymbol {y}}$ .

Le filtre des moindres carrés moyens FIR est lié au filtre de Wiener, mais la minimisation du critère d'erreur du premier ne repose pas sur des corrélations croisées ou des auto-corrélations. Sa solution converge vers la solution de filtre de Wiener. La plupart des problèmes de filtrage adaptatif linéaire peuvent être formulés à l'aide du diagramme ci-dessus. Autrement dit, un système inconnu $\mathbf {h} (n)$ doit être identifié et le filtre adaptatif tente d'adapter le filtre ${\hat {\mathbf {h} }}(n)$ pour le rapprocher le plus possible de $\mathbf {h} (n)$ , tout en utilisant les seuls signaux observables $x(n),d(n)$ et $e(n)$ ; mais $y(n)$ , $h(n)$ et $v(n)$ ne sont pas directement observables. Sa solution est étroitement liée au filtre de Wiener.

Principe de base

L'idée de base du filtre LMS est d'approcher les poids de filtre optimaux $R^{-1}P$ , en mettant à jour les poids de filtre de manière à converger vers le filtre optimal.

Ceci est basé sur l'algorithme de descente de gradient. L'algorithme commence par supposer de petits poids (zéro dans la plupart des cas) et, à chaque étape, en trouvant le gradient de l'erreur quadratique moyenne, les poids sont mis à jour. Autrement dit, si le gradient EQM est positif, cela implique que l'erreur continuerait d'augmenter positivement si le même poids est utilisé pour d'autres itérations, ce qui signifie que nous devons réduire les poids. De la même manière, si le gradient est négatif, nous devons augmenter les poids. L'équation de mise à jour du poids est:

$W_{n+1}=W_{n}-\mu \nabla \varepsilon [n]$

où $\varepsilon$ représente l'erreur quadratique moyenne et $\mu$ est un coefficient de convergence.Le signe négatif montre que nous descendons la pente de l'erreur, $\varepsilon$ pour trouver les poids de filtre, $W_{i}$ , qui minimise l'erreur.

L'erreur quadratique moyenne en fonction des poids de filtre est une fonction quadratique, ce qui signifie qu'elle n'a qu'un extremum, celui qui minimise l'erreur quadratique moyenne, qui est le poids optimal. Le LMS se rapproche donc de ces poids optimaux en montant / descendant la courbe moyenne d'erreur quadratique en fonction du poids du filtre.

L'idée derrière les filtres LMS est d'utiliser la descente la plus raide pour trouver les poids des filtres ${\hat {\mathbf {h} }}(n)$ qui minimisent une fonction de coût. Nous commençons par définir la fonction de coût comme $C(n)=E\left\{|e(n)|^{2}\right\}$

Cette fonction de coût $C(n)$ est l'erreur quadratique moyenne, et elle est minimisée par le LMS. C'est là que le LMS tire son nom. Appliquer la descente la plus abrupte signifie prendre les dérivées partielles par rapport aux entrées individuelles du vecteur de coefficient de filtre (poids)

$\nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e(n)e^{*}(n)\right\}=2E\left\{\nabla _{\mathbf {h} ^{H}}(e(n))e^{*}(n)\right\}$

${\begin{array}{l}\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)\\\nabla C(n)=-2E\left\{\mathbf {x} (n)e^{*}(n)\right\}\end{array}}$

A présent $\nabla C(n)$ est un vecteur qui pointe vers la montée la plus abrupte de la fonction de coût. Pour trouver le minimum de la fonction de coût, nous devons faire un pas dans la direction opposée de $\nabla C(n)$ . Pour exprimer cela en termes mathématiques

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu E\left\{\mathbf {x} (n)e^{*}(n)\right\}$

où ${\frac {\ mu}{2}}$ est le pas d'adaptation. Cela signifie que nous avons trouvé un algorithme de mise à jour séquentielle qui minimise la fonction de coût. Malheureusement, cet algorithme n'est pas réalisable tant que nous ne connaissons pas $E\left[\mathbf {x} (n)e^{*}(n)\right]$ .

Généralement, la moyenne ci-dessus n'est pas calculée. Au lieu de cela, pour exécuter le LMS dans un environnement "online" (mise à jour après la réception de chaque nouvel échantillon), nous utilisons une estimation instantanée de cette moyenne. Voir ci-dessous.

Simplifications[modifier | modifier le code]

Pour la plupart des systèmes, la moyenne ${E}\left[\mathbf {x} (n)e^{*}(n)\right]$ doit être approximé. Cela peut être fait avec l'estimateur non biaisé suivant:

${\hat {E}}\left\{\mathbf {x} (n)e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x} (n-i)e^{*}(n-i)$

où $N$ indique le nombre d'échantillons que nous utilisons pour cette estimation. Le cas le plus simple est $N=1$

${\hat {E}}\left\{\mathbf {x} (n)e^{*}(n)\right\}=\mathbf {x} (n)e^{*}(n)$

Pour ce cas simple, l'algorithme de mise à jour s'écrit comme suit:

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)e^{*}(n)$

Cela constitue l'algorithme de mise à jour du filtre LMS.