Poursuite de base

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 la 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 original[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 ondelettesetc. 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

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

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]

La condition d'existence de solution est sans surprise.

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 .

C'est évident. 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 :

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 :

  1. ,
  2. a une solution,
  3. 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]

  1. a, b et c Chen, Donoho et Saunders (1998).
  2. B. K. Natarajan, « Sparse approximate solutions to linear systems », SIAM Journal on Computing, vol. 24, no 2, 2005, p. 227-234.
  3. 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]

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