AnnalesÉcoles d'ingénieurs

Mines-Ponts MP 2015 — Maths 2

Norme d'une matrice aléatoire · 5 pages

PDF hébergé hors du site officiel — source : archive officielle (ZIP)

Le sujet établit une inégalité de concentration pour la norme d'opérateur d'une matrice aléatoire de taille $n$ à coefficients indépendants $\alpha$ -sous-gaussiens : $P(\|M\|_{\mathrm{op}} \geqslant 2r\sqrt{n}) \leqslant (25\, e^{-\gamma r^2})^n$ avec $\gamma = 1/(4\alpha^2)$ . Il étudie d'abord la norme d'opérateur (lien avec le spectre pour une matrice symétrique, comparaison avec la norme de Frobenius), puis les variables sous-gaussiennes (lemme de Hoeffding, borne de Chernoff, inégalité d'Orlicz), enfin les recouvrements de la sphère unité par des boules ( $\varepsilon$ -réseaux de cardinal au plus $5^n$ par un argument de volume).

Le sujet, partie par partie

Partie A — Norme d'opérateur d'une matrice p. 2–3

Normes subordonnées et applications linéaires continues · Théorème spectral · Compacité · Matrices remarquables · Dénombrement et combinatoire — norme d'opérateur, sphère unité compacte, matrice symétrique, rayon spectral, matrice dont tous les coefficients valent 1, norme de Frobenius, rang 1

Partie B — Variables aléatoires sous-gaussiennes p. 3–4

Inégalités de concentration · Espérance, variance, moments · Fonctions convexes · Séries entières · Inégalités de Markov et de Bienaymé-Tchebychev · Fonction zêta de Riemann — variable sous-gaussienne, lemme de Hoeffding, borne de Chernoff, inégalité de convexité, espérance et queue de distribution, inégalité d'Orlicz

Partie C — Recouvrements de la sphère p. 4–5

Compacité · Topologie, compacité, connexité · Espaces vectoriels normés — recouvrement par des boules, $\varepsilon$ -réseau, Bolzano-Weierstrass, argument de volume, partie $\varepsilon$ -séparée

Partie D — Norme d'une matrice aléatoire p. 5

Matrices et graphes aléatoires · Inégalités de concentration · Normes subordonnées et applications linéaires continues · Couples et sommes de variables aléatoires — matrice aléatoire, norme d'opérateur, coefficients indépendants sous-gaussiens, borne de l'union, $\varepsilon$ -réseau de la sphère