Problèmes de reconstruction de phase

Piste rouge Le 10 janvier 2017  - Ecrit par  Irène Waldspurger Voir les commentaires (1)

Les problèmes de reconstruction de phase sont une famille de problèmes mathématiques, étudiée depuis longtemps - environ un demi-siècle - à cause de ses importantes applications en physique. Leur compréhension théorique a beaucoup progressé ces dernières années ; nous donnerons un aperçu de certains résultats obtenus et des questions qui se posent encore.

Présentation du problème

Avant d’introduire les problèmes de reconstruction de phase, expliquons brièvement ce que sont les problèmes inverses. De manière informelle, un problème inverse consiste à déterminer un « objet » inconnu à partir d’un certain nombre de « renseignements » sur cet objet. Par exemple, reconstruire la forme tridimensionnelle d’un bâtiment (« l’objet ») à partir de photos bidimensionnelles de ce bâtiment (les « renseignements ») est un problème inverse.

JPEG - 30.1 ko
Première photo
JPEG - 18.9 ko
Deuxième photo
JPEG - 20.1 ko
Troisième photo
JPEG - 24 ko
Vue 3D du château de Trim, en Irlande
Figure 1 : Un exemple de problème inverse : reconstruire une forme tridimensionnelle à partir d’images bidimensionnelles.

Un problème de reconstruction de phase est un problème inverse dans lequel l’objet et les renseignements ont une forme particulière.

L’objet inconnu, tout d’abord, est une liste de nombres, $(x_1,x_2,\dots,x_n)$. À première vue, on pourrait se demander quel est l’intérêt d’un tel objet ; on répondra à cette question par un exemple concret dans la section suivante.

Décrivons maintenant la forme des renseignements. Nous allons commencer par nous intéresser à une version simplifiée du problème. Dans cette version simplifiée, on suppose que, pour retrouver $(x_1,x_2,\dots,x_n)$, on a accès à des informations de la forme
\[a_1x_1+a_2x_2+ \dots + a_nx_n,\]
où les $a_1,a_2,\dots,a_n$ sont des nombres connus. De telles informations sont appelées des mesures linéaires.

En général, retrouver une liste de nombres à partir de mesures linéaires n’est pas très difficile, s’il y a assez de mesures, comme l’illustre l’exemple suivant. [1]

Exemple 1 : Supposons qu’on veuille déterminer une liste de deux nombres, $(x_1,x_2)$, à partir des deux mesures linéaires suivantes, qu’on note $y_1$ et $y_2$ :
$\quad\qquad$ Première mesure linéaire : $ \quad y_1=x_1 + 2x_2$  ;
Deuxième mesure linéaire : $\quad y_2=x_1.$

À partir de $y_1$ et $y_2$, on peut déterminer $(x_1,x_2)$ par les formules suivantes :
\[x_1 = y_2\quad\mbox{ et }\quad x_2 = \frac{y_1-y_2}{2}.\]

Dans la version non-simplifiée, on n’a pas réellement accès à des mesures linéaires mais seulement à des valeurs absolues [2] de mesures linéaires, c’est-à-dire que les informations sont de la forme
\[ |a_1x_1+a_2x_2+\dots +a_nx_n|. \]
Le problème devient alors beaucoup plus difficile.

Un premier (petit) problème est qu’il n’est jamais possible de différencier les listes $(x_1,x_2,\dots,x_n)$ et $(-x_1,-x_2,\dots,-x_n)$ si on a uniquement des renseignements de la forme qu’on vient de décrire. En effet, quels que soient $a_1,\dots,a_n$, on a :
\[\begin{align*} |a_1(-x_1)&+a_2(-x_2)+\dots+a_n(-x_n)|\\ &=|-(a_1x_1+a_2x_2+\dots+a_nx_n)|\\ &=|a_1x_1+a_2x_2+\dots+a_nx_n|. \end{align*}\]
Il faut donc se résoudre à l’idée qu’il est impossible de reconstruire exactement $(x_1,x_2,\dots,x_n)$. Au mieux, on arrive à reconstruire notre liste à multiplication par $-1$ près ; on parle alors de reconstruction « à une phase globale près ».

Avertissement : le cas réel et le cas complexe.

Les nombres de la liste $(x_1,x_2,\dots,x_n)$ peuvent être de deux types : il peut s’agir de nombres « réels » (c’est-à-dire de nombres « habituels », tels que $1$, $-3/4$, $\pi$, $\sqrt{2}$ ...) ou de nombres « complexes ». La version réelle est plus simple mais la version complexe donne lieu à une théorie plus riche et a davantage d’applications. Afin que ce texte soit le plus accessible possible, nous allons surtout décrire la première version. Pour les personnes familières avec la notion de nombres complexes, des boîtes déroulantes indiqueront aux endroits idoines les différences entre les deux versions. À l’intention des personnes qui ne connaissent pas déjà la notion mais souhaitent tout de même comprendre le contenu des boîtes déroulantes, une brève présentation des nombres complexes se trouve à la fin de l’article.

La définition que nous venons de donner des problèmes de reconstruction de phase est celle du cas réel. Dans le cas complexe, la principale différence est que la valeur absolue est remplacée par un module complexe. Les informations auxquelles on a accès pour reconstruire la liste $(x_1,\dots,x_n)$ sont donc des modules de mesures linéaires :
\[|a_1x_1+a_2x_2+\dots+a_nx_n|.\]
Dans ce cas, pour tout nombre complexe $u$ de module $1$, il est impossible de distinguer $(x_1,x_2,\dots,x_n)$ de $(ux_1,ux_2,\dots,ux_n)$. En effet, quels que soient $a_1,a_2,\dots,a_n$,
\[\begin{align*} |a_1(ux_1)+a_2(ux_2)+\dots+a_n(ux_n)| &=|u\times (a_1x_1+a_2x_2+\dots+a_nx_n)|\\ &=|u|\times |a_1x_1+a_2x_2+\dots+a_nx_n|\\ &=|a_1x_1+a_2x_2+\dots+a_nx_n|. \end{align*}\]
On peut donc au mieux reconstruire la liste $(x_1,x_2,\dots,x_n)$ à multiplication par un nombre complexe de module $1$ près. C’est ce qu’on appelle « à phase globale près » dans le cas complexe.

Même lorsqu’on admet ces ambiguïtés dues à la multiplication par $-1$, les problèmes de reconstruction de phase restent difficiles. En particulier, si un ensemble de valeurs absolues de mesures linéaires nous est donné, il n’est pas facile de dire si cet ensemble est suffisant pour déterminer la liste $(x_1,x_2,\dots,x_n)$ de manière unique (à une phase globale près) ou pas. Cette difficulté est illustrée par l’exemple suivant.

Exemple 2 : Supposons de nouveau qu’on veut déterminer une liste à deux éléments $(x_1,x_2)$, à partir des deux valeurs absolues de mesures linéaires suivantes :
$\quad\qquad$ Première valeur absolue : $ \quad y_1=|x_1 + 2x_2|$  ;
Deuxième valeur absolue : $\quad y_2=|x_1|.$

Supposons qu’on sait que $y_1=1$ et $y_2=3$.
Ces deux informations, à elles seules, ne sont pas suffisantes pour déterminer $(x_1,x_2)$ de manière unique, même à multiplication par $-1$ près. Les listes $(3,-1)$ et $(3,-2)$, par exemple, sont toutes les deux des candidates acceptables :
\[\begin{align*} |3+2\times(-1)| = |1| = 1 = y_1\quad\mbox{et}\quad |3| = 3 = y_2;\\ |3+2\times(-2)| = |-1| = 1 = y_1\quad\mbox{et}\quad |3| = 3 = y_2. \end{align*}\]
Pourtant, ces deux listes ne sont pas égales à multiplication par $-1$ près : $(3,-1)\ne (-3,-(-2))$.

Si l’on souhaite déterminer $(x_1,x_2)$ de manière unique, à multiplication par $-1$ près, il faut davantage de mesures. Les trois mesures suivantes, par exemple, suffisent :
\[\begin{gather*} y_1 = |x_1+2x_2|=1,\quad\quad y_2=|x_1|=3,\\ y_3 = |x_1+x_2|=2. \end{gather*}\]
Pouvez-vous le démontrer ?

Dans ce cas précis, la démonstration peut être effectuée avec des outils élémentaires ; elle est toutefois déjà plus compliquée que le raisonnement mené dans l’exemple 1.

Exemple similaire dans le cas complexe

Exemple 2 bis : Dans le cas complexe, il faut généralement plus de trois mesures pour déterminer une liste de deux nombres de manière unique, à phase globale près. Les informations suivantes, par exemple, sont insuffisantes : \[\begin{gather*} y_1 = |x_1+2x_2|=1,\quad\quad y_2=|x_1|=3,\\ y_3 = |x_1+x_2|=\sqrt{\frac{5}{2}}. \end{gather*}\] En effet, les listes $\left(3,\frac{-3+i}{2}\right)$ et $\left(3,\frac{-3-i}{2}\right)$ sont toutes deux des candidates possibles, alors qu’elles ne sont pas égales à une phase globale près.

Une mesure de plus, en revanche, suffit :
\[\begin{align*} y_1 = |x_1+2x_2|=1,&\quad \quad y_2=|x_1|=3,\\ y_3 = |x_1+x_2|=\sqrt{\frac{5}{2}},&\quad\quad y_4 = |x_1-2ix_2| = 5 . \end{align*}\]
Pouvez-vous le démontrer ?

Remarque terminologique

Imaginons que pour chaque $(a_1,\dots,a_n)$, en plus d’avoir accès à la valeur absolue
\[|a_1x_1+a_2x_2+\dots+a_nx_n|,\]
on puisse déterminer le signe de $a_1x_1+a_2x_2+\dots+a_nx_n$. On peut alors déterminer chacune des mesures linéaires
\[a_1x_1+a_2x_2+\dots+a_nx_n\]
et on s’est ramené au problème qui consiste à reconstruire une liste inconnue à partir d’un ensemble de mesures linéaires, dont on a dit qu’il n’était pas très difficile.

On voit donc que, pour résoudre notre problème, il suffit de trouver un moyen de reconstruire le signe de chaque mesure linéaire. Dans ce contexte, le « signe » est appelé une « phase » (par analogie avec le cas complexe), ce qui explique le nom « reconstruction de phase ».

Une application : l’imagerie moléculaire

L’une des applications les plus importantes de la reconstruction de phase est de permettre l’observation de petites particules avec une très bonne résolution.

Imaginons qu’on souhaite observer un petit objet (une cellule, par exemple, ou un échantillon d’un cristal). Si la taille de cet objet est de l’ordre de quelques micromètres ou plus, on peut l’observer avec un microscope optique classique, dont le principe de fonctionnement est le suivant : un faisceau lumineux est envoyé à travers l’échantillon, puis dévié par des lentilles, de façon à ce que les rayons de lumière sortant du microscope forment une image agrandie de l’objet à observer. Si la taille est inférieure à un micromètre, ce processus ne fonctionne pas : des phénomènes dits de diffraction ont lieu et l’image agrandie est floue. Pour limiter l’ampleur de cette diffraction, il faut utiliser, à la place du faisceau lumineux, des rayons électromagnétiques de haute fréquence : des rayons X.

Malheureusement, il est difficile de fabriquer des lentilles de bonne qualité pour un système optique à base de rayons X. Un système d’agrandissement fonctionnant sans lentille est donc nécessaire. Nous allons en décrire un.

JPEG - 29.3 ko
(a) L’objet d’intérêt
JPEG - 65 ko
(b) Son approximation par des carrés noirs et blancs
JPEG - 68.3 ko
(c) Sa représentation comme une liste de nombres
Figure 2

Pour simplifier, on suppose qu’on ne s’intéresse qu’à la silhouette de l’objet à imager (représenté sur la figure 2, à gauche). On peut approximer cette silhouette par un assemblage de petits carrés noirs et blancs (figure 2, au milieu) ; l’approximation est d’autant plus précise que les carrés sont petits. Appelons $C_1,C_2,\dots,C_n$ ces carrés. Pour chaque indice $k$, définissons un nombre $x_k$ qui vaut $1$ si le carré $C_k$ est blanc et $0$ s’il est noir (figure 2, à droite). Pour déterminer la silhouette approximative de l’objet, il suffit de déterminer chacun des nombres $x_k$.

Imaginons maintenant qu’on place notre objet sur une plaque transparente, qu’on illumine par un faisceau d’ondes électromagnétiques, orienté perpendiculairement à la plaque. Ce dispositif est représenté sur la figure 3. Mathématiquement, on peut modéliser les ondes électromagnétiques par une certaine fonction $f$, qui varie au cours du temps (on notera $f(t)$ la valeur de la fonction à l’instant $t$).

JPEG - 28.1 ko
Figure 3 : Schéma du dispositif d’imagerie

Expression de $\boldsymbol{f}$ :

\[f(t)= e^{i(\omega t+\phi)}\in \mathbb{C}.\]
Le nombre $\omega$ est un paramètre physique, la fréquence des ondes, et $\phi$ est un autre paramètre qu’on appelle la phase.

En chaque point $p$ de la plaque transparente, lorsque les ondes arrivent, un phénomène de diffraction se produit. De manière très approximative, on peut décrire ce phénomène de la manière suivante.

  • Si le point $p$ appartient à l’intérieur de l’objet, l’onde est arrêtée.
  • Si le point $p$ est à l’extérieur de l’objet, il envoie dans toutes les directions une nouvelle onde électromagnétique. L’onde envoyée dans une direction est décrite par une nouvelle fonction :
    \[\begin{align}\label{eq:onde_diffractee} f_{p}(t)= a_{p}\times f(t), \end{align}\]
    où $a_{p}$ est un nombre qui dépend du point $p$, ainsi que de la direction.

Expression de $\boldsymbol{f_{p}}$ :

Si on représente la direction $v$ par un vecteur de $\mathbb{R}^3$, $v=(v_x,v_y,v_z)$, de norme $1$, l’équation de l’onde envoyée par le point dans cette direction est :
\[f_{p}(t)= e^{i\left(\omega t-\frac{\omega}{c}(Xv_x+Yv_y) +\phi\right)}\]
où $c$ est la vitesse des ondes électromagnétiques et $(X,Y)$ est la position du point $p$ par rapport au centre de la plaque. On a donc, pour tout $t$, $f_{p}(t)=a_{p}\times f(t)$, avec
\[a_{p}=e^{-i\frac{\omega}{c}(Xv_x+Yv_y)}.\]

Reprenons notre description de l’objet comme un assemblage de petits carrés $C_1,C_2,\dots,C_n$. Pour tout indice $k$, appelons $p_k$ le point central du carré $C_k$ et rappelons qu’on a défini $x_k$ de sorte que $x_k$ vaut $1$ si le carré est blanc, $0$ s’il est noir. On peut approximer le phénomène de diffraction que nous venons de décrire par le fait que chaque carré $C_k$ renvoie une onde décrite par la fonction
\[ x_k \times a_{p_k}\times f(t). \]
En effet, si le carré est noir, c’est-à-dire s’il est à l’intérieur de l’objet, $x_k$ vaut $0$ et l’expression que nous venons de donner est la fonction nulle, ce qui décrit une absence d’onde. En revanche, si le carré est blanc, $x_k$ vaut $1$ et on retrouve l’équation $\eqref{eq:onde_diffractee}$ (en considérant que chaque carré se comporte comme un point unique, $p_k$, ce qui est raisonnable si les carrés sont petits).

L’onde totale envoyée est la somme des ondes envoyées par chacun des carrés :
\[\begin{align*} x_1 a_{p_1} f(t) + &x_2 a_{p_2} f(t) + \dots + x_n a_{p_n} f(t)\\ &=(x_1 a_{p_1} + x_2 a_{p_2} + \dots + x_n a_{p_n}) \times f(t). \end{align*}\]

Expression complexe :

Si, pour tout $k$, $(X_k,Y_k)$ est la position du point $p_k$ par rapport au centre de la plaque, on aboutit, au vu des équations précédentes, à la formule :
\[ \begin{align*} \left(x_1 e^{-i\frac{\omega}{c}(X_1 v_x+Y_1 v_y)} + \dots + x_n e^{-i\frac{\omega}{c}(X_n v_x+Y_n v_y)}\right)e^{i(\omega t+\phi)}. \end{align*} \]

 [3]

Si on place un détecteur dans une certaine direction, on peut enregistrer l’onde renvoyée dans cette direction. En réalité, on ne peut facilement enregistrer que sa valeur absolue :
\[ |x_1 a_{p_1} + x_2 a_{p_2} + \dots + x_n a_{p_n}| \times |f(t)|. \]
Comme on connaît $f$, on peut diviser par $|f(t)|$ ; on arrive donc à mesurer
\[ |x_1 a_{p_1} + x_2 a_{p_2} + \dots + x_n a_{p_n}|, \]
ce qui est une valeur absolue de mesure linéaire pour la liste inconnue $(x_1,x_2,\dots,x_n)$. Remarquons que les $a_{p_k}$ dépendent de la direction $v$. En plaçant des détecteurs dans d’autres directions, on obtient d’autres valeurs absolues de mesures linéaires, avec des $a_{p_k}$ différents.

Comme on l’a vu, déterminer la forme de l’objet qui nous intéresse revient à déterminer les valeurs $x_1,x_2,\dots,x_n$. Or nous venons d’expliquer qu’en plaçant des détecteurs sur le trajet des ondes diffractées par l’objet, on obtenait des valeurs absolues de mesures linéaires sur la liste $(x_1,x_2,\dots,x_n)$. Déterminer la forme de l’objet est donc un problème de reconstruction de phase.

JPEG - 4.2 ko
(a) Molécule de caféine
JPEG - 8.8 ko
(b) Exemple de motif de diffraction
JPEG - 5.6 ko
(c) Image reconstruite

Figure 3 : exemple synthétique de reconstruction. L’image de gauche représente la molécule à imager. Celle du centre est un premier jeu de valeurs absolues ; chaque pixel représente la valeur absolue associée à une direction. On peut obtenir d’autres jeux en répétant le processus de diffraction, avec des « masques » placés devant la molécule. L’image de droite est la reconstruction à partir de deux jeux.

Axes de recherche

Présentons maintenant deux grands axes de recherche relatifs aux problèmes de reconstruction de phase.

Unicité de la reconstruction

Comme on l’a vu dans la première partie, si le nombre de valeurs absolues de mesures linéaires auquel on a accès est insuffisant, il est possible que la liste $(x_1,x_2,\dots,x_n)$ ne soit pas déterminée de manière unique, même à phase globale près. Une question importante est donc de comprendre dans quels cas la liste est uniquement déterminée et dans quels cas elle ne l’est pas.

Souvent, on pose la question sous la forme suivante. On suppose qu’un ensemble de $m$ listes de $n$ nombres $(a_1^{(1)},a_2^{(1)},\dots,a_n^{(1)}),\dots,(a_1^{(m)},a_2^{(m)},\dots,a_n^{(m)})$ est fixé et on se demande si toutes les listes de $n$ nombres $(x_1,x_2,\dots,x_n)$ sont uniquement déterminées à partir des valeurs absolues de mesures linéaires correspondantes :
\[ \begin{gather*} |a_1^{(1)}x_1+a_2^{(1)}x_2+\dots+a_n^{(1)}x_n|,\\ \dots\\ |a_1^{(m)}x_1+a_2^{(m)}x_2+\dots+a_n^{(m)}x_n|. \end{gather*}\]
Pour l’application que nous avons donnée dans le paragraphe précédent, cette question devient, par exemple : si on a choisi un ensemble de directions et placé des détecteurs selon ces directions, peut-on garantir que les mesures obtenues seront suffisantes pour déterminer n’importe quelle forme de molécule ?

Ici, la situation est assez différente selon qu’on regarde la version simple du problème, avec des nombres réels, ou la version plus sophistiquée, avec des nombres complexes. Si tous les nombres sont réels, il existe une méthode générale (quoiqu’un peu compliquée) pour résoudre cette question.

Dans le cas complexe, en revanche ...

... une telle méthode n’existe pas. Cela dépend des listes $(a_1^{(1)},a_2^{(1)},\dots,a_n^{(1)}),\dots$. Si ces listes ne vérifient pas de propriétés particulières, on ne sait a priori pas répondre. Il existe toutefois un certain nombre de cas intéressants dans lesquels c’est possible. Pour les listes qui apparaissent dans les problèmes d’imagerie décrits dans la partie précédente, par exemple, on peut répondre : la plupart des listes $(x_1,x_2,\dots,x_n)$ sont uniquement déterminées mais pas toutes, et on peut démontrer que les listes qui ne sont pas uniquement déterminées sont « très rares ».

Dans le même ordre d’idées, on peut se demander quel est le plus petit $m$ possible pour lequel il existe des listes $(a_1^{(1)},a_2^{(1)},\dots,a_n^{(1)}),\dots,(a_1^{(m)},a_2^{(m)},\dots,a_n^{(m)})$ qui permettent de déterminer uniquement toutes les listes $(x_1,x_2,\dots,x_n)$ (à phase globale près).

Dans le cas réel, on peut démontrer que le plus petit $m$ est égal à $2n-1$ [BCE06].

Le cas complexe est beaucoup plus intéressant.

Des chercheurs ont démontré en 2006 que la plus petite valeur de $m$ était inférieure ou égale à $4n-2$. Plus précisément, ils ont montré que, si on choisissait $4n-2$ listes « au hasard » [4], alors ces listes vérifiaient la propriété voulue avec probabilité égale à $1$ [BBCE06]. Ce résultat a ensuite été également démontré pour $4n-4$ [CEHV15].

Pour certaines valeurs de $n$ (celles qui sont de la forme $n=2^a+1$, pour un entier $a$ positif), on sait que la plus petite valeur possible pour $m$ est exactement $4n-4$ [CEHV15] : si $m<4n-4$, quelles que soient $(a_1^{(1)},a_2^{(1)},\dots,a_n^{(1)}),\dots,(a_1^{(m)},a_2^{(m)},\dots,a_n^{(m)})$, il y a au moins une liste $(x_1,x_2,\dots,x_n)$ qui n’est pas uniquement déterminée à partir des modules de mesures linéaires associés. Des chercheurs ont conjecturé que ce résultat était vrai pour toutes les valeurs de $n$ [BCMN14] mais leur conjecture a depuis été infirmée. En effet, une chercheuse a réussi à trouver un système de $11$ listes $(a_1^{(1)},a_2^{(1)},a_3^{(1)},a_4^{(1)}),\dots,(a_1^{(11)},a_2^{(11)},a_3^{(11)},a_4^{(11)})$ qui permet de déterminer de manière unique toutes les listes de $4$ nombres complexes $(x_1,x_2,x_3,x_4)$. Comme $11<12=4\times 4-4$, cela montre que la conjecture n’est pas vraie. Les $11$ listes sont assez compliquées ; pour prouver qu’elles vérifient bien la propriété voulue, il faut s’aider d’un ordinateur et manipuler des polynômes dont les coefficients sont des entiers de plus de cent chiffres [V15] !

Algorithmes de reconstruction

Un autre axe de recherche important est de trouver des algorithmes permettant de résoudre par ordinateur des problèmes de reconstruction de phase.

Les algorithmes les plus anciens, conçus dans les années soixante-dix [5], sont « itératifs » : ils partent d’une approximation de la liste $(x_1,x_2,\dots,x_n)$ (en général extrêmement mauvaise) et essaient de raffiner progressivement cette approximation, jusqu’à obtenir un résultat très proche de la solution. Diverses heuristiques existent pour raffiner l’approximation mais aucune n’est infaillible : parfois, après quelques étapes de raffinage, on obtient une liste $(x_1,x_2,\dots,x_n)$ qui n’est pas la bonne solution mais que les heuristiques n’arrivent plus à améliorer. Même si ces algorithmes fonctionnent correctement dans certains cas, il était donc souhaitable de trouver des méthodes plus efficaces.

Une nouvelle famille d’algorithmes a vu le jour dans les cinq dernières années [CMP11] [CST13]. Leur principe est d’effectuer un changement de variables. Au lieu de reconstruire directement $(x_1,x_2,\dots,x_n)$, on essaie de reconstruire la liste de $n^2$ nombres suivante :
\[ (x_1^2,x_1x_2,x_1x_3,\dots, x_2x_1,x_2^2,x_2x_3,\dots, x_3x_1,x_3x_2, x_3^2,\dots). \]

Dans le cas complexe, ...

... on reconstruit plutôt la liste
\[(|x_1|^2,x_1\overline{x_2},\dots, x_2\overline{x_1},|x_2|^2,\dots, x_3\overline{x_1},x_3\overline{x_2},\dots). \]

Le problème qui consiste à reconstruire cette liste-là se trouve être un petit peu plus simple que le problème de départ ; de plus, si on arrive à reconstruire la liste de $n^2$ nombres, on peut facilement en déduire la liste $(x_1,x_2,\dots,x_n)$.

En testant sur des exemples de problèmes de reconstruction de phase les algorithmes de cette famille, on constate qu’ils fonctionnent bien ; dans un certain nombre de situations, on peut même démontrer rigoureusement qu’ils arrivent à trouver la solution. Leur gros inconvénient est leur temps d’exécution : lorsque $n$ augmente, $n^2$ devient rapidement très grand. Reconstruire la liste de $n^2$ nombres devient donc très lent.

En pratique, ces algorithmes sont difficiles à utiliser pour des valeurs de $n$ supérieures à quelques centaines. Or il est fréquent d’avoir $n\geq 10000$. Dans l’exemple d’application à l’imagerie moléculaire que nous avons décrit, par exemple, si la grille utilisée pour approximer la silhouette a $100$ petits carrés sur chaque côté (ce qui est une valeur raisonnable), on a $n=100^2=10000$.

La communauté qui travaille sur les problèmes de reconstruction de phase semble donc en train de revenir aux algorithmes itératifs, beaucoup plus rapides. Elle essaie de comprendre dans quels cas ces algorithmes fonctionnent et de quelle manière on peut les améliorer pour qu’ils réussissent plus souvent.

Conclusion

Nous venons de donner une présentation du domaine mathématique qu’on appelle la reconstruction de phase. Il convient de préciser que cette présentation était à certains moments un peu idéalisée. Les applications en imagerie, notamment, soulèvent, dans la pratique, divers problèmes que nous n’avons pas évoqués. Par exemple, il est rarement possible de mesurer la valeur absolue des ondes diffractées de manière exacte ; on ne peut en général mesurer qu’une valeur approximative, ce qui complique la reconstruction.

Malgré ces simplifications, nous espérons avoir clairement montré que les problèmes de reconstruction de phase posent des questions qui peuvent être formulées de manière relativement élémentaire mais qui sont néanmoins difficiles à résoudre et dont certains aspects, malgré d’importants progrès, restent incompris.

Supplément : présentation des nombres complexes

On définit les nombres complexes en « ajoutant » aux nombres réels un nombre qu’on appelle $i$ et dont on suppose que le carré vaut $-1$ :
\[\begin{equation}i^2=-1\label{eq:i2}\end{equation}\].
Les nombres complexes sont tous les nombres de la forme $a+b\times i$, avec $a$ et $b$ des nombres réels. Les opérations algébriques usuelles (addition, soustraction, ...) sont définies de la même façon que sur les réels, en tenant compte de la relation $\eqref{eq:i2}$. Par exemple,
\[\begin{align*} (1-3i) + (2+i) &= 3-2i;\\ (1-3i) \times (2+i) &= 1 \times 2 + (-3)\times 2 \times i + 1 \times i + (-3)\times i\times i\\ &= 1 \times 2 + (-3)\times 2 \times i + 1 \times i + (-3)\times (-1)\\ &= 5 - 5 i. \end{align*}\]
Cette définition peut surprendre lorsqu’on la voit pour la première fois mais les nombres complexes interviennent de manière naturelle dans presque tous les domaines des mathématiques. Ils sont également indispensables en physique. La deuxième partie de notre article utilise par exemple le fait qu’ils permettent de modéliser des phénomènes ondulatoires, comme les ondes électromagnétiques.

Par définition, le module d’un nombre complexe est
\[ |a+bi| = \sqrt{a^2+b^2}. \]
C’est un nombre réel positif. On peut vérifier que, pour tous $a,a',b,b'$,
\[ \left|(a+bi) \times (a'+b'i)\right|=|a+bi|\times|a'+b'i|. \]

Pour tout nombre réel $\theta$, on note $e^{i\theta}$ le nombre complexe suivant :
\[ e^{i\theta}=(\cos\theta) + (\sin\theta)i \]
On peut démontrer que, pour tout $\theta$,
\[ |e^{i\theta}|=\sqrt{(\cos(\theta))^2+(\sin(\theta))^2}=1, \]
et que, pour tous réels $\theta_1,\theta_2$,
\[ e^{i\theta_1}\times e^{i\theta_2}=e^{i(\theta_1+\theta_2)}. \]

Enfin, le conjugué de $a+bi$ est défini par
\[ \overline{a+bi}=a-bi. \]

Références

Travaux cités dans l’article

[BBCE06]
R. Balan, B. G. Bodmann, P. G. Casazza, D. Edidin, Painless reconstruction from magnitudes of frame coefficients, Journal of Fourier Analysis and Applications, 15-4, 2009.

[BCMN14]
A. S. Bandeira, J. Cahill, D. G. Mixon, A. A. Nelson, Saving phase : injectivity and stability for phase retrieval, Applied and Computational Harmonic Analysis, 37-1, 2014.

[CEHV15]
A. Conca, D. Edidin, M. Hering, C. Vinzant, Algebraic characterization of injectivity in phase retrieval, Applied and Computational Harmonic Analysis, 32-2, 2015.

[CMP11]
A. Chai, M. Moscoso, G. Papanicolaou, Array imaging using intensity-only measurements, Inverse Problems, 27-1, 2011.

[CST13]
E. J. Candès, T. Strohmer, V. Voroninski, PhaseLift : exact and stable signal recovery from magnitude measurements via convex programming, Communications in Pure and Applied Mathematics, 66-8, 2013.

[GS72]
R. Gerchberg, W. Saxton, A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik, 35, 1972.

[V15]
C. Vinzant, A small frame and a certificate of its injectivity, Sampling theory and applications conference proceedings, 2015.

Autres lectures

En plus des sources citées dans le paragraphe précédent, on pourra consulter les deux articles suivants :

Y. Schechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, M. Segev, Phase retrieval with application to optical imaging : a contemporary overview, IEEE Signal processing magazine, 32-3, 2015.

J. L. C. Sanz, Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude, SIAM Journal on Applied Mathematics, 45-4, 1985.

Le premier est une revue sur les problèmes de reconstruction de phase en imagerie et les algorithmes utilisés pour les résoudre. Le second explique le résultat que nous avons énoncé au sujet de l’unicité de la reconstruction dans le cas de l’imagerie.

Sources des images

Toutes les images qui n’ont pas été réalisées par l’auteure proviennent de Wikimedia Commons :

La simulation de reconstruction a été effectuée par l’auteure avec le logiciel PhaseCut, qui utilise lui-même le simulateur spsim, ainsi que le résolveur SDPT3.

Post-scriptum :

Merci à amic, Jérôme Buzzi, Carole Gaboriau, Élise Janvresse, FlavienK et Frédéric Le Roux pour leur relecture, leur aide technique et leurs conseils.

Article édité par Frédéric Le Roux

Notes

[1Remarque à destination des personnes qui connaissent les matrices : si on représente la liste de nombres complexes sous la forme d’un vecteur vertical $\boldsymbol{x}=\left(\begin{smallmatrix}x_1\\\vdots\\x_n\end{smallmatrix}\right)$, les « informations » sont de la forme $y=A\boldsymbol{x}$, où $A$ est une matrice à $n$ colonnes, avec autant de lignes que de mesures linéaires. Il suffit que l’application linéaire représentée par $A$ soit injective pour qu’on puisse reconstruire $\boldsymbol{x}$ à partir de $y$.

[2La valeur absolue d’un nombre $x$, qu’on note $|x|$, est définie par $\left\{\begin{array}{rll}|x|&=x&\mbox{ si }x\geq 0,\\|x|&=-x&\mbox{ sinon.}\end{array}\right.$

[3En choisissant bien le système de coordonnées, on voit apparaître une version discrète de la transformée de Fourier bidimensionnelle.

[4L’expression « tirer une liste au hasard » nécessite d’être précisément définie.

[5(par exemple [GS72])

Partager cet article

Pour citer cet article :

Irène Waldspurger — «Problèmes de reconstruction de phase» — Images des Mathématiques, CNRS, 2017

Crédits image :

Première photo - https://commons.wikimedia.org/wiki/File:Castle_In_Trim,_County_Meath_-_geograph.org.uk_-_303169.jpg
Deuxième photo - https://commons.wikimedia.org/wiki/File:Trim_Castle_6.jpg
Troisième photo - https://commons.wikimedia.org/wiki/File:TrimCastlePortal.jpg
Vue 3D du château de Trim, en Irlande - https://commons.wikimedia.org/wiki/File:Thumbnail_GIF_of_3D_Model_of_Trim_Castle-320x160.gif
(b) Son approximation par des carrés noirs et blancs - Travail personnel
(a) L’objet d’intérêt - http://commons.wikimedia.org/wiki/File:1-Adamantyl-nitrilium-N-tetrakis (trifluoromehyl)cyclopentadienylide-3D-spacefill.png
(c) Sa représentation comme une liste de nombres - Travail personnel
img_16396 - Travail personnel

Commentaire sur l'article

  • Merci !

    le 13 janvier à 14:25, par Walabiz

    Excellent article ! Touffu et compréhensible comme je les aime ! =)

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM