Functional Analysis/Probability Theory
Random Euclidean embeddings in spaces of bounded volume ratio
Comptes Rendus. Mathématique, Volume 339 (2004) no. 1, pp. 33-38.

Let ( N ,·) 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 ,|·|) onto its image in ( N ,·): there exist α,β>0 such that for all x n , αN|x|ΓxβN|x|. This solves a conjecture of Schechtman on random embeddings of ℓ2n into ℓ1N.

Soit ( N ,·) 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 ,·) : il existe α,β>0 tels que pour tout x n , αN|x|ΓxβN|x| ; ce qui démontre une conjecture de Schechtman sur les plongements aléatoires de ℓ2n dans ℓ1N.

Published online:
DOI: 10.1016/j.crma.2004.04.019
Litvak, Alexander 1; Pajor, Alain 2; Rudelson, Mark 3; Tomczak-Jaegermann, Nicole 1; Vershynin, Roman 4

1 Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
2 É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
3 Department of Mathematics, University of Missouri, Columbia, MO 65211, USA
4 Department of Mathematics, University of California, Davis, CA 95616, USA
     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 = {}
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  -
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
%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, Volume 339 (2004) no. 1, pp. 33-38. doi : 10.1016/j.crma.2004.04.019.

[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 L12k. Israel J. Math., in press

[9] Szarek, S.J. On Kashin's almost Euclidean orthogonal decomposition of l1n, 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

Cited by Sources: