Poursuite de base

Voici comment on peut être amené à résoudre un problème d'optimisation de la forme ${\displaystyle (P_{1})}$  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 ${\displaystyle b\in \mathbb {R} ^{m}}$  est le signal à décomposer, les colonnes de la matrice ${\displaystyle A}$  de type ${\displaystyle m\times n}$  sont les éléments du dictionnaire de signaux et les composantes de ${\displaystyle x\in \mathbb {R} ^{n}}$  sont les coefficients recherchés pour représenter le signal au moyen des signaux du dictionnaire. On peut donc écrire

${\displaystyle b=\sum _{j=1}^{n}x_{j}A^{j},}$ 

où ${\displaystyle A^{j}}$  est la colonne ${\displaystyle j}$  de ${\displaystyle A}$ . Lorsque le dictionnaire de signaux ${\displaystyle A^{j}}$  est surabondant, ${\displaystyle m<n}$  et la décomposition de ${\displaystyle x}$  comme ci-dessus n'est pas unique. Lorsqu'on cherche une décomposition parcimonieuse, l'on cherche à avoir le moins de coefficients ${\displaystyle x_{j}}$  non nuls. C'est ce qui permet d'avoir une représentation compacte du signal (compression de celui-ci).

Annuler le plus de coefficients ${\displaystyle x_{j}}$  revient à résoudre le problème

${\displaystyle (P_{0})\quad \left\{{\begin{array}{l}\min \;\|x\|_{0}\\Ax=b,\end{array}}\right.}$ 

où ${\displaystyle \|x\|_{0}:=|\{i\in [1\,{:}\,n]:x_{i}\neq 0\}|}$  est le nombre d'éléments non nuls de ${\displaystyle x}$  (ce n'est pas une norme, mais la limite de ${\displaystyle \|x\|_{p}}$  lorsque ${\displaystyle p\to 0}$ , 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 ${\displaystyle (P_{1})}$ , en norme ${\displaystyle \ell _{1}}$ , peut être vu comme une approximation traitable du problème ${\displaystyle (P_{0})}$ , pour les raisons suivantes.

• Le problème ${\displaystyle (P_{1})}$  consiste à trouver un point du sous-espace affine ${\displaystyle {\mathcal {A}}:=\{x\in \mathbb {R} ^{n}:Ax=b\}}$  le plus proche de zéro au sens de la norme ${\displaystyle \ell _{1}}$ . Comme la boule unité ${\displaystyle B_{1}}$  de cette dernière est polyédrique, elle a un nombre fini de sommets et le problème ${\displaystyle (P_{1})}$  a tendance à trouver une solution en un sommet de ${\displaystyle \operatorname {val} (P_{1})B_{1}}$  (on a noté ${\displaystyle \operatorname {val} (P_{1})}$  la valeur optimale du problème ${\displaystyle (P_{1})}$ ) ou sur une face contenant peu de sommets de cette boule. Or les sommets de ${\displaystyle \operatorname {val} (P_{1})B_{1}}$  sont des multiples des vecteurs de base de ${\displaystyle \mathbb {R} ^{n}}$ , qui ont toutes leurs composantes nulles sauf une ! La solution de ${\displaystyle (P_{1})}$  aura donc tendance à avoir beaucoup d'éléments nuls.
• Par ailleurs, le problème ${\displaystyle (P_{1})}$  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].

La norme ${\displaystyle \ell _{\infty }}$  d'un vecteur ${\displaystyle v\in \mathbb {R} ^{m}}$  est définie et désignée par

${\displaystyle \|v\|_{\infty }:=\max _{1\leqslant i\leqslant m}|v_{i}|,}$ 

La valeur optimale d'un problème d'optimisation ${\displaystyle (P)}$  se note ${\displaystyle \operatorname {val} (P)}$ .

La polyédricité de l'ensemble des solutions vient de ce que la norme ${\displaystyle \ell _{1}}$  est polyédrique et l'ensemble admissible ${\displaystyle {\mathcal {X}}:=\{x\in \mathbb {R} ^{n}:Ax=b\}}$  aussi (c'est un sous-espace affine). Pour l'existence de solution, on utilise le fait que l'ensemble admissible est non vide (lorsque ${\displaystyle b\in {\mathcal {R}}(A)}$ ) 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 ${\displaystyle (P_{1})}$  sont moins aisées à déterminer. On notera que celles présentées ci-dessous^[3] dépendent du point ${\displaystyle {\bar {x}}}$  considéré comme candidat-solution ; elles s'apparentent donc à des conditions d'optimalité d'un point ${\displaystyle {\bar {x}}\in \mathbb {R} ^{n}}$  donné : la première condition, celle caractérisant ${\displaystyle {\bar {x}}}$  comme solution, traduit d'ailleurs l'appartenance de zéro au sous-différentiel de ${\displaystyle \|\cdot \|_{1}+{\mathcal {I}}_{\mathcal {X}}}$  en ${\displaystyle {\bar {x}}}$  (${\displaystyle {\mathcal {I}}_{\mathcal {X}}}$  est l'indicatrice de l'ensemble admissible ${\displaystyle {\mathcal {X}}}$ ) et le vecteur ${\displaystyle {\bar {y}}}$  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 ${\displaystyle \operatorname {Sol} (P_{1})}$  l'ensemble des solutions du problème ${\displaystyle (P_{1})}$  et ${\displaystyle \operatorname {intr} (\operatorname {Sol} (P_{1}))}$  son intérieur relatif.

Existence et unicité de solution — Soient ${\displaystyle {\bar {x}}\in \mathbb {R} ^{n}}$  un point vérifiant ${\displaystyle A{\bar {x}}=b}$ , ${\displaystyle I:=\{i\in [1\,{:}\,n]:{\bar {x}}_{i}\neq 0\}}$ , ${\displaystyle I^{c}:=[1\,{:}\,n]\setminus I}$  et ${\displaystyle {\bar {s}}:=\operatorname {signe} ({\bar {x}}_{I})}$ . Alors

${\displaystyle {\begin{aligned}{\bar {x}}\in \operatorname {Sol} (P_{1})&\qquad \Longleftrightarrow \qquad {\mbox{il existe}}~{\bar {y}}\in \mathbb {R} ^{m}~{\mbox{tel que}}~A_{I}^{\mathsf {T}}{\bar {y}}={\bar {s}}~{\mbox{et}}~\|A_{I^{c}}^{\mathsf {T}}{\bar {y}}\|_{\infty }\leqslant 1,\\{\bar {x}}\in \operatorname {intr} (\operatorname {Sol} (P_{1}))&\qquad \Longleftrightarrow \qquad {\mbox{il existe}}~{\bar {y}}\in \mathbb {R} ^{m}~{\mbox{tel que}}~A_{I}^{\mathsf {T}}{\bar {y}}={\bar {s}}~{\mbox{et}}~\|A_{I^{c}}^{\mathsf {T}}{\bar {y}}\|_{\infty }<1,\\\operatorname {Sol} (P_{1})=\{{\bar {x}}\}&\qquad \Longleftrightarrow \qquad \left\{{\begin{array}{l}{\mbox{il existe}}~{\bar {y}}\in \mathbb {R} ^{m}~{\mbox{tel que}}~A_{I}^{\mathsf {T}}{\bar {y}}={\bar {s}}~{\mbox{et}}~\|A_{I^{c}}^{\mathsf {T}}{\bar {y}}\|_{\infty }<1\\A_{I}~{\mbox{est injective.}}\end{array}}\right.\end{aligned}}}$ 

Le problème dual lagrangien de ${\displaystyle (P_{1})}$  s'écrit comme le problème en ${\displaystyle y\in \mathbb {R} ^{m}}$  suivant

${\displaystyle (D_{1})\quad \left\{{\begin{array}{l}\sup \;b^{\mathsf {T}}y\\\|A^{\mathsf {T}}y\|_{\infty }\leqslant 1.\end{array}}\right.}$ 

La contrainte non différentiable de ce problème revient à imposer que chaque composante de ${\displaystyle A^{\mathsf {T}}y}$  est entre les bornes ${\displaystyle -1}$  et ${\displaystyle +1}$ . Il s'agit donc d'un problème d'optimisation linéaire.

On peut reformuler le problème ${\displaystyle (P_{1})}$  comme un problème d'optimisation linéaire en ${\displaystyle (u,v)\in \mathbb {R} ^{n}\times \mathbb {R} ^{n}}$  sous forme standard :

${\displaystyle (P_{1}')\quad \left\{{\begin{array}{l}\min \;e^{\mathsf {T}}u+e^{\mathsf {T}}v\\{\begin{pmatrix}A&-A\end{pmatrix}}{\begin{pmatrix}u\\v\end{pmatrix}}=b,\\u\geqslant 0,~~v\geqslant 0.\end{array}}\right.}$ 

où ${\displaystyle e\in \mathbb {R} ^{n}}$  est le vecteur dont toutes les composantes valent 1. Le lien entre les variables ${\displaystyle (u,v)}$  de ${\displaystyle (P_{1}')}$  et la variable ${\displaystyle x}$  de ${\displaystyle (P_{1})}$  est ${\displaystyle x=u-v}$ . Quant au problème dual ${\displaystyle (D_{1})}$ , on peut l'écrire comme le problème d'optimisation linéaire suivant

${\displaystyle (D_{1}')\quad \left\{{\begin{array}{l}\sup \;b^{\mathsf {T}}y\\-e\leqslant A^{\mathsf {T}}y\leqslant e.\end{array}}\right.}$ 

D'après la dualité lagrangienne en optimisation linéaire, ${\displaystyle (D_{1}')}$  est le dual lagrangien de ${\displaystyle (P_{1}')}$ .

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 ${\displaystyle (P_{1})}$  et ${\displaystyle (D_{1})}$  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 ${\displaystyle -\infty }$ ).

L'approche proposée par Chen, Donoho et Saunders^[1] consiste à résoudre ${\displaystyle (P_{1}')}$  par un algorithme de résolution de problème d'optimisation linéaire : algorithme du simplexe ou de points intérieurs.

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

• 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 ${\displaystyle \ell _{1}}$ 

• (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, n^o 1, 2001, p. 129-159 [lire en ligne]
• (en) J. Ch. Gilbert, « On the solution uniqueness characterization in the ${\displaystyle \ell _{1}}$  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 ${\displaystyle \ell _{1}}$ /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, n^o 1, 2015, p. 109-122

•   Portail des mathématiques