Un algorithme itératif glouton pour l'approximation parcimonieuse qui construit une représentation k-parcimonieuse d'un signal en sélectionnant à chaque itération l'atome du dictionnaire le plus corrélé avec le résidu courant, en projetant orthogonalement le signal sur l'espace engendré par les atomes sélectionnés pour mettre à jour les coefficients, et en actualisant le résidu jusqu'à satisfaction d'un critère d'arrêt.

Principe

À chaque itération, choisir l'élément du dictionnaire dont le produit scalaire absolu avec le résidu est maximal (sélection gloutonne), puis recalculer les coefficients en résolvant un problème des moindres carrés sur les atomes sélectionnés (projection orthogonale) afin d'éviter une ré-weighting incohérent des atomes précédemment choisis et garantir une diminution monotone de la norme du résidu.

Démonstration

Approximer un signal y avec une base redondante (dictionnaire) : initialiser le résidu r=y, sélectionner l'atome de plus forte corrélation , l'ajouter à l'ensemble actif, résoudre le problème des moindres carrés pour calculer les coefficients sur cet ensemble, mettre à jour r=y - D_active c_active, et répéter jusqu'à atteindre la norme de résidu ou l'objectif de parcimonie, produisant un codage parcimonieux et interprétable.

Mauvaise application

Arrêter OMP trop tôt alors que des atomes essentiels restent non sélectionnés, produisant des approximations biaisées, ou appliquer OMP lorsque les colonnes du dictionnaire sont très cohérentes sans modifications (par ex. régularisation), ce qui peut conduire à une sélection d'atomes incorrecte et une mauvaise récupération.

Conséquence

Lorsque des conditions telles que le niveau de parcimonie et l'incohérence ou les conditions de type Restricted Isometry sont (approximativement) satisfaites, OMP récupère rapidement des représentations parcimonieuses avec des supports interprétables et un coût computationnel faible par rapport à la recherche exhaustive ; il offre un compromis clair entre parcimonie et erreur d'approximation.

Inversion

Ajustement dense en moindres carrés sur le dictionnaire complet : résoudre une minimisation L2 globale en utilisant tous les atomes, obtenant un résidu plus faible pour une norme donnée mais produisant des coefficients denses sans parcimonie imposée ni interprétabilité du support sélectionné.

Limite

Champ d'application : problèmes d'approximation linéaire parcimonieuse avec une matrice dictionnaire explicite et cohérence modérée où la sélection gloutonne est significative ; exclut les problèmes nécessitant une minimisation exacte du l0 dans des dictionnaires très cohérents, ou les signaux mieux modélisés par des sparsités structurées (groupées ou hiérarchiques) sans adaptation de l'algorithme.

Tension sémantique

Tension entre gloutonnerie et optimalité globale : les choix locaux et gloutons d'OMP sont rapides et interprétables mais peuvent manquer des supports parcimonieux globalement optimaux ; cela contraste avec les approches de relaxation convexe (minimisation L1) qui proposent d'autres compromis entre robustesse et coût computationnel.

Synthèse

La Poursuite D'Appariement Orthogonal est un algorithme glouton de codage parcimonieux qui sélectionne itérativement l'atome le plus corrélé avec le résidu et recalcule les coefficients par projection orthogonale pour construire une représentation parcimonieuse à support interprétable et à réduction monotone du résidu.