Centrale Maths 1 MP 2018

î, % Mathématiques 1 O0

°.) , 1--l
--/ MP o
tnucnuns EENÏHHLE--SUPËLEE 4 heures Calculatrices autorisées N

Aplatz'ssement aléatoire d'un ensemble
de points en grande dimension

Notations
-- Dans tout le problème N, le et d désignent des entiers supérieurs ou égaux à 
deux.

-- Pour tous entiers naturels non nuls p et q, on note Mpfiq([R) l'ensemble des 
matrices a p lignes et q colonnes
à coefficients réels.

-- On note AT la transposée d'une matrice A.
-- Pour tous entiers naturels p et q, avec p < q, la notation [|p, q|| désigne l'ensemble {i EUR N | p g i < q}. -- Dans tout le problème on note ( Q, A, P) un espace probabilisé fini. Toutes les variables aléatoires considérées sont définies sur Q. -- Pour tout événement A de probabilité non nulle, et pour tout événement B, on note [PA(B) ou [P(B | A) la probabilité conditionnelle de B sachant A. -- Etant donnée une variable aléatoire Z à valeurs réelles, on note : (Z) son espérance. -- On dit qu'une variable aléatoire Z est une variable de Rademacher lorsque Z (Q) : {--1, 1} et -- De façon générale, si E est un espace euclidien, son produit scalaire et sa norme seront respectivement notés (. | > et |||.| Ces notations seront utilisées notamment pour Rd et Rk, munis 
de leurs structures euclidiennes
canoniques.

Problématique

On s'intéresse à la question suivante : étant donnés N 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 N vecteurs distincts vl, ..., 'UN 
dans [Rd. Pour tout réel 5 tel que 0 < 6 < 1, on dit qu'une application linéaire f : [Rd --> lR'" est une e--isométrie pour 
vl, ..., U N lorsque :

V(i,j) EUR ll, Nl2, (1-- EUR)llm- -- va| < ||f(w) -- f(w)|l < (1 + EUR>|lw -- 
vj|l
La question peut se reformuler ainsi :

-- Objectif
Pour quelles valeurs de k existe--t--il f : Rd --> [Rk qui soit une 
e--isométrie pour vl, ..., 'UN '?

On se propose d'établir le théorème suivant, démontré par William B. Johnson et 
J oram Lindenstrauss en 1984 :

Il existe une constante absolue e strictement positive telle que :

quels que soient N et d, entier naturels supérieurs ou égaux à 2 et quels que 
soient "1: , 'UN distincts
dans Rd, il suffit que

pour qu'il existe une e--isométrie f : Rd --> [Rk pour vl, , UN.

Les seules méthodes connues à ce jour pour démontrer ce théorème sont de nature 
probabiliste.

Dans la partie l, on établit des résultats préliminaires portant sur la 
convexité et les probabilités. La partie Il est
consacrée à la démonstration d'une inégalité de concentration, qui est utilisée 
dans la partie 111 où le théorème
de Johnson--Lindenstrauss est démontré.

2018-03--02 14:50:23 Page 1/6 («à BY--NC-SA

I Préliminaires

I.A + Projection sur un conveoee fermé
Soit E un espace euclidien.

Q 1. Soient a et b dans E. Montrer la relation suivante et en donner une 
interprétation géométrique :

la + b|l2 + la -- b|l2 : 2 (|IOE|l2 + |lb|l2)

, . . , . u + u'
Q 2. En dedu1re que s1 u, v et U' dans E ver1fient v # u" et ||u-- v|| : ||u -- 
v' || alors ||u -- 2 || < ||u -- v||. Q 3. Soient F un fermé non vide de E et u dans E. Montrer qu'il existe fu dans F tel que VwEF, |lu--v|l<|lu--wll Q 4. En déduire que si C est un convexe fermé non vide de E et u est un vecteur de E alors il existe un unique 1) dans C tel que ... e F. |u -- v| < |u -- ...| On dira que 1) est le projeté de u sur C et on notera d(u, C) : ||u -- v||. LB + Inégalité de Hälder pour l'espérance 1 1 Soient p et q deux réels strictement positifs tels que -- + -- : 1. P q Q 5. Montrer que, pour tous réels positifs a et b, ap bq ab g -- + -- P Q On pourra utiliser la concavité du logarithme. Q 6. En déduire que si X et Ysont deux variables aléatoires réelles sur l'espace probabilisé fini (Q, A, [P) alors "(IXYI) < "(IXIP)W '(lqu)l/q On pourra d'abord montrer ce résutat lorsque -(|X|p) : -(|Y|q) : 1. LG -- Espérance conditionnelle Soit X : Q _) B? une variable aléatoire à valeurs réelles. Pour tout événement A C Q de probabilité non nulle, l'espérance conditionnelle de X sachant A, notée - (X | A), est par définition le réel *(X|A)= î: Û°A(X=OE)'OE OEEX(Q) En d'autres termes, -(X | A) est l'espérance de X dans l'espace (Q, A, lPA). 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 A. Q 7. Soit (Al, ..., A...) un système complet d'événements de probabilités non nulles. Montrer que - = ÎP - Çî(X | A.>

i=1

I.D + Variables aléatoires à queue sous-gaussienne
Soit X : Q --> R une variable aléatoire réelle.
On suppose qu'il existe deux réels strictement positifs (1 et b tels que, pour 
tout réel positif t,

[P(|X| ; 15) < aexp(--bt2) Q 8. Montrer que +oo -(X2) =2 / t[P(|X| 2t)dt () On pourra noter X2(Q) : {y1, ...,yn} avec 0 < yl < y2 < < yn. 2018-03--02 14:50:23 Page 2/6 | @'3 (1 Q 9. Montrer que le moment d'ordre deux de X est inférieur ou égal à E' Soit 6 un réel tel que 0 < |5| g %. Q 10. Justifier que, pour tout réel t, [P(|X+ôl ? t) < [P(|Xl ? t-- |6|) Q 11. Montrer que, pour tout réel t, 2 1 2 --b(t-- |5|> < a-- 5bt Q 12. En déduire que pour tout réel t tel que t ; |5| on a 1 [P(|X + (?| 2 75) < a exp(a) exp (--äbt2>
Q 13. Justifier que l'inégalité précédente reste valable si 0 < t < |6 | II L'inéga1îté de concentration de Talagrand Soit E un espace euclidien de dimension n 2 1 muni d'une base orthonormée (el, ..., en). Soient el, , en : Q --> {--1, 1} des variables aléatoires de Rademacher 
indépendantes dans leur ensemble.

n
On pose X : EE,-e,.
7'=1

L'objectif de cette partie est de montrer, pour tout convexe fermé non vide 0 
de E,

U°(X EUR c>- » (exp (%d(X,C)?)) g 1 (11.1)

II.A -- Étude de deus: cas particuliers

Q 14. Traiter le cas où C est un convexe fermé de E ne rencontrant pas X (Q)

On suppose, dans la suite de cette sous--partie 11.A uniquement, que C est un 
convexe fermé de E qui rencontre
X(Q) en un seul vecteur u.

1
Q 15. Montrer que ÂdE'

n nf1

7TI
E 332--61-- l--> % 331--61-
i=1 i=1

nil
On pose X ' : 7r 0 X = E eiei. C'est une variable aléatoire à valeurs dans E'.
i=1

Pour t dans {--1, 1} on note

-- Ht l'hyperplan affine E' + ten ;

-- Ct : 7T(C fi Ht).

Q 19. Montrer, pour :C' E E' et 75 EUR {--1, 1}, que a:' E Ct (:> :C' +ten E C.
Q 20. Montrer que C +1 et CL1 sont des convexes fermés non vides de E'.

2018-03--02 14:50:23 Page 3/6 (GQ BY--NC-SA

Pour t dans { --1, l}, on note Y,, le projeté de X ' sur le convexe fermé non 
vide C,. C'est une variable aléatoire
à valeurs dans E'.

Q 21. Montrer que

1 1
[P(X EUR C) : îlP(X' EUR CH) + 5P(X' EUR 011)

II.D -- Une inégalité cruciale
Soit A un réel tel que 0 { À { 1.
Q 22. Montrer que

d(X1 0) < "(1 _ À)(î/sn + EURnen) + )'(st _ Enfin) _ X" 'n. Q 23. En déduire que d(Xa @" < 4À2 + ll(1 -- À)(st -- X') + À(stn -- X')ll2 puis que d(X7C)2 < 4À2 + (1 -- À)llY.n -- X'll2 + ÀllYfen -- X'll2 Ainsi, on a montré l'inégalité d(X, C)2 { 4À2 + (1 -- À)d(X', CE )2 + Àd(X', CLE )2 n n ILE * Espérances conditionnelles On note p+=[P(X'ECH) et pÿ:lP(X/EURCÿl) On va supposer, sans perte de généralité, que p + 2 pi. Q 24. Montrer que pi > 0.
Q 25. Montrer que pour tout A dans (0, 1]

-- (exp (êdZ) | e.. = --1) < exp (',) - ((exp (âd(XflCl)2))U . (exp (àd(X',C,l)2))À) Q 26. En déduire que - (exp (êd2)))w . ( (exp 
(%d(X', c.1>2)))À

Q 27. À l'aide de l'hypothèse de récurrence, justifier que

' (exp (âd(X,C)2) | En :1) { L

p+

Q 28. Déduire de ce qui précède que pour tout A dans (0, 1]

' (eXp (âd) < % (à +...) (AZ--2) (rtlH ' (pî)') II. F * Optimisation Q 29. On pose À : 1 -- &. Montrer que p+ ' (exp (%d(X,C)2)) < 2;+ (l +exp (ÿ) (1 -- A)") Q 30. Montrer que pour tout 93 EUR {0,11 OE2 2 +(oe--l)ln(l--oe) (x e C) - P(d(X, C) ; t) < exp (32) III Démonstration du théorème de Johnson-Lindenstrauss Dans cette partie on considère l'espace E : Mk,d([R) muni du produit scalaire défini par V(A,B) EUR E2, (A | B) : tr(AT - B) On notera |||| F la norme euclidienne associée. On rappelle que Rd et [R]" sont munis de leurs normes euclidiennes canoniques, notées indistinctement ||||. On identifie [Rd a Md71([R), de sorte qu'un vecteur quelconque x : (æ1,....,æd) de [Rd peut être identifié à la matrice colonne (acl æd)T. On fixe un vecteur (ul, ..., ud) dans [Rd, identifié comme ci--dessus a la matrice colonne (ul...ud)T de Md,1([R>)a
et tel que ||u|| : 1. On définit l'application

. Mk,d<[R) --> |?

9' Mi-->||Mw|l

Soit X : (eij) 1 0.
Q 36. Montrer que pour toute matrice JW dans Mk,d([R)

d(M,C) g(M)

III.B * Médianes
On dit qu'un réel m est une médiane de g(X ) lorsque

n>(g(X) ; m) 2% et n>(g(X) < m) ; Q 38. Justifier que g(X ) admet au moins une médiane. On pourra considérer la fonction G de [R dans [R telle que, pour tout réel t, G(t) : P(g(X) < t), et examiner l'ensemble G*1(|1/2,1|). Q 39. Déduire de ce qui précède que, pour tout réel strictement positif t 1 t) < 4exp (--ët2) \\/ P(|g -- ml

où m est une médiane de g(X )

2018-03--02 14:50:23 Page 5/6 (CÔ BY--NC-SA

Q 40. En déduire que ' <(g(X) -- m)2) < 32. Q 41. Montrer que ' (g(X)2) : k, et en déduire que - (g(X)) < \/Ë. Q 42. En déduire que (xÆ -- m)2 < - ((g(X) - m)2). III.C * Un lemme-clé Q 43. Montrer que, pour tout réel strictement positif t [P(|g(X) -- \/Ë| } 75) < 4exp(4) exp (--11--6t2) X 1 1 On pose Ak : --. Soient EUR dans ]0,1{ et 6 dans ]0,1/2{. On suppose que k: 2 160 M /5). \/Ë Q 44. Montrer que, pour tout vecteur unitaire u dans Rd : [P({||Ak-uu--iy>s) <5 III.D * Conclusion On conserve les notations et les hypothèses précédentes. Soient vl, UN des vecteurs distincts dans [Rd. Pour tout (i,j) EUR [[LN]]2 tel que i < j on note Eij l'événement (1--5)H"i _UjH < "Ale 'Ui_ Ak ' "j" < (1 + 5)""i _ "j" 45. Montrer que [P E -- < 5, Où Î dési ne l'événement contraire de E- -. 13 1] g 'L] Q 46. En déduire que [P ( fi Bij) } 1-- wé. igi