2018-03-02 14:50:23 Page 1/6 2018 Mathématiques 1 MP 4 heures Calculatrices autorisées Aplatissement aléatoire d’un ensemble de points en grande dimension Notations — Dans tout le problème 𝑁, 𝑘 et 𝑑 désignent des entiers supérieurs ou égaux à deux. — Pour tous entiers naturels non nuls 𝑝 et 𝑞, on note ℳ𝑝,𝑞(ℝ) l’ensemble des matrices à 𝑝 lignes et 𝑞 colonnes à coefficients réels. — On note 𝐴⊤ la transposée d’une matrice 𝐴. — Pour tous entiers naturels 𝑝 et 𝑞, avec 𝑝 ⩽ 𝑞, la notation ⟦𝑝, 𝑞⟧ désigne l’ensemble {𝑖 ∈ ℕ | 𝑝 ⩽ 𝑖 ⩽ 𝑞}. — Dans tout le problème on note (Ω, 𝒜, ℙ) un espace probabilisé fini. Toutes les variables aléatoires considérées sont définies sur Ω. — Pour tout événement 𝐴 de probabilité non nulle, et pour tout événement 𝐵, on note ℙ𝐴(𝐵) ou ℙ(𝐵 | 𝐴) la probabilité conditionnelle de 𝐵 sachant 𝐴. — Étant donnée une variable aléatoire 𝑍 à valeurs réelles, on note 𝔼(𝑍) son espérance. — On dit qu’une variable aléatoire 𝑍 est une variable de Rademacher lorsque 𝑍(Ω) = {−1, 1} et ℙ(𝑍 = −1) = ℙ(𝑍 = 1) = 1 2 — De façon générale, si 𝐸 est un espace euclidien, son produit scalaire et sa norme seront respectivement notés ⟨⋅ | ⋅⟩ et ‖⋅‖. Ces notations seront utilisées notamment pour ℝ𝑑 et ℝ𝑘, munis de leurs structures euclidiennes canoniques. Problématique On s’intéresse à la question suivante : étant donnés 𝑁 points dans un espace euclidien de grande dimension, est-il possible de les envoyer linéairement dans un espace de petite dimension sans trop modifier les distances entre ces points ? Pour préciser cette question, considérons 𝑁 vecteurs distincts 𝑣1, …, 𝑣𝑁 dans ℝ𝑑. Pour tout réel 𝜀 tel que 0 < 𝜀 < 1, on dit qu’une application linéaire 𝑓 : ℝ𝑑 → ℝ𝑘 est une 𝜀-isométrie pour 𝑣1, …, 𝑣𝑁 lorsque : ∀(𝑖, 𝑗) ∈ ⟦1, 𝑁 ⟧2, (1 − 𝜀)‖𝑣𝑖 − 𝑣𝑗‖ ⩽ ‖𝑓(𝑣𝑖) − 𝑓(𝑣𝑗)‖ ⩽ (1 + 𝜀)‖𝑣𝑖 − 𝑣𝑗‖ La question peut se reformuler ainsi : Objectif Pour quelles valeurs de 𝑘 existe-t-il 𝑓 : ℝ𝑑 → ℝ𝑘 qui soit une 𝜀-isométrie pour 𝑣1, …, 𝑣𝑁 ? On se propose d’établir le théorème suivant, démontré par William B. Johnson et Joram Lindenstrauss en 1984 : Il existe une constante absolue 𝑐 strictement positive telle que : quels que soient 𝑁 et 𝑑, entier naturels supérieurs ou égaux à 2 et quels que soient 𝑣1, … , 𝑣𝑁 distincts dans ℝ𝑑, il suffit que 𝑘 ⩾ 𝑐 ln(𝑁 ) 𝜀2 pour qu’il existe une 𝜀-isométrie 𝑓 : ℝ𝑑 → ℝ𝑘 pour 𝑣1, … , 𝑣𝑁. Les seules méthodes connues à ce jour pour démontrer ce théorème sont de nature probabiliste. Dans la partie I, on établit des résultats préliminaires portant sur la convexité et les probabilités. La partie II est consacrée à la démonstration d’une inégalité de concentration, qui est utilisée dans la partie III où le théorème de Johnson-Lindenstrauss est démontré. -- 1 of 6 -- 2018-03-02 14:50:23 Page 2/6 I Préliminaires I.A – Projection sur un convexe fermé Soit 𝐸 un espace euclidien. Q 1. Soient 𝑎 et 𝑏 dans 𝐸. Montrer la relation suivante et en donner une interprétation géométrique : ‖𝑎 + 𝑏‖2 + ‖𝑎 − 𝑏‖2 = 2 (‖𝑎‖2 + ‖𝑏‖2) Q 2. En déduire que si 𝑢, 𝑣 et 𝑣′ dans 𝐸 vérifient 𝑣 ≠ 𝑣′ et ‖𝑢 − 𝑣‖ = ‖𝑢 − 𝑣′‖ alors ‖𝑢 − 𝑣 + 𝑣′ 2 ‖ < ‖𝑢 − 𝑣‖. Q 3. Soient 𝐹 un fermé non vide de 𝐸 et 𝑢 dans 𝐸. Montrer qu’il existe 𝑣 dans 𝐹 tel que ∀𝑤 ∈ 𝐹 , ‖𝑢 − 𝑣‖ ⩽ ‖𝑢 − 𝑤‖ Q 4. En déduire que si 𝐶 est un convexe fermé non vide de 𝐸 et 𝑢 est un vecteur de 𝐸 alors il existe un unique 𝑣 dans 𝐶 tel que ∀𝑤 ∈ 𝐹 , ‖𝑢 − 𝑣‖ ⩽ ‖𝑢 − 𝑤‖ On dira que 𝑣 est le projeté de 𝑢 sur 𝐶 et on notera 𝑑(𝑢, 𝐶) = ‖𝑢 − 𝑣‖. I.B – Inégalité de Hölder pour l’espérance Soient 𝑝 et 𝑞 deux réels strictement positifs tels que 1 𝑝 + 1 𝑞 = 1. Q 5. Montrer que, pour tous réels positifs 𝑎 et 𝑏, 𝑎𝑏 ⩽ 𝑎𝑝 𝑝 + 𝑏𝑞 𝑞 On pourra utiliser la concavité du logarithme. Q 6. En déduire que si 𝑋 et 𝑌 sont deux variables aléatoires réelles sur l’espace probabilisé fini (Ω, 𝒜, ℙ) alors 𝔼(|𝑋𝑌 |) ⩽ 𝔼(|𝑋|𝑝)1/𝑝 𝔼(|𝑌 |𝑞)1/𝑞 On pourra d’abord montrer ce résutat lorsque 𝔼(|𝑋|𝑝) = 𝔼(|𝑌 |𝑞) = 1. I.C – Espérance conditionnelle Soit 𝑋 : Ω → ℝ une variable aléatoire à valeurs réelles. Pour tout événement 𝐴 ⊂ Ω de probabilité non nulle, l’espérance conditionnelle de 𝑋 sachant 𝐴, notée 𝔼(𝑋 | 𝐴), est par définition le réel 𝔼(𝑋 | 𝐴) = ∑ 𝑥∈𝑋(Ω) ℙ𝐴(𝑋 = 𝑥) ⋅ 𝑥 En d’autres termes, 𝔼(𝑋 | 𝐴) est l’espérance de 𝑋 dans l’espace (Ω, 𝒜, ℙ𝐴). Les propriétés usuelles de linéarité et de positivité de l’espérance, qu’on ne demande pas de redémontrer, sont ainsi valables pour l’espérance conditionnelle sachant 𝐴. Q 7. Soit (𝐴1, …, 𝐴𝑚) un système complet d’événements de probabilités non nulles. Montrer que 𝔼(𝑋) = 𝑚 ∑ 𝑖=1 ℙ(𝐴𝑖) ⋅ 𝔼(𝑋 | 𝐴𝑖) I.D – Variables aléatoires à queue sous-gaussienne Soit 𝑋 : Ω → ℝ une variable aléatoire réelle. On suppose qu’il existe deux réels strictement positifs 𝑎 et 𝑏 tels que, pour tout réel positif 𝑡, ℙ(|𝑋| ⩾ 𝑡) ⩽ 𝑎 exp (−𝑏𝑡2) Q 8. Montrer que 𝔼(𝑋2) = 2 +∞ ∫ 0 𝑡ℙ(|𝑋| ⩾ 𝑡) d𝑡 On pourra noter 𝑋2(Ω) = {𝑦1, …, 𝑦𝑛} avec 0 ⩽ 𝑦1 < 𝑦2 < ⋯ < 𝑦𝑛. -- 2 of 6 -- 2018-03-02 14:50:23 Page 3/6 Q 9. Montrer que le moment d’ordre deux de 𝑋 est inférieur ou égal à 𝑎 𝑏 . Soit 𝛿 un réel tel que 0 ⩽ |𝛿| ⩽ √ 𝑎 𝑏 . Q 10. Justifier que, pour tout réel 𝑡, ℙ(|𝑋 + 𝛿| ⩾ 𝑡) ⩽ ℙ(|𝑋| ⩾ 𝑡 − |𝛿|) Q 11. Montrer que, pour tout réel 𝑡, −𝑏(𝑡 − |𝛿|)2 ⩽ 𝑎 − 1 2 𝑏𝑡2 Q 12. En déduire que pour tout réel 𝑡 tel que 𝑡 ⩾ |𝛿| on a ℙ(|𝑋 + 𝛿| ⩾ 𝑡) ⩽ 𝑎 exp(𝑎) exp (− 1 2 𝑏𝑡2) Q 13. Justifier que l’inégalité précédente reste valable si 0 ⩽ 𝑡 < |𝛿|. II L’inégalité de concentration de Talagrand Soit 𝐸 un espace euclidien de dimension 𝑛 ⩾ 1 muni d’une base orthonormée (𝑒1, …, 𝑒𝑛). Soient 𝜀1, … , 𝜀𝑛 : Ω → {−1, 1} des variables aléatoires de Rademacher indépendantes dans leur ensemble. On pose 𝑋 = 𝑛 ∑ 𝑖=1 𝜀𝑖𝑒𝑖. L’objectif de cette partie est de montrer, pour tout convexe fermé non vide 𝐶 de 𝐸, ℙ(𝑋 ∈ 𝐶) ⋅ 𝔼 (exp ( 1 8 𝑑(𝑋, 𝐶)2)) ⩽ 1 (II.1) II.A – Étude de deux cas particuliers Q 14. Traiter le cas où 𝐶 est un convexe fermé de 𝐸 ne rencontrant pas 𝑋(Ω). On suppose, dans la suite de cette sous-partie II.A uniquement, que 𝐶 est un convexe fermé de 𝐸 qui rencontre 𝑋(Ω) en un seul vecteur 𝑢. Q 15. Montrer que 1 4 𝑑(𝑋, 𝑢)2 suit une loi binomiale de paramètres 𝑛 et 1/2. Q 16. En déduire l’espérance de exp ( 1 8 𝑑(𝑋, 𝑢)2) et montrer qu’elle est inférieure ou égale à 2𝑛. Q 17. Justifier que 𝑑(𝑋, 𝐶) ⩽ 𝑑(𝑋, 𝑢) et en déduire l’inégalité (II.1) dans ce cas. II.B – Initialisation On suppose désormais que 𝐶 est un convexe fermé de 𝐸 tel que 𝐶 ∩ 𝑋(Ω) contient au moins deux éléments. Quitte à permuter les vecteurs de la base, on peut supposer que ces deux vecteurs diffèrent par leur dernière coordonnée. On se propose de démontrer l’inégalité (II.1) par récurrence sur la dimension 𝑛 de 𝐸. Q 18. Traiter le cas 𝑛 = 1. II.C – Propriétés de 𝑪+𝟏 et 𝑪−𝟏 Soit 𝑛 un entier tel que 𝑛 ⩾ 2. On suppose à présent que (II.1) est vérifiée au rang 𝑛 − 1. On note 𝐸′ = Vect(𝑒1, …, 𝑒𝑛−1) et 𝜋 la projection orthogonale sur 𝐸′ 𝜋 : ∣ ∣ ∣ ∣ 𝐸 → 𝐸′ 𝑛 ∑ 𝑖=1 𝑥𝑖𝑒𝑖 ↦ 𝑛−1 ∑ 𝑖=1 𝑥𝑖𝑒𝑖 On pose 𝑋′ = 𝜋 ∘ 𝑋 = 𝑛−1 ∑ 𝑖=1 𝜀𝑖𝑒𝑖. C’est une variable aléatoire à valeurs dans 𝐸′. Pour 𝑡 dans {−1, 1} on note — 𝐻𝑡 l’hyperplan affine 𝐸′ + 𝑡𝑒𝑛 ; — 𝐶𝑡 = 𝜋(𝐶 ∩ 𝐻𝑡). Q 19. Montrer, pour 𝑥′ ∈ 𝐸′ et 𝑡 ∈ {−1, 1}, que 𝑥′ ∈ 𝐶𝑡 ⟺ 𝑥′ + 𝑡𝑒𝑛 ∈ 𝐶. Q 20. Montrer que 𝐶+1 et 𝐶−1 sont des convexes fermés non vides de 𝐸′. -- 3 of 6 -- 2018-03-02 14:50:23 Page 4/6 Pour 𝑡 dans {−1, 1}, on note 𝑌𝑡 le projeté de 𝑋′ sur le convexe fermé non vide 𝐶𝑡. C’est une variable aléatoire à valeurs dans 𝐸′. Q 21. Montrer que ℙ(𝑋 ∈ 𝐶) = 1 2 ℙ(𝑋′ ∈ 𝐶+1) + 1 2 ℙ(𝑋′ ∈ 𝐶−1) II.D – Une inégalité cruciale Soit 𝜆 un réel tel que 0 ⩽ 𝜆 ⩽ 1. Q 22. Montrer que 𝑑(𝑋, 𝐶) ⩽ ‖(1 − 𝜆)(𝑌𝜀𝑛 + 𝜀𝑛𝑒𝑛) + 𝜆(𝑌−𝜀𝑛 − 𝜀𝑛𝑒𝑛) − 𝑋‖ Q 23. En déduire que 𝑑(𝑋, 𝐶)2 ⩽ 4𝜆2 + ‖(1 − 𝜆)(𝑌𝜀𝑛 − 𝑋′) + 𝜆(𝑌−𝜀𝑛 − 𝑋′)‖2 puis que 𝑑(𝑋, 𝐶)2 ⩽ 4𝜆2 + (1 − 𝜆)‖𝑌𝜀𝑛 − 𝑋′‖2 + 𝜆‖𝑌−𝜀𝑛 − 𝑋′‖2 Ainsi, on a montré l’inégalité 𝑑(𝑋, 𝐶)2 ⩽ 4𝜆2 + (1 − 𝜆)𝑑(𝑋′, 𝐶𝜀𝑛 )2 + 𝜆𝑑(𝑋′, 𝐶−𝜀𝑛 )2 II.E – Espérances conditionnelles On note 𝑝+ = ℙ(𝑋′ ∈ 𝐶+1) et 𝑝− = ℙ(𝑋′ ∈ 𝐶−1) On va supposer, sans perte de généralité, que 𝑝+ ⩾ 𝑝−. Q 24. Montrer que 𝑝− > 0. Q 25. Montrer que pour tout 𝜆 dans [0, 1] 𝔼 (exp ( 1 8 𝑑(𝑋, 𝐶)2) | 𝜀𝑛 = −1) ⩽ exp ( 𝜆2 2 ) 𝔼 ((exp ( 1 8 𝑑(𝑋′, 𝐶−1)2)) 1−𝜆 ⋅ (exp ( 1 8 𝑑(𝑋′, 𝐶+1)2)) 𝜆 ) Q 26. En déduire que 𝔼 (exp ( 1 8 𝑑(𝑋, 𝐶)2) | 𝜀𝑛 = −1) ⩽ exp ( 𝜆2 2 ) (𝔼 (exp ( 1 8 𝑑(𝑋′, 𝐶−1)2))) 1−𝜆 ⋅ (𝔼 (exp ( 1 8 𝑑(𝑋′, 𝐶+1)2))) 𝜆 Q 27. À l’aide de l’hypothèse de récurrence, justifier que 𝔼 (exp ( 1 8 𝑑(𝑋, 𝐶)2) | 𝜀𝑛 = 1) ⩽ 1 𝑝+ Q 28. Déduire de ce qui précède que pour tout 𝜆 dans [0, 1] 𝔼 (exp ( 1 8 𝑑(𝑋, 𝐶)2)) ⩽ 1 2 ( 1 𝑝+ + exp ( 𝜆2 2 ) 1 (𝑝−)1−𝜆 ⋅ 1 (𝑝+)𝜆 ) II.F – Optimisation Q 29. On pose 𝜆 = 1 − 𝑝− 𝑝+ . Montrer que 𝔼 (exp ( 1 8 𝑑(𝑋, 𝐶)2)) ⩽ 1 2𝑝+ (1 + exp ( 𝜆2 2 ) (1 − 𝜆)𝜆−1) Q 30. Montrer que pour tout 𝑥 ∈ [0, 1[ 𝑥2 2 + (𝑥 − 1) ln(1 − 𝑥) ⩽ ln(2 + 𝑥) − ln(2 − 𝑥) On pourra faire une étude de fonction. -- 4 of 6 -- 2018-03-02 14:50:23 Page 5/6 Q 31. En déduire que pour tout 𝑥 ∈ [0, 1[ 1 + exp ( 𝑥2 2 ) (1 − 𝑥)𝑥−1 ⩽ 4 2 − 𝑥 Q 32. Terminer la démonstration de l’inégalité (II.1). II.G – Inégalité de Talagrand Q 33. En déduire l’inégalité de Talagrand : Pour tout 𝐶 convexe fermé non vide de 𝐸 et pour tout réel 𝑡 strictement positif ℙ(𝑋 ∈ 𝐶) ⋅ ℙ(𝑑(𝑋, 𝐶) ⩾ 𝑡) ⩽ exp (− 𝑡2 8 ) III Démonstration du théorème de Johnson-Lindenstrauss Dans cette partie on considère l’espace 𝐸 = ℳ𝑘,𝑑(ℝ) muni du produit scalaire défini par ∀(𝐴, 𝐵) ∈ 𝐸2, ⟨𝐴 | 𝐵⟩ = tr(𝐴⊤ ⋅ 𝐵) On notera ‖⋅‖𝐹 la norme euclidienne associée. On rappelle que ℝ𝑑 et ℝ𝑘 sont munis de leurs normes euclidiennes canoniques, notées indistinctement ‖⋅‖. On identifie ℝ𝑑 à ℳ𝑑,1(ℝ), de sorte qu’un vecteur quelconque 𝑥 = (𝑥1, …, 𝑥𝑑) de ℝ𝑑 peut être identifié à la matrice colonne (𝑥1 … 𝑥𝑑)⊤. On fixe un vecteur (𝑢1, …, 𝑢𝑑) dans ℝ𝑑, identifié comme ci-dessus à la matrice colonne (𝑢1…𝑢𝑑)⊤ de ℳ𝑑,1(ℝ)), et tel que ‖𝑢‖ = 1. On définit l’application 𝑔 : ∣ ℳ𝑘,𝑑(ℝ) → ℝ 𝑀 ↦ ‖𝑀 ⋅ 𝑢‖ Soit 𝑋 = (𝜀𝑖𝑗)1⩽𝑖⩽𝑘, 1⩽𝑗⩽𝑑 une variable aléatoire à valeurs dans ℳ𝑘,𝑑(ℝ), dont les coefficients 𝜀𝑖𝑗 sont des variables aléatoires de Rademacher indépendantes dans leur ensemble. III.A – Une inégalité de concentration Q 34. Montrer que 𝐶 = {𝑀 ∈ ℳ𝑘,𝑑(ℝ) | 𝑔(𝑀) ⩽ 𝑟} est une partie convexe et fermée de ℳ𝑘,𝑑(ℝ). Q 35. Montrer que pour toute matrice 𝑀 dans ℳ𝑘,𝑑(ℝ) ‖𝑀 ⋅ 𝑢‖ ⩽ ‖𝑀‖𝐹 Soient 𝑟 et 𝑡 deux réels, avec 𝑡 > 0. Q 36. Montrer que pour toute matrice 𝑀 dans ℳ𝑘,𝑑(ℝ) 𝑑(𝑀, 𝐶) < 𝑡 ⟹ 𝑔(𝑀) < 𝑟 + 𝑡 Q 37. En déduire que ℙ(𝑔(𝑋) ⩽ 𝑟) ⋅ ℙ(𝑔(𝑋) ⩾ 𝑟 + 𝑡) ⩽ exp (− 1 8 𝑡2) III.B – Médianes On dit qu’un réel 𝑚 est une médiane de 𝑔(𝑋) lorsque ℙ(𝑔(𝑋) ⩾ 𝑚) ⩾ 1 2 et ℙ(𝑔(𝑋) ⩽ 𝑚) ⩾ 1 2 Q 38. Justifier que 𝑔(𝑋) admet au moins une médiane. On pourra considérer la fonction 𝐺 de ℝ dans ℝ telle que, pour tout réel 𝑡, 𝐺(𝑡) = ℙ(𝑔(𝑋) ⩽ 𝑡), et examiner l’ensemble 𝐺−1([1/2, 1]). Q 39. Déduire de ce qui précède que, pour tout réel strictement positif 𝑡 ℙ(|𝑔(𝑋) − 𝑚| ⩾ 𝑡) ⩽ 4 exp (− 1 8 𝑡2) où 𝑚 est une médiane de 𝑔(𝑋). -- 5 of 6 -- 2018-03-02 14:50:23 Page 6/6 Q 40. En déduire que 𝔼 ((𝑔(𝑋) − 𝑚)2) ⩽ 32. Q 41. Montrer que 𝔼 (𝑔(𝑋)2) = 𝑘, et en déduire que 𝔼(𝑔(𝑋)) ⩽ √𝑘. Q 42. En déduire que (√𝑘 − 𝑚)2 ⩽ 𝔼 ((𝑔(𝑋) − 𝑚)2). III.C – Un lemme-clé Q 43. Montrer que, pour tout réel strictement positif 𝑡 ℙ(|𝑔(𝑋) − √𝑘| ⩾ 𝑡) ⩽ 4 exp(4) exp (− 1 16 𝑡2) On pose 𝐴𝑘 = 𝑋 √𝑘 . Soient 𝜀 dans ]0, 1[ et 𝛿 dans ]0, 1/2[. On suppose que 𝑘 ⩾ 160 ln(1/𝛿) 𝜀2 . Q 44. Montrer que, pour tout vecteur unitaire 𝑢 dans ℝ𝑑 : ℙ(∣‖𝐴𝑘 ⋅ 𝑢‖ − 1∣ > 𝜀) < 𝛿 III.D – Conclusion On conserve les notations et les hypothèses précédentes. Soient 𝑣1, …, 𝑣𝑁 des vecteurs distincts dans ℝ𝑑. Pour tout (𝑖, 𝑗) ∈ ⟦1, 𝑁 ⟧2 tel que 𝑖 < 𝑗 on note 𝐸𝑖𝑗 l’événement (1 − 𝜀)‖𝑣𝑖 − 𝑣𝑗‖ ⩽ ‖𝐴𝑘 ⋅ 𝑣𝑖 − 𝐴𝑘 ⋅ 𝑣𝑗‖ ⩽ (1 + 𝜀)‖𝑣𝑖 − 𝑣𝑗‖ Q 45. Montrer que ℙ(𝐸𝑖𝑗) < 𝛿, où 𝐸𝑖𝑗 désigne l’événement contraire de 𝐸𝑖𝑗. Q 46. En déduire que ℙ ( ⋂ 1⩽𝑖<𝑗⩽𝑁 𝐸𝑖𝑗) ⩾ 1 − 𝑁 (𝑁 − 1) 2 𝛿. Q 47. En déduire le théorème de Johnson et Lindenstrauss. • • • FIN • • • -- 6 of 6 --