Structure des matrices aléatoires inhomogènes

Qu'est ce qu'une matrice ? La réponse à cette question dépend fortement de la personne à qui elle est posée.

Pour un analyste de données, c'est tout simplement un grand tableau regroupant des données.
Cependant, un probabiliste dira presque sûrement que ces données sont des variables aléatoires. Un informaticien la verra comme un tableau de $0/1$ et l'interprètera comme un graphe/réseau1 où les sommets sont reliés par une arête lorsque l'entrée correspondante de la matrice est égale à $1$. Un chercheur en analyse fonctionnelle la considèrera comme un opérateur linéaire et un géomètre rajoutera que c'est une transformation linéaire. Peu importe la catégorie à laquelle on appartient, la compréhension des valeurs propres de la matrice est fondamentale. En effet, en analyse des données, les méthodes spectrales sont utilisées afin de réduire la taille et complexité de celles-ci et en éliminer les informations redondantes. En informatique, il est connu que les propriétés spectrales de la matrice d'adjacence se traduisent directement en des propriétés d'expansion du graphe associé, donnant ainsi des informations sur la connectivité et structure du réseau. Pour les matrices aléatoires, la motivation d'origine fut en mécanique quantique, où Wigner a observé que la répartition des niveaux d'énergie dans les noyaux atomiques est reliée à la distribution spectrale de certaines matrices aléatoires. Depuis, plusieurs applications ont vu le jour, comme en télécommunications où la capacité du canal de communication associé à un groupe d'antennes émettrices/réceptrices est une statistique linéaire du spectre d'une matrice aléatoire.

Géométriquement, les valeurs propres peuvent être interprétées comme des facteurs de déformation de l'espace dans certaines directions associées qui sont les vecteurs propres. De ce point de vue, il est important de connaître la "déformation maximale'', celle donnée par la plus grande valeur propre. En analyse fonctionnelle, on étudie les espaces normés et l'effet d'une transformation sur cet espace. Prenons l'exemple de $R^n$ qu'on munit de la norme Euclidienne $\Vert \cdot\Vert_2$ qui n'est autre que la distance Euclidienne à l'origine. L'espace normé $(R^n, \Vert \cdot\Vert_2)$ est caractérisé par sa boule unité $B_2^n$ qui est l'ensemble des points à distance plus petite que $1$ de l'origine i.e.
$$
B_2^n=\{x\in R^n:\, \Vert x\Vert_2= \sqrt{x_1^2+\ldots+x_n^2}\leq 1\}.
$$
Une matrice symétrique2 $A$ de taille $n\times n$ est vue comme une transformation linéaire de l'espace $(R^n, \Vert\cdot \Vert_2)$. Celle-ci transforme la boule Euclidienne $B_2^n$ en une ellipse $AB_2^n$ dont les axes sont les vecteurs propres et leurs longueurs est donnée par la valeur absolue des valeurs propres. La longueur maximale des axes nous indique le rayon de la boule Euclidienne contenant cette ellipse. On en déduit donc que $AB_2^n\subseteq \Vert A\Vert B_2^n$ où $\Vert A\Vert$ correspond à la plus grande (en valeur absolue) valeur propre (voir Figure 0.1).

Figure 0.1. La boule unité Euclidienne en noir, transformée en une ellipse contenue dans la boule Euclidienne (en rouge) dont le rayon est la longueur maximale des axes de l'ellipse. C'est la norme spectrale de la transformation.

Dans cette interprétation, nous avons regardé l'opérateur $A: E=(R^n, \Vert \cdot \Vert_2)\to F=(R^n, \Vert\cdot\Vert_2)$ et on a essayé de comprendre comment $A$ transporte la structure normée de $E$ dans $F$, et ainsi
$$
\Vert A\Vert=\Vert A\Vert_{2\to 2}= \sup_{x\in B_2^n} \Vert Ax\Vert_2.
$$
On pourrait évidemment regarder l'action de $A$ sur d'autres espaces normés, par exemple $A: (R^n, \Vert \cdot\Vert_1)\to (R^n, \Vert \cdot\Vert_2)$ où $\Vert x\Vert_1= \vert x_1\vert+\ldots+\vert x_n\vert$. Si on note $B_1^n$ la boule unité de $\Vert \cdot\Vert_1$, il s'agit de comprendre la position de $AB_1^n$ par rapport à $B_2^n$. Puisque $B_1^n={\rm conv}\{\pm e_i, i\leq n\}$ est l'enveloppe convexe des vecteurs de la base canonique qu'on a noté $\{e_i, i\leq n\}$, alors on a
$$
AB_1^n= {\rm conv}\{\pm Ae_i, i\leq n\} \subseteq \Vert A\Vert_{1\to 2}\, B_2^n,
$$
où $\Vert A\Vert_{1\to 2}= \max_{i\leq n} \Vert Ae_i\Vert_2$ est le maximum des normes Euclidienne des lignes/colonnes de $A$ (voir Figure 0.2).
 

Figure 0.2. La boule unité de $\Vert\cdot\Vert_1$ en noir, dont la transformée en bleu est contenue dans la boule Euclidienne (en rouge) dont le diamètre est la longueur maximale des diagonales du parallélépipède obtenu. C'est la norme $\Vert \cdot\Vert_{1\to 2}$ de la transformation.

Puisque $B_1^n\subseteq B_2^n$, alors on voit que
$$
\Vert A\Vert_{1\to 2}= \max_{i\leq n} \Vert Ae_i\Vert_2\leq \Vert A\Vert.
$$
D'autre part, puisque $B_2^n \subseteq \sqrt{n} B_1^n$, alors
$$
\Vert A\Vert\leq \sqrt{n}\Vert A\Vert_{1\to 2}.
$$
Ces inégalités ont une signification assez pertinente : elles permettent de relier la plus grande valeur propre qui est une fonction assez compliquée des entrées de la matrice à une quantité explicite en terme de ces dernières. A priori, c'est le mieux que l'on puisse faire en toute généralité.
Cependant, ce qu'on verra par la suite, est que pour certaines matrices aléatoires, un phénomène spécial se passe et la plus grande valeur propre peut être directement "déterminée'' par la plus grande norme Euclidienne des lignes. En d'autres termes, pour connaître la "déformation maximale'' produite par une telle matrice aléatoire, il suffit de regarder la distorsion causée aux vecteurs de la base canonique.

Commençons à présent à nous placer dans un cadre probabiliste. Pour tout $n\in N$, on considère $G_n$ une matrice $n\times n$ symétrique dont les entrées $g_{ij}$ sur et au-dessus de la diagonale sont des variables Gaussiennes centrées, indépendantes et de variance $1$. On notera également $G_\infty$ la matrice correspondante de taille infinie et on étudie donc l'opérateur $G_\infty: \ell_2\to \ell_2$ où $\ell_2=\{x=(x_i)_{i\in N}:\, \sum_{i\in N} x_i^2<\infty\}$. Une question assez naturelle et basique est de se demander si $G_\infty$ définit un opérateur borné i.e. si
$$
\Vert G_\infty\Vert:=\sup_{n\in N} \Vert G_n\Vert<\infty.
$$
Evidemment, ceci est loin d'être vrai puisque
$$
\Vert G_n\Vert\geq \Vert G_n\Vert_{1\to 2}= \max_{i\leq n} \Vert G_n e_i\Vert_2,
$$
et ce dernier tend p.s. vers l'infini. Il est donc clair qu'afin de définir un opérateur borné à travers une matrice Gaussienne, il faudrait absolument avoir une certaine décroissance des variances des entrées. Plaçons-nous dans un cadre général et considérons pour tout $n\in N$ une matrice symétrique $B_n$ de taille $n\times n$ à entrées positives et notons comme avant $B_\infty$ pour la matrice infinie. Les entrées de $B_\infty$ joueront le rôle d'un profil de variance pour les variables Gaussiennes. On considère pour cela $X_n= B_n\bullet G_n$ la matrice symétrique de taille $n\times n$ dont les entrées sont données par $b_{ij}g_{ij}$ i.e. des variables Gaussiennes indépendantes centrées de variance $b_{ij}^2$, et on note $X_\infty$ comme avant. La question qui se pose est la suivante
$$
\textit{Sous quelles conditions sur $B_\infty$, l'opérateur $X_\infty$ est-il borné sur $\ell_2$?}
$$
Considérer des matrices inhomogènes (i.e. dont les entrées ne sont pas identiquement distribuées) est assez naturel en soi. En effet, l'exemple des  graphes aléatoires en est la parfaite illustration: le graphe est formé en décidant d'une manière aléatoire et indépendante de placer une arête entre deux sommets ou non. Le caractère inhomogène permet dans ce cas d'implémenter le fait que les probabilités de connexion entre les sommets varient en fonction des sommets considérés, ce qui est assez intuitif.

Notre résultat principal dans [1] répond entre autre à la question posé ci-dessus en affirmant ce qui suit.

Théorème 1. Soit $X_{\infty}=(X_{ij})_{i,j\in N}$ une matrice symétrique infinie avec $X_{ij}= b_{ij}g_{ij}$, où $b_{ij}\geq 0$ et $g_{ij}$ sont des variables Gaussiennes indépendantes centrées de variance $1$ pour tout $i\geq j$. On a la dichotomie suivante:

• Si $\max_i \sum_j b_{ij}^2<\infty$ et $\max_{ij} b_{ij}^*\sqrt{\log i} <\infty$, alors $X_{\infty}$ définit p.s. un opérateur borné sur $\ell_2$.
• Sinon, $X_{\infty}$ est non bornée p.s.,

où les $b_{ij}^*$ sont obtenus en permutant les lignes/colonnes de $B_{\infty}$ de telle sorte à avoir $\max_{j} b_{1j}^*\geq \max_{j}b_{2j}^*\geq \ldots$.

En outre, la preuve pour établir ce résultat fournit des informations structurelles sur les opérateurs bornés. Elle nous permet d'affirmer que tout opérateur Gaussien borné sur $\ell_2$ est (à permutation de lignes/colonnes près) composé d'un noyau dont l'épaisseur augmente (à vitesse polynomiale), mais contenant des variances qui décroissent à une vitesse logarithmique. En contraste, les variances en dehors de ce noyau décroissent bien plus vite à une vitesse polynomiale. Ceci indique que ces opérateurs sont essentiellement portés par leur noyau et ont leur "aléatoire'' (l'ordre de variance des entrées) plutôt concentrée dans la partie haute à gauche de la matrice (voir Figure 0.3).

Figure 0.3. Après permutation des lignes/colonnes, c'est la forme de l'opérateur borné à entrées Gaussiennes indépendantes. Un noyau où les variances décroissent lentement, alors qu'elles décroissent beaucoup plus rapidement en dehors. La largeur du noyau augmente à une vitesse polynomiale. Dans [1], nous prenons $s=\frac13$, $\kappa=\frac14$ et $\Gamma=\max_i\sqrt{\sum_j b_{ij}^2} + \max_{ij}b_{ij}^*\sqrt{\log i}$ dans les quantités ci-dessus.

Outre une formule explicite de la norme d'un opérateur Gaussien, nos résultats mettent la lumière sur un phénomène assez intéressant et très particulier aux matrices Gaussiennes. En effet, nous montrons l'énoncé suivant, qui explique entre autre le théorème précédent.

Théorème 2. Soit $n\in N$ et $(X_{ij})_{i,j\leq n}$ une matrice symétrique de taille $n\times n$ avec $X_{ij}= b_{ij}g_{ij}$, où $b_{ij}\geq 0$ et $g_{ij}$ sont des variables Gaussiennes indépendantes centrées de variance $1$ pour tout $i\geq j$. On a
$$
\mathbf{E}\, \Vert X\Vert_{1\to 2} \leq \mathbf{E}\, \Vert X\Vert\leq C\mathbf{E}\, \Vert X\Vert_{1\to 2},
$$
où $C$ est une constante universelle (qui ne dépend de rien). De plus, on a la formule explicite suivante
$$
\mathbf{E}\|X\|
    \asymp
    \max_i\sqrt{\sum_j b_{ij}^2} + \max_{ij}b_{ij}^*\sqrt{\log i}.
$$

La notation $x\asymp y$ signifie qu'il existe deux constantes $c,C$ tels que $cy\leq x\leq Cy$. Bien qu'énoncé en moyenne, le résultat précédent est plus précis et affirme que les variables aléatoires $\Vert X\Vert$ et $\Vert X\Vert_{1\to 2}$ ont des distributions comparables. Ceci est un fait assez remarquable et contraste avec le cas déterministe où l'action d'une matrice sur la boule unité de $\Vert \cdot\Vert_{1}$ n'implique pas en général des informations précises sur son action sur la boule Euclidienne. A l'opposé, ce qu'on affirme par le théorème précédent, est que l'action d'une matrice Gaussienne sur la boule Euclidienne est "entièrement'' déterminée par son action sur une boule plus petite qui est la boule unité de $\Vert \cdot\Vert_{1}$. Il s'avère que ce phénomène est particulier aux Gaussiennes (et pour certaines distributions à queues lourdes) et est loin d'être vrai en toute généralité pour n'importe quelle matrice aléatoire.

• 1La matrice est alors appelée "matrice d'adjacence" du graphe.
• 2Dans cette note, on considère seulement des matrices symétriques bien que tout est valable dans un cadre plus général.