Analyse de Fourier sur des variétés et des graphes

Section 2.5 Analyse de Fourier sur des variétés et des graphes

...

Subsubsection 2.5.1 Théorie spectrale des graphes

L'idée ici est de définir la notion de la fonction sur un graphe puis les notions de dérivée et de Laplacien sur un graphe, et de montrer que son spectre donne des informations sur le graphe (au même titre que le spectre de l'opérateur de Laplace Beltrami donne des informations sur la variété sous-acjente).

On travaillera sur des graphes non orientés pondérés: \(G=[V,W]\) avec \(W\) la matrice des poids.

Définition 2.40. Espace de Hilbert des sommets.

On note \(\mathcal{H}(V,\chi)\) l'espace des fonctions définit sur les sommets. Il s'agit d'un espace de Hilbert \((\mathbb{R}^{\mid V\mid}, \langle .,. \rangle_v)\) muni du produit scalaire

\begin{equation*} \langle f,g \rangle_V = \frac{1}{n}\sum_{i=1}^nf_ig_i \chi_{i} \end{equation*}

avec \(\chi_{i} = \chi_{in}(\frac{1}{n}\sum_{j=1}^nw_{ji})+\chi_{out}(\frac{1}{n}\sum_{j=1}^nw_{ij})\) (la somme des poids des arrêtes entrantes et sortantes) et avec \(\chi_{in}(x)>0, \chi_{out}(x)>0\) sur \(\mathbb{R}_{+}^*\) et \(\chi_{in}(0)=0\text{,}\) \(\chi_{out}(0)=0\text{.}\)

Définition 2.41. Espace de Hilbert des arêtes.

On note \(\mathcal{H}(E,\psi)\) l'espace des fonctions définit les arêtes. Il s'agit d'un espace de Hilbert \((\mathbb{R}^{\mid E\mid}, \langle .,.\rangle_E)\) muni du produit scalaire

\begin{equation*} \langle f,g \rangle_E = \frac{1}{2n^2}\sum_{i,j=1}^nf_{ij}g_{ij} \psi(w_{ij}) \end{equation*}

avec \(\psi(x)>0\) sur \(\mathbb{R}_{+}^*\) et \(\psi(0)=0\text{.}\)

Le 1er espace peut être vu comme un espace classique de fonction (mais discret). Le second peut être vu comme un espace de flux de masse sur l'arête. Maintenant on peut définir un opérateur de différentiation entre les deux espaces. La façon dont on va construire les opérateurs se rapproche de celle utilisée dans le cours de "méthodes numériques géométriques".

Définition 2.42. Dérivée.

L'opérateur dérivée \(d:\mathcal{H}(V,\chi)\rightarrow \mathcal{H}(E,\psi)\) peut être défini par

\begin{equation*} \forall e_{ij} \in E, \quad d(e_{ij})=\gamma(w_{ij})(f(j)-f(i)) \end{equation*}

avec \(f(i),f(j)\) la valeur de la fonction \(f\) aux sommets \(i\) et \(j\text{.}\) On peut aussi le définit avec:

\begin{equation*} \forall e_{ij} \in E, \quad d^n(e_{ij})=\gamma(w_{ij})\left(\frac{f(j)}{\sqrt{d(j)}}-\frac{f(i)}{\sqrt{d(i)}}\right) \end{equation*}

avec \(d(.)\) le degré du noeud et \(\gamma: \mathbb{R}_{+}^* \rightarrow \mathbb{R}_{+}^*\text{.}\)

On peut définir l'opérateur dual avec la relation:

\begin{equation*} \langle d f,g \rangle_V = \langle f, d^*g \rangle_E, \quad \forall f \in \mathcal{H}(V,\chi), g\in \mathcal{H}(E,\psi) \end{equation*}

Définition 2.43. Dual de la dérivée.

Le dual de l'opérateur dérivé \(d\) est donnée par

\begin{equation*} \forall v_j \in V, \quad d^*(v_j)=\frac{1}{2 n \chi(d_j)}\sum_{i=1}\gamma(w_{ij})\psi(w_{ij})(g_{ij}-g_{ji}) \end{equation*}

avec \(\psi(x)>0\) sur \(\mathbb{R}_{+}^*\) et \(\psi(0)=0\text{.}\)

A partir de la, comme en géométrie différentielle ou le Laplacien est la composée de la dérivée extérieure et de son dual, on va définir l'opérateur de Laplace sur un graphe à partir de la dérivée sur graphe et de son dual.

Définition 2.44. Laplacien sur un graphe.

L'opérateur laplacien sur un graphe \(\Delta :\mathcal{H}(V,\chi)\rightarrow \mathcal{H}(V,\psi)\) est défini par

\begin{equation*} \Delta (i)= d^* d \end{equation*}

On peut obtenir une formule explicite:

\begin{equation*} \Delta(i) = \frac{1}{\chi(i)}\left[ f(i)\frac{1}{n}\sum_{j=1}^n\gamma(w_{ji})^2\psi(w_{ji}) - \frac{1}{n}\sum_{j=1}^nf(j)\gamma(w_{ji})^2\psi(w_{ji})\right] \end{equation*}

On peut utiliser aussi \(d^n\) et son dual.

La définition précédente est très générale. Elle dépend des fonctions: \(\gamma\text{,}\) \(\psi\text{,}\) \(\chi_{in}\) et \(\chi_{out}\text{.}\) En pratique certains de chez choix vont donner les différents Laplacien sur les graphes introduits dans la littérature. Pour la suite on donne \(D\) la matrice des volumes des noeuds et \(W\) la matrice des poids. Maintenant introduit les 3 Laplaciens sur graphe classique dans la littérature:

Le Laplacien dit Marche aléatoire:

\begin{equation*} \Delta^{rw}f = (I_d - D^{-1}W)f \end{equation*}

obtenu avec \(\frac{\gamma(w_{ji})^2\psi(w_{ji}) }{\chi(d_i)}=\frac{w_{ij}}{d_i}\)
Le Laplacien dit non normalisé:

\begin{equation*} \Delta^{u}f = (D- W)f \end{equation*}

obtenu avec \(\frac{\gamma(w_{ji})^2\psi(w_{ji}) }{\chi(d_i)}=w_{ij}\)
Le Laplacien dit normalisé:

\begin{equation*} \Delta^{n}f = D^{-\frac12}(D- W)D^{-\frac12} \end{equation*}

obtenu avec \(d^n\) au lieu de \(d\) et \(\gamma(w_{ji})^2\psi(w_{ji}) =w_{ij}\) et \(\chi(d_i)=1\text{.}\)

Dans le cas d'un graphe orienté la matrice \(W\) est symétrique. Maintenant on va étudier les propriétés de ces opérateurs.

Lemme 2.45.

Les opérateurs précédents sont symétriques et positifs, la plus petite valeur propre est \(\lambda_0=0\) et le nombre de composantes connectées dans le graphe correspond à la dimension de l'espace propre de \(\lambda_0\text{.}\)

Preuve.

TOO DOOOO

Le Laplacien sur graphe est un opérateur qui permet d'étudier les propriétés d'un graphe. En plus de cela lorsque le graphe repose sur une variété régulière sous-jacente on peut le relier à l'opérateur de Laplace-Beltrami. On va d'abord introduire une variation de l'opérateur de Laplce Beltrami.

Définition 2.46. Laplacian a poids.

Soit \((\mathcal{M},g)\) une variété Riemanienne avec une loi de probabilité \(P\) de densité positive \(p(x)\) par rapport aux volumes naturels \(dV = \sqrt{det g}dx\text{.}\) Soit \(s\in\mathbb{R}\) le Laplacien à poids est définit par

\begin{equation*} \Delta_s f=\frac{1}{p^s}\nabla\cdot (p^s \nabla f) \end{equation*}

On obtient cela par la caractérisation:

\begin{equation*} \int_{\mathcal{M}} f\Delta_s g p^s(x) dV = -\int_{\mathcal{M}} \langle\nabla f,\nabla g\rangle p^s(x) dV \end{equation*}

Pour \(s=0\) ou \(P\) la loi uniforme on obtient l'opérateur de Laplace Beltrami classique. Si on se replace dans le cadre de notre méthode il est raisonnable d'essayer de trouver la fonction \(f\) la plus régulière possible notamment dans les zones de forte densité. Cela revient à minimiser

\begin{equation*} \int_{\mathcal{M}} \parallel\nabla f(x) \parallel_2^2 p^s dx \end{equation*}

et donc a prendre projeter sur les premiers vecteurs propres de \(\Delta_s\text{.}\)

Théorème 2.47.

Soit \(\mathcal{M}\) une variété riemannienne de dimension \(m\) incluse dans \(\mathbb{R}^d\text{.}\) Soit \(X=(x_1,...x_n)\) un échantillon obtenu avec une loi de probabilité \(P\) et de densité positive \(p(x)\) de support \(\mathcal{M}\text{.}\) Soit \(x\) à l'intérieur de la variété. On se donne un graphe \(G=[X,W]\) obtenu par la méthode des \(K\) plus proches voisins tel que si \(\parallel x_i - x_j\parallel \lt C(k)h\) alors l'arrête existe dans le graphe. Sous certaines hypothèses sur \(\mathcal{M}\text{,}\) l'algorithme des plus proches voisins et sur \(p\text{,}\) on a quel si \(h\rightarrow 0\) et \(\frac{n h^{m+2}}{log n}\rightarrow \infty\)

\(\Delta^{rw}f\) converge presque sûrement vers \(- C \Delta_s f\)
\(\Delta^{u}f\) converge presque sûrement vers \(- C p^{1-2\lambda}\Delta_s f\)

avec \(s=(1-2\lambda)\) et si \(\frac{n h^{m+4}}{log n}\rightarrow \infty\) on a

\(\Delta^{u}f\) converge presque sûrement vers \(- C p^{\frac12-\lambda}\Delta_s \left(\frac{f}{ p^{\frac12-\lambda}}\right)\)

avec \(C\) une constante dépendante de \(\lambda\) et des paramètres de l'algorithme de voisin.

Preuve.

Admis

Subsection 2.5.1 Analyse de Fourier sur un graphe

En construction

Subsection 2.5.2 Extension sur les maillages

En construction