---
title: VISI601_CMI Analyse spectrale de graphes/maillages
type: slide
slideOptions:
transition: slide
progress: true
slideNumber: true
---
# Analyse spectrale de graphes/maillages
> [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)
---
## Maillage
| Maillage (10264 sommets) | (20532 triangles) |
| -------------------------------------------------------------------------------------------------- | --------- |
|  |  |
---
## Analyse spectrale via l'opérateur Laplacien
* On ne peut directement définir de base orthogonale "fréquentielle" sur un maillage
* seulement des cas particuliers: tore (DFT), grille régulière (DCT), sphère (spherical harmonics)
* la **base spectrale** sera les vecteurs propres de l'opérateur Laplacien
* plusieurs façons de définir un **opérateur Laplacien** sur un graphe/maillage
* Laplacien de graphe: générique, simple, symétrique, mais avec distorsions
* Laplacien des "co-tangentes": spécifique aux surfaces triangulées, moins de distorsions
* Laplacien par noyau de diffusion: générique, précis, mais très lent à calculer
---
## Laplacien de graphe
Soit $G=(V,E)$ un graphe, où $V=\{1, \ldots, n\}$ est l'ensemble des $n$ sommets,
$E\subset V \times V$ est l'ensemble des arêtes, $G$ supposé non orienté
:::info
**Laplacien de graphe $L$** : matrice de taille $n \times n$, t.q.
$L_{ij}=1$ si $(i,j) \in E$
$L_{ii}=-\sum_{j\neq i }L_{ij}$
:::
:::success
$L$ est donc symétrique à valeur réelle,
et donc diagonalisable dans une base orthogonale
:::
Soit $(\lambda_i,\mathbf{v}_i)$ ses valeurs propres/vecteurs propres triées $\searrow$
---
## Vecteurs propres du Laplacien de graphe
Analogue de la décomposition de Fourier
| $V_1$ | $V_2$ | $V_3$ |
| -------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------- | --- |
|  |  |  |
---
## Vecteurs propres du Laplacien de graphe
| $V_4$ | $V_5$ | $V_6$ |
| -------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------- |
|  |  |  |
---
## Vecteurs propres du Laplacien de graphe
| $V_7$ | $V_8$ | $V_9$ |
| -------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------- |
|  | |  |
---
## Reconstruction partielle sur la base des vecteurs propres
| 10 vecteurs | 50 vecteurs | 250 vecteurs | 1250 vecteurs |
| -------- | -------- | -------- | ----- |
|  |  |  |  |