Poursuite de base

La poursuite de base (de l'anglais basis pursuit), aussi appelée recouvrement par norme $\ell _{1}$ ou plus simplement recouvrement $\ell _{1}$, 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

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

où l'inconnue est un vecteur $x=(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}$ formé de $n$ nombres réels, $\|\cdot \|_{1}$ est la norme $\ell _{1}$,

$\|x\|_{1}:=\sum _{i=1}^{n}|x_{i}|,$

$A$ est une matrice réelle $m\times n$ et $b\in \mathbb {R} ^{m}$. Il s'agit donc de trouver le plus petit vecteur $x\in \mathbb {R} ^{n}$, au sens de la norme $\ell _{1}$, qui vérifie l'équation affine $Ax=b$. Ce problème est convexe (l'objectif est convexe et l'ensemble admissible est affine, donc convexe), mais non lisse (la norme $\ell _{1}$ n'est pas partout différentiable).

Le contexte dans lequel intervient le recouvrement $\ell _{1}$ est décrit dans l'article Acquisition comprimée.

Comme nous le verrons, l'intérêt du problème $(P_{1})$ est de sélectionner une solution du système linéaire $Ax=b$, supposé sous-déterminé, ayant le moins d'éléments non nuls possible (ou presque). La non-différentiabilité de la norme $\ell _{1}$ 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 $m$ colonnes de $A$, supposée surjective en l'occurrence, telle que la sous-matrice $B$ correspondante soit inversible et détermine la solution par $B^{-1}b$.

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 $(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 $b\in \mathbb {R} ^{m}$ est le signal à décomposer, les colonnes de la matrice $A$ de type $m\times n$ sont les éléments du dictionnaire de signaux et les composantes de $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

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

où $A^{j}$ est la colonne $j$ de $A$. Lorsque le dictionnaire de signaux $A^{j}$ est surabondant, $m<n$ et la décomposition de $x$ comme ci-dessus n'est pas unique. Lorsqu'on cherche une décomposition parcimonieuse, l'on cherche à avoir le moins de coefficients $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 $x_{j}$ revient à résoudre le problème

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

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

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

Analyse du problème

Notation

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

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

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

Existence et unicité de solution

Ensemble des solutions — L'ensemble des solutions de $(P_{1})$ est un polyèdre convexe, qui est non vide si, et seulement si, $b$ est dans l'image de $A$.

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

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

${\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}}$

Dualité lagrangienne

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

$(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 $A^{\mathsf {T}}y$ est entre les bornes $-1$ et $+1$. Il s'agit donc d'un problème d'optimisation linéaire.

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

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

$(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, $(D_{1}')$ est le dual lagrangien de $(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 $(P_{1})$ et $(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 $-\infty$).

Dualité forte — Les propriétés suivantes sont équivalentes :

1. $b\in {\mathcal {R}}(A)$,
2. $(P_{1})$ a une solution,
3. $(D_{1})$ a une solution.

Par ailleurs,

• il n'y a pas de saut de dualité : si les propriétés ci-dessus ont lieu, alors $\operatorname {val} (D_{1})=\operatorname {val} (P_{1})\in \mathbb {R}$, sinon $\operatorname {val} (D_{1})=\operatorname {val} (P_{1})=+\infty$,
• ${\bar {x}}$ est solution de $(P_{1})$ et ${\bar {y}}$ est solution de $(D_{1})$ si, et seulement si, $({\bar {x}},{\bar {y}})$ est un point-selle du lagrangien $(x,y)\in \mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \|x\|_{1}-y^{\mathsf {T}}(Ax-b)$.

Méthodes de résolution

Optimisation linéaire

L'approche proposée par Chen, Donoho et Saunders consiste à résoudre $(P_{1}')$ 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

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

Bibliographie

• (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 $\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 $\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