On A Class of Greedy Sparse Recovery Algorithms

1. Problématique

Le problème central abordé est la reconstruction de signaux clairsemés (sparse signal recovery) à partir d'un système linéaire sous-déterminé de la forme $x = Qs$, où$Q \in \mathbb{R}^{N \times L}$ avec $N < L$ et $s \in \mathbb{R}^{L}$ est un vecteur clairsemé (ayant peu d'entrées non nulles).

L'objectif est de trouver la solution la plus clairsemée $s^\star$ (minimisant la norme $l_0$) satisfaisant le système. Ce problème est connu pour être NP-difficile. Les méthodes existantes se divisent principalement en deux catégories :

• Méthodes convexes (ex: Basis Pursuit - BP, IRLS) : Elles offrent une haute précision mais sont souvent coûteuses en calcul et sensibles aux instabilités numériques lorsque la matrice $Q$ est mal conditionnée.
• Méthodes gloutonnes (ex: OMP, CoSaMP) : Elles sont rapides mais souffrent généralement d'une précision de récupération inférieure à celle des méthodes convexes, car leur stratégie de sélection d'indices (basée sur la minimisation du résidu dans l'espace des mesures $x$) ne garantit pas toujours de trouver le bon support.

2. Méthodologie Proposée

Les auteurs proposent une approche novatrice qui transforme le problème de récupération. Au lieu de travailler directement dans l'espace des mesures $x$, ils caractérisent l'ensemble des solutions du système linéaire pour travailler directement dans l'espace du signal $s$.

Caractérisation de la solution

En utilisant la décomposition en valeurs singulières (SVD) de $Q = U \Sigma V^\top$, l'ensemble des solutions de $x = Qs$ est caractérisé par :
$$s = s_0(x) + Wz$$
où :

• $s_0(x) = V_1 \Sigma^{-1} U_1^\top x$ est une solution particulière (estimateur initial).
• $W$ est la matrice formée des vecteurs singuliers droits correspondant aux valeurs nulles de $\Sigma$ (noyau de $Q$).
• $z$ est un vecteur de paramètres libres.

Le problème de récupération clairsemée est ainsi reformulé comme une recherche de $z^\star$ minimisant la norme $l_0$ de $s_0 + Wz$. Cette reformulation transforme un problème contraint en un problème non contraint dans l'espace $s$.

Algorithmes Développés

Sur la base de cette caractérisation, les auteurs dérivent une classe d'algorithmes gloutons itératifs qui sélectionnent les indices du support en minimisant une mesure de clairsemé sur le résidu dans l'espace $s$ (et non $x$) :

1. AlgGL2 (Relaxation $l_2$) : Utilise la norme $l_2$ pour approximer la minimisation. C'est une variante de l'OMP qui opère sur le système transformé $s_0 = \bar{Q}s$. Elle maintient une complexité computationnelle similaire à l'OMP classique mais avec une meilleure précision.
2. AlgGL1 (Relaxation $l_1$) : Utilise la norme $l_1$ (programmation linéaire) pour sélectionner les indices. Il combine la force de l'optimisation globale du Basis Pursuit avec la stratégie gloutonne, offrant une précision supérieure aux algorithmes classiques.
3. AlgGLQ (Amélioration $l_q$) : Remplace la minimisation $l_1$ par une minimisation $l_q$ ($0 < q < 1$) via une approche de moindres carrés pondérés itératifs (IRLS) pour mieux approximer la parcimonie.
4. Versions Rapides (AlgF_GL1, AlgF_GLQ) : Intègrent une stratégie de type CoSaMP (sélection de plusieurs atomes par itération) pour accélérer la convergence, rendant ces algorithmes applicables à de grands systèmes.

Robustesse aux perturbations

L'approche est également étendue pour gérer les interférences de rang faible dans les mesures ($x = Qs + \Gamma\alpha$). En intégrant le modèle de perturbation directement dans la caractérisation de la solution, les algorithmes proposés peuvent séparer le signal clairsemé du bruit de rang faible, là où les méthodes classiques échouent souvent.

3. Contributions Clés

• Nouvelle Caractérisation : Introduction d'une formulation mathématique permettant de travailler directement dans l'espace du signal clairsemé ($s$-space) plutôt que dans l'espace des mesures.
• Série d'Algorithmes : Développement d'une famille d'algorithmes (AlgGL2, AlgGL1, AlgGLQ et leurs versions rapides) qui surpassent les méthodes de référence (OMP, CoSaMP, BP, IRLS).
• Robustesse Numérique : Démonstration que les algorithmes proposés sont beaucoup moins sensibles aux conditions numériques défavorables (matrice $Q$ mal conditionnée) que les méthodes IRLS classiques.
• Gestion du Bruit de Rang Faible : Capacité à récupérer le signal propre même en présence de perturbations structurées de rang faible, sans nécessiter de méthodes de décomposition complexes séparées.

4. Résultats Expérimentaux

Les simulations ont été menées sur des données synthétiques et des images (transmission d'images avec interférences).

• Précision de Récupération :
  • AlgGL2 surpasse significativement l'OMP classique et atteint des performances comparables au Basis Pursuit (BP).
  • AlgGL1 et AlgGLQ surpassent les algorithmes de l'état de l'art (y compris IRLSC et FISTA) en termes de taux de récupération réussie ($\varrho_{ok}$), atteignant souvent 100% de succès là où les autres échouent, surtout à des niveaux de clairsemé élevés.
• Efficacité Computationnelle :
  • Bien que les versions basées sur $l_1$ soient plus lentes que l'OMP, elles sont compétitives par rapport aux méthodes convexes lourdes.
  • Les versions rapides (AlgF_GLQ) offrent un excellent compromis, surpassant IRLSC en précision tout en étant plus rapides dans de nombreux scénarios.
• Robustesse au Conditionnement :
  • Lorsque le nombre de conditionnement de $Q$ ($C_Q$) augmente (jusqu'à $10^{10}$), les algorithmes classiques (notamment IRLSC) échouent ou deviennent extrêmement lents.
  • Les algorithmes proposés (AlgGL2, AlgGLQ, AlgF_GLQ) maintiennent une précision de récupération parfaite et un temps de calcul stable, même pour des systèmes très mal conditionnés.
• Reconstruction d'Images :
  • Dans le scénario de transmission d'images avec interférence de rang faible, les algorithmes proposés (notamment AlgGLQ) ont restauré les images avec des rapports signal-sur-bruit (PSNR) nettement supérieurs (autour de 50 dB) par rapport à l'OMP et l'IRLSC (autour de 22-25 dB).

5. Signification et Impact

Cet article représente une avancée significative dans le domaine de la récupération de signaux clairsemés et de l'échantillonnage compressé (Compressed Sensing).

1. Dépassement du compromis Précision/Vitesse : Les auteurs réussissent à briser le compromis traditionnel où les méthodes rapides (gloutonnes) sont moins précises que les méthodes lentes (convexes).
2. Stabilité Numérique : La méthode proposée offre une solution robuste aux problèmes d'instabilité numérique qui limitent l'application des méthodes IRLS dans des conditions réelles (systèmes mal conditionnés).
3. Versatilité : La capacité à traiter simultanément le signal clairsemé et les interférences de rang faible ouvre la voie à des applications plus complexes en imagerie hyperspectrale, en traitement sismique et en communications sans fil, où le bruit n'est pas toujours blanc ou gaussien.

En conclusion, cette approche basée sur la caractérisation de l'ensemble des solutions dans l'espace $s$ fournit un cadre théorique solide et des algorithmes pratiques qui surpassent les méthodes existantes en termes de précision, de robustesse et d'adaptabilité.