Random Euclidean embeddings in spaces of bounded volume ratio

Litvak, Alexander; Pajor, Alain; Rudelson, Mark; Tomczak-Jaegermann, Nicole; Vershynin, Roman

doi:10.1016/j.crma.2004.04.019

Functional Analysis/Probability Theory

Random Euclidean embeddings in spaces of bounded volume ratio
[Plongements aléatoires de l'espace euclidien dans un espace à volume ratio borné]

Présenté par : Gilles Pisier

Litvak, Alexander ¹ ; Pajor, Alain ² ; Rudelson, Mark ³ ; Tomczak-Jaegermann, Nicole ¹ ; Vershynin, Roman ⁴

¹ Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
² Équipe d'analyse et mathématiques appliquées, université de Marne-la-Vallée, 5, boulevard Descartes, Champs sur Marne, 77454 Marne-la-Vallée cedex 2, France
³ Department of Mathematics, University of Missouri, Columbia, MO 65211, USA
⁴ Department of Mathematics, University of California, Davis, CA 95616, USA

Comptes Rendus. Mathématique, Tome 339 (2004) no. 1, pp. 33-38.

Résumé
Abstract

Soit $(ℝ^{N}, ∥ \cdot ∥)$ l'espace $ℝ^{N}$ muni d'une norme ‖·‖ dont la boule unité est à volume ratio borné par rapport à la boule unité euclidienne. On montre qu'une matrice aléatoire Γ, de taille N×n (N>n), dont les coefficients sont des variables aléatoires indépendantes, vérifiant certaines hypothèses de moments, réalise avec une grande probabilité, un bon isomorphisme de l'espace euclidien de dimension n, de norme |·|, sur son image dans $(ℝ^{N}, ∥ \cdot ∥)$ : il existe α,β>0 tels que pour tout $x \in ℝ^{n}$ , $α \sqrt{N} | x | ⩽ ∥ Γ x ∥ ⩽ β \sqrt{N} | x |$ ; ce qui démontre une conjecture de Schechtman sur les plongements aléatoires de ℓ₂ⁿ dans ℓ₁^N.

Let $(ℝ^{N}, ∥ \cdot ∥)$ be the space $ℝ^{N}$ equipped with a norm ‖·‖ whose unit ball has a bounded volume ratio with respect to the Euclidean unit ball. Let Γ be any random N×n matrix with N>n, whose entries are independent random variables satisfying some moment assumptions. We show that with high probability Γ is a good isomorphism from the n-dimensional Euclidean space $(ℝ^{n}, | \cdot |)$ onto its image in $(ℝ^{N}, ∥ \cdot ∥)$ : there exist α,β>0 such that for all $x \in ℝ^{n}$ , $α \sqrt{N} | x | ⩽ ∥ Γ x ∥ ⩽ β \sqrt{N} | x |$ . This solves a conjecture of Schechtman on random embeddings of ℓ₂ⁿ into ℓ₁^N.

Reçu le : 2004-04-01
Accepté le : 2004-04-27
Publié le : 2004-05-28

DOI : 10.1016/j.crma.2004.04.019

Affiliations des auteurs :

Litvak, Alexander ¹ ; Pajor, Alain ² ; Rudelson, Mark ³ ; Tomczak-Jaegermann, Nicole ¹ ; Vershynin, Roman ⁴

@article{CRMATH_2004__339_1_33_0,
     author = {Litvak, Alexander and Pajor, Alain and Rudelson, Mark and Tomczak-Jaegermann, Nicole and Vershynin, Roman},
     title = {Random {Euclidean} embeddings in spaces of bounded volume ratio},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {33--38},
     publisher = {Elsevier},
     volume = {339},
     number = {1},
     year = {2004},
     doi = {10.1016/j.crma.2004.04.019},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2004.04.019/}
}

TY  - JOUR
AU  - Litvak, Alexander
AU  - Pajor, Alain
AU  - Rudelson, Mark
AU  - Tomczak-Jaegermann, Nicole
AU  - Vershynin, Roman
TI  - Random Euclidean embeddings in spaces of bounded volume ratio
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 33
EP  - 38
VL  - 339
IS  - 1
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2004.04.019/
DO  - 10.1016/j.crma.2004.04.019
LA  - en
ID  - CRMATH_2004__339_1_33_0
ER  -

%0 Journal Article
%A Litvak, Alexander
%A Pajor, Alain
%A Rudelson, Mark
%A Tomczak-Jaegermann, Nicole
%A Vershynin, Roman
%T Random Euclidean embeddings in spaces of bounded volume ratio
%J Comptes Rendus. Mathématique
%D 2004
%P 33-38
%V 339
%N 1
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2004.04.019/
%R 10.1016/j.crma.2004.04.019
%G en
%F CRMATH_2004__339_1_33_0

Litvak, Alexander; Pajor, Alain; Rudelson, Mark; Tomczak-Jaegermann, Nicole; Vershynin, Roman. Random Euclidean embeddings in spaces of bounded volume ratio. Comptes Rendus. Mathématique, Tome 339 (2004) no. 1, pp. 33-38. doi : 10.1016/j.crma.2004.04.019. http://www.numdam.org/articles/10.1016/j.crma.2004.04.019/

Bibliographie
Cité par

[1] Carl, B. Inequalities of Bernstein–Jackson type and the degree of compactness of operators in Banach spaces, Ann. Inst. Fourier, Volume 35 (1985), pp. 79-118

[2] Giannopoulos, A.; Milman, V.D. Mean width and diameter of proportional sections of a symmetric convex body, J. Reine Angew. Math., Volume 497 (1998), pp. 113-139

[3] Giannopoulos, A.; Milman, V.D. On the diameter of proportional sections of a symmetric convex body, Internat. Math. Res. Notices, Volume 1 (1997), pp. 5-19

[4] Kashin, B. The widths of certain finite-dimensional sets and classes of smooth functions, Izv. Akad. Nauk SSSR Ser. Mat., Volume 41 (1977), pp. 334-351 (in Russian)

[5] A.E. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, submitted for publication

[6] Milman, V.D.; Pajor, A. Regularization of star bodies by random hyperplane cut off, Studia Math., Volume 159 (2003), pp. 247-261

[7] Pisier, G. The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press, 1989

[8] G. Schechtman, Special orthogonal splittings of L₁^2k. Israel J. Math., in press

[9] Szarek, S.J. On Kashin's almost Euclidean orthogonal decomposition of l¹_n, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., Volume 26 (1978), pp. 691-694

[10] Szarek, S.J.; Tomczak-Jaegermann, N. On nearly Euclidean decomposition for some classes of Banach spaces, Compositio Math., Volume 40 (1980), pp. 367-385

Cité par Sources :