---
title: VISI601_CMI Analyse spectrale
type: slide
slideOptions:
transition: slide
progress: true
slideNumber: true
---
# Analyse spectrale
> [name=Jacques-Olivier Lachaud][time=January 2022][color=#907bf7]
> (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique)
###### tags: `visi601`
Retour à [VISI601_CMI (Main) Algorithmique numérique](https://codimd.math.cnrs.fr/s/IWTaBkA9m)
---
## Opérateur de double moyennage
Si $\mathbf{v}$ est un vecteur de $n$ données, on va moyenner deux fois ses valeurs:
$m_i = \frac{v_i+v_{i+1}}{2}, s_i = \frac{m_{i-1}\,+m_{i}}{2}$, indices pris modulo $n$
$$
\mathbf{m}=\underbrace{\frac{1}{2}\begin{bmatrix}1 & 1 & \ldots & 0 & 0 \\ 0 & 1 & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & 0 & 1 & 1 \\ 1 & 0 & \cdots & 0 & 1 \end{bmatrix}}_{M^+}
\mathbf{v}, \quad
\mathbf{s}=\underbrace{\frac{1}{2}\begin{bmatrix}1 & 0 & \ldots & 0 & 1 \\ 1 & 1 & 0 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & 1 & 1 & 0 \\ 0 & 0 & \cdots & 1 & 1 \end{bmatrix}}_{M^-}
\mathbf{v}.
$$
Processus de moyennage: $\mathbf{x}^{(0)}$ donné, $\mathbf{x}^{(k+1)} := \underbrace{M^- M^+}_{A} \mathbf{x}^{(k)}$
---
## Itérations successives de moyennage sur un contour
$\color{blue}{\text{Contour original}\,(X,Y)}\quad \color{red}{\text{lissé 512 fois}\,(A^{2^9}X, A^{2^9}Y)}\quad \color{green}{\text{16384 fois}\,(A^{2^{15}}X, A^{2^{15}}Y)}$
---
## Interprétation géométrique
$\mathbf{x}^{(k+1)} := A \mathbf{x}^{(k)} = \mathbf{x}^{(k)} + \underbrace{(A-I)\mathbf{x}^{(k)}}_{\delta \mathbf{x}^{(k)}}$ avec déplacement $\delta \mathbf{x}^{(k)}=(A-I)\mathbf{x}^{(k)}$
$$
\text{Soit}\, L=\begin{bmatrix}-2 & 1 & \ldots & 0 & 1 \\ 1 & -2 & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & 1 & -2 & 1 \\ 1 & 0 & \cdots & 1 & -2 \end{bmatrix}
\quad\text{alors}\quad\delta \mathbf{x}^{(k)}=\frac{1}{4} L \mathbf{x}^{(k)}
$$
$L$ est appelé **Laplacien discret 1D**
---
## Comment montrer que "moyenner par A" lisse un contour ?
On cherche un moyen de comprendre $A^k \mathbf{x}^{(0)} = \left( I+ \frac{1}{4}L \right)^k \mathbf{x}^{(0)}$
:::info
**Valeurs propres/vecteurs propres** de la matrice $L$ (de taille $n \times n$)
couples $(\lambda_i,\mathbf{w}_i)$ tels que $L \mathbf{w}_i = \lambda_i \mathbf{w}_i$
:::
Oui mais on cherche à comprendre $A^k$, pas $L^k$ !?!
En fait les $\mathbf{w}_i$ sont aussi vecteurs propres de $A$, et de $A^k$ !
**valeurs propres de $A^k$** c'est simplement $\mu_i=(1+\lambda_i/4)^k$
car $A^k \mathbf{w}_i = (I+L/4)^k \mathbf{w}_i = (1+\lambda_i/4)^k \mathbf{w}_i$
---
## Mais c'est quoi les vecteurs propres ?
Si la matrice est réelle et sym., ses vecteurs propres forment une base **orthogonale**
Pour tout $i$, $\mathbf{w}_i^T \mathbf{w}_i =1$ et tout $j\neq i$, $\mathbf{w}_i^T \mathbf{w}_j =0$
Pour $L$ les vecteurs propres sont les sinusoïdes et cosinusoïdes !
$\mathbf{w}_0[j]=\sqrt{\frac{1}{n}}\cos(2\pi 0 \frac{j}{n}) \quad \mathbf{w}_1[j]=\sqrt{\frac{2}{n}}\cos(2\pi 1 \frac{j}{n}) \quad \mathbf{w}_2[j]=\sqrt{\frac{2}{n}}\sin(2\pi 1 \frac{j}{n})$
---
## Et les valeurs propres de L et de A ?
Pour $L$, $\lambda_i$ décroît de 0 à -4, on montre $\lambda_i=-4\sin^2(\frac{i\pi}{2n})$
Pour $A=I+\frac{1}{4}L$, valeur propre $\mu_i=1+\lambda_i/4$ décroît de 1 à 0
Pour $A^k=(I+\frac{1}{4}L)^k$, valeur propre $\mu^k_i=(1+\lambda_i/4)^k$ décroît vite de 1 à 0
:::success
$A$ ne change pas le barycentre et contracte selon toutes les fréquences.
$A^k$ ne change pas le barycentre et contracte de + en + fort.
:::
---
## Projeter sur la base des vecteurs propres
On peut décomposer $\mathbf{x}$ sur la base des vecteurs propres
$\widetilde{\mathbf{x}}=\mathbf{W}^T \mathbf{x}$, avec $\mathbf{W}$ matrices des vecteurs colonnes de $\mathbf{w}_i$
==reconstruction totale== $\mathbf{x}=\sum_{i=0}^{n-1} \widetilde{\mathbf{x}}_i \mathbf{w}_i$
==reconstruction partielle== $\widehat{\mathbf{x}}^k=\sum_{i=0}^{k} \widetilde{\mathbf{x}}_i \mathbf{w}_i$
$(\widehat{X}^3,\widehat{Y}^3) \quad (\widehat{X}^{20},\widehat{Y}^{20}) \quad (\widehat{X}^{200},\widehat{Y}^{200}) \quad (\widehat{X}^{2000},\widehat{Y}^{2000})$
---
## Analyse spectrale
* le terme **analyse spectrale** vient de cette décomposition sur un espace de fréquences
* c'est exactement la transformée de Fourier discrète (TFD) d'un signal
* le terme **filtrage** consiste à agir sur la décomposition fréquentielle
* le filtre moyenneur $A^k$ est un filtre passe-bas: il laisse inchanger les basses fréquences mais écrase les hautes fréquences
* la TFD a de nombreuses applications:
* compression (son, image (JPEG), vidéo, maillage)
* filtrage (égaliseur, rehaussement, ...)
* mise en correspondance, comparaison
* calcul (dérivées, diffusion + rapide dans espace de Fourier)
* On étend l'analyse spectrale aux surfaces, aux graphes, grace au **Laplacien**