AnnalesÉcoles d'ingénieurs

Centrale-Supélec MP 2018 — Maths 1

Aplatissement aléatoire d'un ensemble de points en grande dimension · 6 pages

Le sujet démontre le théorème de Johnson-Lindenstrauss : $N$ points de $\mathbb{R}^d$ peuvent être envoyés linéairement dans $\mathbb{R}^k$ avec $k \geqslant c \ln(N)/\varepsilon^2$ en préservant les distances à un facteur $1 \pm \varepsilon$ près. Après des préliminaires (projection sur un convexe fermé, inégalité de Hölder pour l'espérance, espérance conditionnelle, variables à queue sous-gaussienne), il établit par récurrence sur la dimension l'inégalité de concentration de Talagrand pour un vecteur de variables de Rademacher, puis l'applique à la norme $\|Mu\|$ d'une matrice aléatoire de Rademacher via une médiane, et conclut par une borne de réunion.

Le sujet, partie par partie

Notations et Partie I — Préliminaires p. 1–3

Ensembles convexes · Inégalités de Hölder et de Minkowski · Espérance, variance, moments · Inégalités de concentration · Probabilités totales et formule de Bayes · Compacité · Espaces préhilbertiens et euclidiens — identité du parallélogramme, projection sur un convexe fermé, inégalité de Young, inégalité de Hölder, espérance conditionnelle, variable sous-gaussienne

Partie II — L'inégalité de concentration de Talagrand p. 3–5

Inégalités de concentration · Ensembles convexes · Espérance, variance, moments · Lois de Bernoulli et binomiale · Inégalités de Hölder et de Minkowski · Probabilités totales et formule de Bayes · Fonctions convexes — inégalité de Talagrand, variables de Rademacher, distance à un convexe, récurrence sur la dimension, espérance conditionnelle

Partie III — Démonstration du théorème de Johnson-Lindenstrauss p. 5–6

Inégalités de concentration · Matrices et graphes aléatoires · Espérance, variance, moments · Espaces préhilbertiens et euclidiens · Ensembles convexes · Espaces probabilisés — théorème de Johnson-Lindenstrauss, matrice aléatoire de Rademacher, médiane, norme de Frobenius, réduction de dimension, borne de la réunion

Dans l'édifice

Théorème de Hahn-Banach Les espaces L¹ et L² et le théorème de Riesz-Fischer Espérance, variance et inégalités Moments exponentiels et inégalité de Hoeffding Indépendance d'événements et de tribus Compacité Espaces de Hilbert et théorème de projection Théorème de représentation de Riesz Variables aléatoires, lois, fonctions de répartition Dérivabilité Espaces probabilisés et probabilités conditionnelles