Analyse harmonique sur graphes dirigés et applications

Analyse harmonique sur graphes dirigés et applications

Notions sur la théorie des graphes non dirigés

Un graphe est un objet mathématique composé d’un ensemble de sommets reliés entre eux par des arêtes. Tout au long de ce chapitre, nous considérons uniquement le cas des graphes non dirigés. Cette section contient les principales définitions relatives aux graphes non dirigés [39, 40]. Définition 2.1. Un graphe simple (c’est-à-dire sans arêtes multiples) non dirigé et non pondéré est un couple G “ pV, Eq où V constitue l’ensemble des sommets et E Ď V ˆ V l’ensemble des arêtes, chaque arête étant une paire de sommets non nécessairement distincts. Si u et v sont des sommets, nous représentons une arête reliant les sommets u et v par e “ pu, vq. Si e “ pu, vq forme une arête, alors nous disons que u et v sont adjacents ou que v est voisin de u. Ceci est représenté par u „ v. Dans cette thèse, nous étudierons exclusivement les graphes finis, c’est-à-dire des graphes dont l’ensemble des sommets et l’ensemble des arêtes est fini. Ainsi le terme « graphe » voudra toujours dire « graphe simple fini ». Nous définissons par |V|, la cardinalité de l’ensemble des sommets V, c’est-à-dire le nombre d’éléments dans V. Le graphe G peut être représenté à travers sa matrice d’adjacence que nous définissons de la manière suivante. Définition 2.2 (Représentation algébrique d’un graphe non dirigé et non pondéré). Soit G “ pV, Eq un graphe simple non dirigé et non pondéré où V “ pv1, . . . , vN q et de cardinalité |V| “ N. La matrice d’adjacence A “ taiju1ďi,jďN P R NˆN se rapportant à cet ensemble de sommets est la matrice N ˆ N booléenne avec : aij “ # 1 si pvi , vj q P E 0 sinon. et la relation : aij “ aji, @ i, j P t1, . . . , Nu. (2.1) 16 Nous noterons que la relation (2.1) caractérise la notion de symétrie et est exprimée sous forme matricielle par la relation : AJ “ A, où AJ est la matrice transposée de A. Plus généralement, nous pouvons considérer le cas des graphes non dirigés et pondérés. Nous définissons un graphe non dirigé et pondéré de la manière suivante. Définition 2.3. Soit G “ pV, Eq un graphe non dirigé et non pondéré et w : V ˆ V Ñ R` une application qui associe une valeur wij “ wpvi , vj q à chaque arête pvi , vj q. L’application w est appelée fonction de poids. Le triplet G “ pV, E, wq est donc un graphe non dirigé et pondéré. Un graphe non dirigé et pondéré G “ pV, E, wq peut être entièrement représenté par sa matrice d’adjacence W “ twiju1ďi,jďN P R NˆN ` . Si wij “ 0, pour un couple pi, jq P t1, . . . , Nu 2 , alors il n’existe pas d’arête entre les sommets vi et vj . Nous définissons le degré (pondéré) d’un sommet vi P V comme la somme des poids des arêtes associées à vi , c’est-à-dire di “ řN j“1 wij . Si le graphe G est non pondéré, le degré d’un sommet est simplement le nombre de sommets voisins à ce sommet. Dans ce chapitre, nous supposons les poids de la matrice d’adjacence W positifs ou nuls. Nous définissons la notion de chaîne dans un graphe non dirigé de la manière suivante. Définition 2.4. Soit G “ pV, Eq un graphe non dirigé. Une chaîne reliant un sommet vi à un sommet vj est définie par une suite finie d’arêtes consécutives, reliant vi à vj . Nous définissons un graphe non dirigé connexe de la manière suivante. Définition 2.5. Un graphe non dirigé G “ pV, Eq est connexe si chaque sommet est accessible à partir de n’importe quel autre. Autrement dit, si pour tout couple de sommets distincts pvi , vj q P V ˆ V il existe une chaîne reliant vi à vj . 3 Généralités sur la théorie des opérateurs Nous rappelons les notions essentielles de la théorie des opérateurs en dimension finie nécessaires à la compréhension des prochaines sections [41, 42]. Dans cette section, H et H 1 sont deux espaces de Hilbert de dimension dim H “ N ă 8, dim H 1 “ M ă 8 et e “ pe1, . . . , eN q est une base orthonormale de H. Pour tout vecteur donné x P H, ses coordonnées par rapport à 17 e seront notées x1, . . . , xN , c’est-à-dire x “ x1e1 `¨ ¨ ¨ `xN eN et x le vecteur colonne correspondant : x “ px1, . . . , xN q J. Nous définissons la notion d’opérateur de la manière suivante. Définition 2.6. Toute application linéaire continue T : H Ñ H 1 s’appelle un opérateur. L’espace vectoriel LpH, H 1 q des applications linéaires continues de H dans H 1 est l’espace des opérateurs de H dans H 1 . Par souci de simplicité, supposons H “ H 1 . Un opérateur linéaire T : H Ñ H est représenté par rapport à la base orthonormale e par une matrice T P C NˆN tel que les tij P C de T s’expriment de la manière suivante : tji “ xej , T eiy. Nous définissons la notion d’opérateur adjoint de la manière suivante. Définition 2.7. Soit T P LpH, Hq. Alors il existe un unique opérateur T ˚ P LpH, Hq tel que : xT x, yyH “ xx, T ˚ yyH @x, y P H. L’opérateur T ˚ s’appelle l’adjoint de T. En dimension finie, l’opérateur T ˚ , est représenté par la matrice conjuguée et transposée T J de T (ou seulement TJ si T P R NˆN ). Définition 2.8. Si T P LpH, Hq est tel que T “ T ˚ , on dit que l’opérateur T est autoadjoint (ou hermitien). Les opérateurs autoadjoints ont des propriétés particulièrement importantes que nous examinons. Théorème 2.1 (Théorème spectral des opérateurs auto-adjoints [43]). Soit H un espace de Hilbert de dimension dim H “ N ă 8 et T P LpH, Hq un opérateur auto-adjoint. Alors il existe une base orthonormale tfnu N n“1 de H et une suite de réels tλnu N n“1 tels que pour tout n P t1, . . . , Nu, T fn “ λnfn et pour tout x P H : T x “ ÿ N n“1 λnxx, fnyfn. Nous définissons une isométrie de la manière suivante. Définition 2.9. Soient H, H 1 deux espaces de Hilbert. Une transformation linéaire V : H ÞÑ H 1 est une isométrie si et seulement si : }Vpx ´ yq}H1 “ }x ´ y}H, @x, y P H. 18 Nous définissons l’entrelacement entre deux opérateurs linéaires de la manière suivante. Définition 2.10. Soient H, H 1 deux espaces de Hilbert. Une transformation linéaire inversible bornée V P LpH, H 1 q entrelace un opérateur linéaire M P LpH, Hq avec un opérateur linéaire S P LpH 1 , H 1 q si : V M “ SV . Les opérateurs linéaires M et S sont alors dits similaires. Nous introduisons maintenant la notion d’opérateur semi-défini positif. Définition 2.11. Soit T P LpH, Hq un opérateur auto-adjoint. L’opérateur T est dit semi-défini positif si : xx, T xy ě 0, @x P H. 4 Fondamentaux du traitement de signal sur graphes Dans cette section, nous introduisons les aspects fondamentaux du traitement de signal sur graphes [16, 17, 44].

Signaux sur graphes

Soit G “ pV, Eq un graphe non dirigé et f : V Ñ C une fonction définie sur l’ensemble des sommets V “ pv1, . . . , vN q. Nous définissons un signal sur graphe, noté f comme la représentation sous forme de vecteur colonne de la fonction f appliquée en chacun des sommets vi P V, c’est-à-dire : f “ pfpv1q, . . . , fpvN qqJ P C N . Nous définissons la notion d’espace de fonctions définies sur les sommets d’un graphe arbitraire de la manière suivante. Définition 2.12 ([45]). Soit G “ pV, Eq un graphe non dirigé et µ : V Ñ r0, 8q une fonction sur V considérée comme une mesure sur V en posant µpUq “ ř xPU µpxq, U Ă V. Pour p P r1, 8q, nous notons ` q pV, µq, l’espace de fonctions f : V Ñ C tel que }f}` qpµ,Vq “ $ ’& ’% ˆ ř xPV |fpxq|qµpxq ˙1{q ă 8, q P r1, 8q. max xPV |fpxq|µpxq ă 8, q “ 8. Nous supposons les fonctions sur G définies sur l’espace ` 2 pV, µq. L’espace ` 2 pV, µq est l’espace de Hilbert de fonctions définies sur l’ensemble des sommets V de G muni du produit scalaire suivant : xf, gyµ “ ÿ xPV fpxqgpxqµpxq, pour tout f, g P ` 2 pV, µq et où fpxq est le complexe conjugué fpxq. 1

Filtrage sur graphes

Un opérateur linéaire sur un graphe non dirigé G “ pV, Eq de cardinalité |V| “ N est représenté par une matrice H P C NˆN qui agit sur un signal sur graphe s P C N et produit un signal sur graphe s˜ P C N selon le produit matrice vecteur : s˜ “ Hs. Dans le cadre du traitement de signal sur graphes et inspiré du traitement de signal classique, on s’intéresse principalement à un type de filtres sur graphes qui commutent avec un opérateur de référence sur graphe non dirigé R, c’est-à-dire : HR “ RH. Nous définissons un filtre sur graphe H comme une somme finie polynomiale d’un opérateur de référence R, c’est-à-dire : H “ ÿ T t“0 htRt , ht P C, @t “ 0, . . . , T. Le théorème suivant établit, sous une condition particulière, qu’un filtre sur graphe commutant avec un opérateur de référence donné peut s’exprimer comme un polynôme de celui-ci. Théorème 2.2. Soit R un opérateur linéaire de référence sur un graphe non dirigé G que nous supposons diagonalisable. Nous supposons également les polynômes caractéristique et minimal de R égaux, c.-à-d. pRpxq “ mRpxq. Alors un filtre sur graphe H qui commute avec R s’exprime comme une somme finie polynomiale de R, c’est-à-dire : H “ ÿ T t“0 htRt , ht P C, @t “ 0, . . . , T. Le théorème 2.2 indique que si un filtre H jouit des trois conditions suivantes : 1. Commute avec un opérateur de référence R. 2. Diagonalisable. 3. Chacun des espaces propres est de dimension un. alors le filtre peut s’exprimer comme une somme finie polynomiale de R. Ce type de filtre sur graphe est appelé filtre linéairement invariant par rapport à R (linear shift invariant en anglais) par Sandryhaila et Moura [44]. Cette notion d’invariance linéaire par rapport à un opérateur de référence sur graphe non dirigé semble assez restrictive dans la mesure où de nombreux opérateurs de référence sur graphes n’admettent pas systématiquement des espaces 20 propres de dimension égale à 1 mais éventuellement des espaces propres de dimension supérieure à 1. Par contre, il sera toujours possible de construire un filtre sur graphe comme une somme finie polynomiale d’un opérateur de référence. Un tel filtre est toujours invariant par rapport à son opérateur de référence. En revanche un filtre qui commute avec un opérateur de référence ne respectant pas l’une des trois conditions énoncées ci-dessus ne peut pas toujours s’exprimer comme un polynôme de cet opérateur de référence.