Reconstruire un signal à partir de mesures imparfaites

Sur une courte fenêtre de temps, un capteur enregistre une grandeur que l'on choisit de modéliser par un polynôme de degré au plus 2. Ce choix ne prétend pas décrire tous les signaux : il fixe un modèle de dimension finie, assez simple pour poser une question fondamentale de reconstruction. Des mesures permettent-elles de retrouver les paramètres du modèle ? Et que signifie « reconstruire au mieux » lorsque les mesures sont incompatibles entre elles ?

On considère donc les signaux

$$s_x(t)=\alpha+\beta t+\gamma t^2, \qquad x=\begin{pmatrix}\alpha\\ \beta\\ \gamma\end{pmatrix}\in\mathbb R^3.$$

Pour $u,v\in\mathbb R^m$, on utilise le produit scalaire canonique

$$\langle u,v\rangle=u^\mathsf{T}v$$

et la norme associée $\|u\|^2=\langle u,u\rangle$. La transposée d'une matrice $A$ est notée $A^\mathsf{T}$.

I - Quand les mesures sont exactes

1. Un premier capteur fournit les trois mesures exactes

$$s(-1)=13,\qquad s(0)=10,\qquad s(1)=11.$$

Déterminer $\alpha$, $\beta$ et $\gamma$.

2. Posons

$$A_0= \begin{pmatrix} 1&-1&1\\ 1&0&0\\ 1&1&1 \end{pmatrix}, \qquad y_0= \begin{pmatrix} 13\\10\\11 \end{pmatrix}.$$

(a) Vérifier que la reconstruction précédente équivaut au système $A_0x=y_0$ et préciser les dimensions de tous les objets. (b) Montrer que $A_0$ est inversible.

3. On mesure maintenant un signal du même modèle en trois instants distincts $t_1,t_2,t_3$. On note

$$A(t_1,t_2,t_3)= \begin{pmatrix} 1&t_1&t_1^2\\ 1&t_2&t_2^2\\ 1&t_3&t_3^2 \end{pmatrix}.$$

Sans calculer son déterminant, montrer que l'application $x\mapsto A(t_1,t_2,t_3)x$ est injective. En utilisant le fait qu'elle va de $\mathbb R^3$ dans $\mathbb R^3$, en déduire que trois mesures exactes prises en trois instants distincts déterminent un unique signal du modèle.

4. Expliquer pourquoi une ou deux mesures ponctuelles ne peuvent pas, en général, déterminer de façon unique les trois paramètres d'un signal quadratique. Que change l'ajout de mesures supplémentaires lorsque celles-ci sont toutes parfaitement compatibles avec le modèle ?

En pratique, les mesures sont affectées par des erreurs. Ajouter des données peut alors faire apparaître non plus une meilleure détermination du même système, mais une incompatibilité : aucun signal du modèle ne passe exactement par tous les points mesurés.

II - Cinq mesures qui ne peuvent pas toutes être exactes

On effectue des mesures aux instants $-2,-1,0,1,2$ et l'on obtient

$$y= \begin{pmatrix} 21\\11\\10\\13\\15 \end{pmatrix}.$$

Il y a désormais cinq équations pour trois paramètres : on parle d'un système surdéterminé. La matrice qui associe à un paramètre $x$ les cinq valeurs prédites par le modèle est

$$A= \begin{pmatrix} 1&-2&4\\ 1&-1&1\\ 1&0&0\\ 1&1&1\\ 1&2&4 \end{pmatrix}\in\mathcal M_{5,3}(\mathbb R).$$

5. (a) Déterminer l'unique polynôme quadratique qui reproduit exactement les trois mesures aux instants $-1,0,1$. (b) Comparer sa valeur en $t=2$ avec la mesure correspondante. En déduire que le système $Ax=y$ n'a pas de solution.

6. Pour $x\in\mathbb R^3$, on appelle résidu

$$r(x)=Ax-y\in\mathbb R^5.$$

(a) Montrer que

$$\sum_{i=1}^5 r_i(x)=5\alpha+10\gamma-70.$$

Pourquoi ce seul critère est-il insuffisant pour mesurer la taille globale des erreurs ? (b) On décide de mesurer l'erreur globale par

$$J(x)=\|r(x)\|^2=\|Ax-y\|^2.$$

Écrire $J(x)$ comme une somme de cinq carrés et expliquer pourquoi ce critère évite les compensations de signe entre erreurs positives et négatives.

III - Faire émerger la meilleure reconstruction

Nous cherchons maintenant un paramètre $\widehat x$ qui minimise $J$ sur $\mathbb R^3$.

7. Soient $x,h\in\mathbb R^3$ et $\lambda\in\mathbb R$. (a) Développer $J(x+\lambda h)$ et établir

$$J(x+\lambda h) = J(x) +2\lambda\langle r(x),Ah\rangle +\lambda^2\|Ah\|^2.$$

(b) Supposons que $x$ minimise $J$. En étudiant, pour chaque $h$, le trinôme en $\lambda$ obtenu en (a), montrer que

$$\langle r(x),Ah\rangle=0 \quad\text{pour tout }h\in\mathbb R^3.$$

(c) En déduire successivement

$$A^\mathsf{T}r(x)=0 \qquad\text{puis}\qquad A^\mathsf{T}Ax=A^\mathsf{T}y.$$

Ces dernières relations sont appelées les équations normales. Préciser les dimensions de $A^\mathsf{T}$, $A^\mathsf{T}A$ et $A^\mathsf{T}y$.

8. Réciproquement, supposons que $x$ vérifie les équations normales. (a) Montrer que, pour tout $h\in\mathbb R^3$,

$$J(x+h)=J(x)+\|Ah\|^2.$$

(b) En déduire que $x$ minimise $J$. (c) Montrer que, si $A$ est injective, ce minimum est atteint en un unique point. (d) Toujours lorsque $A$ est injective, montrer que $A^\mathsf{T}A$ est inversible. On pourra partir de

$$z^\mathsf{T}A^\mathsf{T}Az=\|Az\|^2.$$

9. Revenons aux cinq mesures précédentes. (a) Montrer que la matrice $A$ est injective et en déduire son rang. (b) Calculer exactement $A^\mathsf{T}A$ et $A^\mathsf{T}y$. (c) Résoudre les équations normales et déterminer la meilleure reconstruction $\widehat x$.

10. (a) Calculer le vecteur des cinq valeurs prédites $A\widehat x$. (b) En déduire le résidu $r(\widehat x)$ puis la valeur minimale $J(\widehat x)$. (c) Vérifier directement que $A^\mathsf{T}r(\widehat x)=0$.

IV - Ce que signifie « reconstruire au mieux »

11. Notons $t_1=-2,t_2=-1,t_3=0,t_4=1,t_5=2$ et $r_i=r_i(\widehat x)$. (a) Traduire $A^\mathsf{T}r(\widehat x)=0$ sous la forme de trois identités portant sur

$$\sum r_i,\qquad \sum t_i r_i,\qquad \sum t_i^2r_i.$$

(b) Les trois colonnes de $A$ décrivent, dans $\mathbb R^5$, les variations des valeurs prédites lorsque l'on modifie séparément $\alpha$, $\beta$ ou $\gamma$. Expliquer en quel sens le résidu optimal est orthogonal à toutes les variations permises par le modèle. (c) En déduire une interprétation géométrique de $A\widehat x$ comme le point de $\operatorname{Im}(A)$ le plus proche de $y$. Identifier le lien avec la projection orthogonale.

12. Le polynôme trouvé à la question 5, qui ajuste exactement les trois mesures centrales, correspond au paramètre

$$x_c= \begin{pmatrix} 10\\1\\2 \end{pmatrix}.$$

(a) Calculer $Ax_c-y$ et $J(x_c)$. (b) Comparer avec $J(\widehat x)$ et expliquer pourquoi ajuster exactement un sous-ensemble de mesures n'est pas, en général, la meilleure stratégie lorsque toutes les mesures comptent.

13. Supposons maintenant que les données soient parfaitement compatibles : il existe $x_0\in\mathbb R^3$ tel que $y=Ax_0$, et $A$ est injective. (a) Quelle est la valeur minimale possible de $J$ ? (b) Montrer que la reconstruction par les équations normales redonne nécessairement $x_0$. Les moindres carrés prolongent ainsi la reconstruction exacte au cas où les mesures deviennent incompatibles.

14. Synthèse. Soient $m,n\in\mathbb N^*$, $A\in\mathcal M_{m,n}(\mathbb R)$ et $y\in\mathbb R^m$. On suppose que l'application $x\mapsto Ax$ est injective. (a) Montrer qu'il est nécessaire que $m\ge n$. (b) Montrer que le problème

$$\min_{x\in\mathbb R^n}\|Ax-y\|^2$$

admet une unique solution et que celle-ci est caractérisée par

$$A^\mathsf{T}A\widehat x=A^\mathsf{T}y.$$

(c) En déduire la formule

$$\widehat x=(A^\mathsf{T}A)^{-1}A^\mathsf{T}y.$$

(d) Préciser ce que devient cette formule lorsque $y$ appartient déjà à $\operatorname{Im}(A)$.