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 original 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 

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 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, 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.

Analyse du problème

Notation 

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 

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 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.

Dualité lagrangienne 

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 ).

Méthodes de résolution

Optimisation linéaire 

L'approche proposée par Chen, Donoho et Saunders 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 

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

Notes

Articles connexes 
 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 
  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, , 2001, p. 129-159 
  J. Ch. Gilbert, « On the solution uniqueness characterization in the  norm and polyhedral gauge recovery », Journal of Optimization Theory and Applications, 2016,  
  Y. Nesterov et A. Nemirovski, « On first-order algorithms for /nuclear norm minimization », Acta Numerica, vol. 22, 2013, p. 509-575
  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, , 2015, 

Optimisation