Approximation parcimonieuse en traitement de signal

Un grand nombre de phénomènes physiques sont difficiles à observer et nécessitent la résolution d’un problème inverse pour retrouver les informations d’intérêt. Autrement dit, on observe des données ayant subi un processus de mesure, qui en général fournit des informations indirectes sur le phénomène observé. Il s’agit alors, étant donné un modèle sur le processus d’observation, d’inverser ce dernier pour remonter au phénomène ayant généré les données. De tels problèmes sont souvent mal posés [Idier, 2008] et les données ne contiennent pas suffisamment d’information permettant d’estimer de manière satisfaisante les quantités d’intérêt. Pour y remédier, on peut notamment les régulariser par la mise en valeur de toute information traduisant une connaissance a priori sur l’information recherchée. Une démarche largement utilisée en traitement du signal depuis une vingtaine d’années consiste à imposer la parcimonie (sparsity en anglais) de la solution [Elad, 2010], ce qui signifie au sens le plus strict du terme que seuls quelques coefficients dans l’ensemble des valeurs recherchées sont non nuls. La fonction de comptage, appelée aussi « norme » `0, est la mesure intuitive pour quantifier cette parcimonie.

La parcimonie est naturellement présente dans plusieurs applications en traitement du signal (par exemple pour la déconvolution impulsionnelle [Zala, 1992] et le démélange spectral [Singer and McCord, 1979]) ainsi qu’en économie (par exemple pour la sélection de portefeuilles [Li et al., 2006; Shaw et al., 2008; Bertsimas and Shioda, 2009]). Elle constitue un a priori donnant lieu à ce que l’on appelle l’approximation parcimonieuse, souvent étudié sous le nom de sélection de sous ensembles [Tibshirani, 1996; Osborne et al., 2000; Miller, 2002] en statistique. La résolution de ce dernier peut être décrite par la minimisation de l’erreur d’approximation entre les données et un modèle ainsi que de la norme `0 de la solution, qui formule intrinsèquement des questions d’optimisation combinatoire de complexité élevée [Natarajan, 1995]. Elle est généralement approchée par des méthodes rapides, reposant soit sur la relaxation continue de la norme `0 (notamment la relaxation convexe par la norme `1), soit sur des stratégies heuristiques gloutonnes [voir par exemple Tropp and Wright, 2010]. Cependant, aucune d’elles ne garantit l’optimalité vis-à-vis du problème en norme `0 dans le cadre des problèmes inverses mal posés.

Exemples d’applications en traitement de signal

Il existe plusieurs exemples d’applications de l’approximation parcimonieuse en traitement du signal. Nous présentons ici deux problèmes “historiques”. La première application est la déconvolution de trains d’impulsions [Zala, 1992] rencontrée en géophysique [Taylor et al., 1979; Mendel, 1986], en contrôle non destructif (CND) par ultrasons [Zala, 1992; O’Brien et al., 1994] et en astronomie [Starck et al., 2002]. La deuxième application est le démélange spectral parcimonieux [Singer and McCord, 1979; Iordache et al., 2011; Drumetz et al., 2019] rencontré dans plusieurs domaines comme l’imagerie hyperspectrale et la spectroscopie.

Déconvolution de trains d’impulsions parcimonieuse

La déconvolution de trains d’impulsions est un problème inverse parcimonieux classique en traitement du signal. Le contrôle non destructif par ultrasons (CND) [Zala, 1992; O’Brien et al., 1994] est un exemple d’application utilisant la déconvolution parcimonieuse, où l’on cherche, après émission d’une onde ultrasonore par un instrument de mesure à la surface d’une pièce, à obtenir des informations sur le milieu de propagation en se basant sur l’onde réfléchie (en temps continu) y(t), dans le but de détecter et de localiser des défauts. Ce signal peut alors se modéliser comme le produit de convolution entre une onde (la réponse impulsionnelle h(t)) et la séquence de réflectivité du milieu (un train d’impulsions x(t)), auquel s’ajoute un terme de bruit ε(t) .

La nature parcimonieuse de x(t) traduit alors le fait que les défauts sont peu nombreux dans un matériau globalement homogène. Le modèle convolutif s’écrit donc de la façon suivante :

y(t) = (h ∗ x)(t) + ε(t). (1.2)

Clairement, les colonnes voisines sont très corrélées entre elles. Au niveau fréquentiel, le système convolutif se comporte comme un filtre qui rend les données insensibles à une partie des fréquences contenues dans la séquence x (notamment les hautes fréquences), ce qui se traduit numériquement par le mauvais conditionnement de H. Ainsi, les solutions basées sur le seul ajustement du modèle (1.3) donnent un résultat dominé par le bruit, montrant le caractère mal posé du problème [Idier, 2008]. Cependant, comme nous l’avons mentionné plus haut, les défauts recherchés dans la pièce inspectée ne sont pas nombreux, et il semble naturel de régulariser le problème en recherchant des solutions parcimonieuses.

Démélange spectral parcimonieux

Une image hyperspectrale est une série d’images d’une scène prises dans un grand nombre de longueurs d’onde. Chacun des pixels constituant cette image est représenté par un vecteur de mesures des réflectances, qui désignent la proportion de lumière réfléchie, correspondant au spectre observé. Un problème inverse classique en imagerie hyperspectrale est le démélange spectral [Singer and McCord, 1979], où l’on cherche à décomposer chaque spectre observé y ∈ Rm acquis dans m bandes spectrales en un mélange linéaire de  spectres élémentaires (composants purs ou endmembers) et à estimer les proportions (abondances) de chacun de ces composants. Dans une approche supervisée, on ne s’intéresse qu’à l’estimation des abondances, les spectres purs étant supposés connus, soit par des mesures spectroscopiques en laboratoire des différents minéraux susceptibles d’être présents, soit via leur estimation à partir des mêmes données hyperspectrales, par exemple par des approches géométriques ou statistiques [Bioucas-Dias et al., 2012].

Puisque les abondances représentent des pourcentages, des contraintes de positivité et de somme à un sont ajoutées aux inconnues. Le conditionnement de la matrice S est également très mauvais dans ce cas, car S contient un nombre élevé de spectres qui sont très corrélés (voir Figure 1.3). Même si les contraintes de positivité créent une certaine parcimonie dans la solution, elles peuvent s’avérer insuffisantes pour ce problème et il peut sembler naturel de rechercher des solutions plus parcimonieuses [Iordache et al., 2011].

Méthodes heuristiques gloutonnes

Les méthodes gloutonnes construisent une approximation parcimonieuse en sélectionnant des variables d’une manière itérative partant d’un ensemble vide. Ces algorithmes suivent une stratégie de sélection de variables dite « progressive » (forward selection), répétant deux opérations itérativement jusqu’à atteindre un critère d’arrêt selon la formulation :

— si le degré de parcimonie K est atteint pour P2/0,
— si l’erreur résiduelle est inférieure au seuil donné ε pour P0/2,
— si on ne peut plus améliorer la solution pour P2+0.

Ces algorithmes peuvent donc être utilisés indifféremment pour aborder les trois problèmes. La première opération consiste à sélectionner une variable et la deuxième consiste à mettre à jour le modèle, sachant que, si une variable est sélectionnée, elle ne peut pas être enlevée. Ces algorithmes se prêtent directement aux trois problèmes, en particulier P2/0 et P0/2 qui sont plus faciles à réglé en pratique que P2+0. À l’inverse, il existe d’autres algorithmes plus performants, mettant en œuvre des stratégies plus sophistiquées avec possibilité de retrait, qui donnent de meilleures solutions avec un coût de calcul plus élevé, tel que Single Best Replacement (SBR) [Soussen et al., 2011], conçu pour le problème pénalisé P2+0.

Nous détaillons par la suite le principe de fonctionnement et la différence entre les trois algorithmes de type forward selection les plus connus : Matching Pursuit (MP) [Mallat and Zhang, 1993], Orthogonal Matching Pursuit (OMP) [Pati et al., 1993] et Orthogonal Least Squares (OLS) [Chen et al., 1989].

Table des matières

Introduction générale
Contexte et problématique
Contributions
Organisation du document
1 Approximation parcimonieuse en traitement de signal
1.1 Introduction
1.2 Problèmes inverses parcimonieux
1.2.1 Exemples d’applications en traitement de signal
1.2.2 Parcimonie et formulations du problème
1.3 Stratégies d’optimisation inexactes
1.3.1 Relaxation convexe de la norme `0
1.3.2 Méthodes heuristiques gloutonnes
1.4 Optimisation globale
1.4.1 Reformulation en MIP
1.4.2 Discussion sur l’hypothèse de borne (BigM)
1.4.3 Méthode de branch-and-bound pour la programmation en nombres mixtes
2 Branch-and-Bound et Relaxation continue
2.1 Introduction
2.2 Méthode de branch-and-bound
2.2.1 Procédure de séparation
2.2.2 Procédure d’évaluation
2.2.3 Algorithme branch-and-bound
2.2.4 Condition d’arrêt
2.3 Borne inférieure : Relaxation continue
2.3.1 Relaxation continue au niveau du nœud racine
2.3.2 Relaxation continue au niveau d’un nœud quelconque
2.4 Conclusion
3 Calcul de la borne inférieure
3.1 Introduction
3.2 Conditions d’optimalité du problème pénalisé Qˆ 2+1
3.3 Méthode homotopique pour la résolution des trois problèmes relâchés Qˆ 2/1, Qˆ 1/2 et Qˆ 2+1
3.3.1 Initialisation
3.3.2 Mise à jour récursive de la solution
3.3.3 Calcul de longueur de pas
3.3.4 Solution pour le problème pénalisé Qˆ 2+1
3.3.5 Solutions pour les problèmes contraints Qˆ 2/1 et Qˆ 1/2
3.3.6 Mise en œuvre et aspects pratiques
3.4 Algorithme d’ensemble actif pour le problème relâché Qˆ 2+1 avec redémarrage à chaud
3.4.1 Principe de fonctionnement
3.4.2 Redémarrage à chaud
3.4.3 Synthèse de l’algorithme
3.5 Résultats expérimentaux
3.5.1 Problèmes de déconvolution parcimonieuse
3.5.2 Problèmes de sélection de variables
3.6 Conclusion et perspectives
Conclusion générale

Télécharger le rapport complet