Random Euclidean embeddings in spaces of bounded volume ratio

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

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

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

¹ 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, Volume 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 :

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

@article{CRMATH_2004__339_1_33_0,
     author = {Alexander Litvak and Alain Pajor and Mark Rudelson and Nicole Tomczak-Jaegermann and Roman Vershynin},
     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},
}

TY  - JOUR
AU  - Alexander Litvak
AU  - Alain Pajor
AU  - Mark Rudelson
AU  - Nicole Tomczak-Jaegermann
AU  - Roman Vershynin
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
DO  - 10.1016/j.crma.2004.04.019
LA  - en
ID  - CRMATH_2004__339_1_33_0
ER  -

%0 Journal Article
%A Alexander Litvak
%A Alain Pajor
%A Mark Rudelson
%A Nicole Tomczak-Jaegermann
%A Roman Vershynin
%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

Alexander Litvak; Alain Pajor; Mark Rudelson; Nicole Tomczak-Jaegermann; Roman Vershynin. 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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.04.019/

Bibliographie
Cité par

[1] B. Carl 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] A. Giannopoulos; V.D. Milman Mean width and diameter of proportional sections of a symmetric convex body, J. Reine Angew. Math., Volume 497 (1998), pp. 113-139

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

[4] B. Kashin 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] V.D. Milman; A. Pajor Regularization of star bodies by random hyperplane cut off, Studia Math., Volume 159 (2003), pp. 247-261

[7] G. Pisier 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] S.J. Szarek 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] S.J. Szarek; N. Tomczak-Jaegermann On nearly Euclidean decomposition for some classes of Banach spaces, Compositio Math., Volume 40 (1980), pp. 367-385

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Lower estimates for the singular values of random matrices

Mark Rudelson

C. R. Math (2006)

Randomized isomorphic Dvoretzky theorem

Alexander Litvak; Piotr Mankiewicz; Nicole Tomczak-Jaegermann

C. R. Math (2002)

Smallest singular value of random matrices with independent columns

Radosław Adamczak; Olivier Guédon; Alexander Litvak; ...

C. R. Math (2008)