J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Centrale Mathématiques 1 MP 2018

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Algèbre bilinéaire et espaces euclidiensProbabilités finies, discrètes et dénombrementFonctions (limites, continuité, dérivabilité, intégration)GéométrieIntégrales généralisées
Logo centrale
🔗 Explorer
Banque
Centrale
Année
2018
Filière
MP
Matière
Maths
Centrale MPCentrale 2018MP MathsMaths 2018
2025_08_29_c294cd62f8ea0ee7e2efg

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 et
  • 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 dans . Pour tout réel tel que , on dit qu'une application linéaire est une -isométrie pour lorsque:
La question peut se reformuler ainsi :
    Objectif
Pour quelles valeurs de k existe-t-il f: }\mp@subsup{\mathbb{R}}{}{d}->\mp@subsup{\mathbb{R}}{}{k}\mathrm{ qui soit une }\varepsilon\mathrm{ -isométrie pour }\mp@subsup{v}{1}{},\ldots,\mp@subsup{v}{N}{}\mathrm{ ?
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 distincts dans , il suffit que
pour qu'il existe une -isométrie pour .
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é.

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 :
Q 2. En déduire que si et dans vérifient et alors .
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 .
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
On pourra d'abord montrer ce résutat lorsque .

I. 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 un système complet d'événements de probabilités non nulles. Montrer que

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 ,
Q 8. Montrer que
On pourra noter avec .
Q 9. Montrer que le moment d'ordre deux de est inférieur ou égal à .
Soit un réel tel que .
Q 10. Justifier que, pour tout réel ,
Q 11. Montrer que, pour tout réel ,
Q 12. En déduire que pour tout réel tel que on a
Q 13. Justifier que l'inégalité précédente reste valable si .

II L'inégalité de concentration de Talagrand

Soit un espace euclidien de dimension muni d'une base orthonormée ( ).
Soient des variables aléatoires de Rademacher indépendantes dans leur ensemble.
On pose .
L'objectif de cette partie est de montrer, pour tout convexe fermé non vide de ,

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 suit une loi binomiale de paramètres et .
Q 16. En déduire l'espérance de et montrer qu'elle est inférieure ou égale à .
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 .

II.C - Propriétés de et

Soit un entier tel que . On suppose à présent que (II.1) est vérifiée au rang .
On note et la projection orthogonale sur
On pose . C'est une variable aléatoire à valeurs dans .
Pour dans on note
  • l'hyperplan affine ;
  • .
Q 19. Montrer, pour et , que .
Q 20. Montrer que et sont des convexes fermés non vides de .
Pour dans , on note le projeté de sur le convexe fermé non vide . C'est une variable aléatoire à valeurs dans .
Q 21. Montrer que

II.D - Une inégalité cruciale

Soit un réel tel que .
Q 22. Montrer que
Q 23. En déduire que
puis que
Ainsi, on a montré l'inégalité

II.E - Espérances conditionnelles

On note
On va supposer, sans perte de généralité, que .
Q 24. Montrer que .
Q 25. Montrer que pour tout dans
Q 26. En déduire que
Q 27. À l'aide de l'hypothèse de récurrence, justifier que
Q 28. Déduire de ce qui précède que pour tout dans

II.F - Optimisation

Q 29. On pose . Montrer que
Q 30. Montrer que pour tout
On pourra faire une étude de fonction.
Q 31. En déduire que pour tout
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

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
On notera la norme euclidienne associée.
On rappelle que et sont munis de leurs normes euclidiennes canoniques, notées indistinctement .
On identifie à , de sorte qu'un vecteur quelconque de peut être identifié à la matrice colonne .
On fixe un vecteur ( ) dans , identifié comme ci-dessus à la matrice colonne ( de ), et tel que . On définit l'application
Soit 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 .
Q 36. Montrer que pour toute matrice dans
Q 37. En déduire que

III.B - Médianes

On dit qu'un réel est une médiane de lorsque
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 .
Q 39. Déduire de ce qui précède que, pour tout réel strictement positif
où est une médiane de .
Q 40. En déduire que .
Q 41. Montrer que , et en déduire que .
Q 42. En déduire que .

III.C - Un lemme-clé

Q 43. Montrer que, pour tout réel strictement positif
On pose . Soient dans et dans . On suppose que .
Q 44. Montrer que, pour tout vecteur unitaire dans :

III.D - Conclusion

On conserve les notations et les hypothèses précédentes. Soient des vecteurs distincts dans . Pour tout tel que on note l'événement
Q 45. Montrer que , où désigne l'événement contraire de .
Q 46. En déduire que .
Q 47. En déduire le théorème de Johnson et Lindenstrauss.
Centrale Mathématiques 1 MP 2018 - Version Web LaTeX | WikiPrépa | WikiPrépa