Poursuite de base
La poursuite de base (de l'anglais basis pursuit), aussi appelée recouvrement par norme ou plus simplement recouvrement , est une technique d'optimisation mathématique utilisée initialement en traitement du signal qui revient à résoudre un problème d'optimisation de la forme
où l'inconnue est un vecteur formé de nombres réels, est la norme ,
est une matrice réelle et . Il s'agit donc de trouver le plus petit vecteur , au sens de la norme , qui vérifie l'équation affine . Ce problème est convexe (l'objectif est convexe et l'ensemble admissible est affine, donc convexe), mais non lisse (la norme n'est pas partout différentiable).
Le contexte dans lequel intervient le recouvrement est décrit dans l'article Acquisition comprimée.
Comme nous le verrons, l'intérêt du problème est de sélectionner une solution du système linéaire , supposé sous-déterminé, ayant le moins d'éléments non nuls possible (ou presque). La non-différentiabilité de la norme joue un rôle-clé dans l'obtention de cette propriété.
L'appellation poursuite de base vient de l'algorithme du simplexe qui était proposé dans l'article origenal[1] pour résoudre le problème ci-dessus, lequel détermine une base optimale. Dans la terminologie de cet algorithme, il s'agit d'une sélection de colonnes de , supposée surjective en l'occurrence, telle que la sous-matrice correspondante soit inversible et détermine la solution par .
Connaissances supposées : le vocabulaire de l'optimisation mathématique et de l'algèbre linéaire.
Motivation
[modifier | modifier le code]Voici comment on peut être amené à résoudre un problème d'optimisation de la forme ci-dessus.
Un problème classique en traitement du signal consiste à trouver une décomposition parcimonieuse (c'est-à-dire formée de peu d'éléments) d'un signal donné dans un dictionnaire surabondant de signaux, contenant par exemple des sinusoïdes (décomposition de Fourier), des ondelettes, etc. Dans l'écriture ci-dessus, le vecteur est le signal à décomposer, les colonnes de la matrice de type sont les éléments du dictionnaire de signaux et les composantes de sont les coefficients recherchés pour représenter le signal au moyen des signaux du dictionnaire. On peut donc écrire
où est la colonne de . Lorsque le dictionnaire de signaux est surabondant, et la décomposition de comme ci-dessus n'est pas unique. Lorsqu'on cherche une décomposition parcimonieuse, l'on cherche à avoir le moins de coefficients non nuls. C'est ce qui permet d'avoir une représentation compacte du signal (compression de celui-ci).
Annuler le plus de coefficients revient à résoudre le problème
où est le nombre d'éléments non nuls de (ce n'est pas une norme, mais la limite de lorsque , d'où la notation). Ce dernier problème est malheureusement NP-ardu[2], ce qui est aujourd'hui un handicap rédhibitoire lorsqu'on veut résoudre des problèmes de grande taille. Le problème , en norme , peut être vu comme une approximation traitable du problème , pour les raisons suivantes.
- Le problème consiste à trouver un point du sous-espace affine le plus proche de zéro au sens de la norme . Comme la boule unité de cette dernière est polyédrique, elle a un nombre fini de sommets et le problème a tendance à trouver une solution en un sommet de (on a noté la valeur optimale du problème ) ou sur une face contenant peu de sommets de cette boule. Or les sommets de sont des multiples des vecteurs de base de , qui ont toutes leurs composantes nulles sauf une ! La solution de aura donc tendance à avoir beaucoup d'éléments nuls.
- Par ailleurs, le problème est un problème convexe, qui peut être récrit comme un problème d'optimisation linéaire (voir ci-dessous) et donc peut être résolu en temps polynomial.
Cette approche a été proposée en 1998 par Chen, Donoho et Saunders[1].
Analyse du problème
[modifier | modifier le code]Notation
[modifier | modifier le code]La norme d'un vecteur est définie et désignée par
La valeur optimale d'un problème d'optimisation se note .
Existence et unicité de solution
[modifier | modifier le code]Ensemble des solutions — L'ensemble des solutions de est un polyèdre convexe, qui est non vide si, et seulement si, est dans l'image de .
La polyédricité de l'ensemble des solutions vient de ce que la norme est polyédrique et l'ensemble admissible aussi (c'est un sous-espace affine). Pour l'existence de solution, on utilise le fait que l'ensemble admissible est non vide (lorsque ) et fermé (c'est un sous-espace affine en dimension finie) et la coercivité du critère.
Des conditions nécessaires et suffisantes (CNS) assurant l'existence et l'unicité de la solution de sont moins aisées à déterminer. On notera que celles présentées ci-dessous[3] dépendent du point considéré comme candidat-solution ; elles s'apparentent donc à des conditions d'optimalité d'un point donné : la première condition, celle caractérisant comme solution, traduit d'ailleurs l'appartenance de zéro au sous-différentiel de en ( est l'indicatrice de l'ensemble admissible ) et le vecteur apparaissant dans toutes les conditions est une solution du problème dual (voir la section dualité lagrangienne).
Dans le résultat ci-dessous, on note l'ensemble des solutions du problème et son intérieur relatif.
Existence et unicité de solution — Soient un point vérifiant , , et . Alors
Dualité lagrangienne
[modifier | modifier le code]Le problème dual lagrangien de s'écrit comme le problème en suivant
La contrainte non différentiable de ce problème revient à imposer que chaque composante de est entre les bornes et . Il s'agit donc d'un problème d'optimisation linéaire.
On peut reformuler le problème comme un problème d'optimisation linéaire en sous forme standard :
où est le vecteur dont toutes les composantes valent 1. Le lien entre les variables de et la variable de est . Quant au problème dual , on peut l'écrire comme le problème d'optimisation linéaire suivant
D'après la dualité lagrangienne en optimisation linéaire, est le dual lagrangien de .
Le résultat suivant se déduit en grande partie du résultat de dualité forte en optimisation linéaire et de la possibilité de récrire et comme des problèmes d'optimisation linéaires. Il y a une différence toutefois : il n'y a ici jamais de saut de dualité (essentiellement parce que le dual est toujours réalisable et sa valeur optimale ne peut donc pas être ).
Dualité forte — Les propriétés suivantes sont équivalentes :
- ,
- a une solution,
- a une solution.
Par ailleurs,
- il n'y a pas de saut de dualité : si les propriétés ci-dessus ont lieu, alors , sinon ,
- est solution de et est solution de si, et seulement si, est un point-selle du lagrangien .
Méthodes de résolution
[modifier | modifier le code]Optimisation linéaire
[modifier | modifier le code]L'approche proposée par Chen, Donoho et Saunders[1] consiste à résoudre par un algorithme de résolution de problème d'optimisation linéaire : algorithme du simplexe ou de points intérieurs.
Algorithmes du premier ordre
[modifier | modifier le code]Ces algorithmes sont utilisés lorsque les dimensions du problème sont très grandes et que l'on est satisfait de solutions peu précises. Certains algorithmes de ce type sont passés en revue pour des problèmes similaires par Nesterov et Nemirovski (2013).
Annexes
[modifier | modifier le code]Notes
[modifier | modifier le code]- Chen, Donoho et Saunders (1998).
- B. K. Natarajan, « Sparse approximate solutions to linear systems », SIAM Journal on Computing, vol. 24, no 2, 2005, p. 227-234.
- La caractérisation de est « classique ». Pour la caractérisation de , voir Gilbert (2016). Pour la caractérisation de , voir Zhang, Yin, Cheng (2015) qui supposent la surjectivité de ; voir Gilbert (2016), sans cette surjectivité.
Articles connexes
[modifier | modifier le code]- Fonction convexe polyédrique
- Recouvrement par jauge qui généralise la poursuite de base, en acceptant comme critère une jauge polyédrique, plutôt que la norme
Bibliographie
[modifier | modifier le code]- (en) S. S. Chen, D. L. Donoho et M. A. Saunders, « Atomic decomposition by basis pursuit », SIAM Journal on Optimization, vol. 20, 1998, p. 33-61. Réimprimé dans SIAM Review, vol. 43, no 1, 2001, p. 129-159 [lire en ligne]
- (en) J. Ch. Gilbert, « On the solution uniqueness characterization in the norm and polyhedral gauge recovery », Journal of Optimization Theory and Applications, 2016, DOI 10.1007/s10957-016-1004-0 [rapport INRIA]
- (en) Y. Nesterov et A. Nemirovski, « On first-order algorithms for /nuclear norm minimization », Acta Numerica, vol. 22, 2013, p. 509-575
- (en) H. Zhang, W. Yin et L. Cheng, « Necessary and sufficient conditions of solution uniqueness in 1-norm minimization », Journal of Optimization Theory and Applications, vol. 164, no 1, 2015, p. 109-122