Geodesic
Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$
Y. Gordon1 ; A. E. Litvak2 ; A. Pajor3 ; N. Tomczak-Jaegermann2
1Department of Mathematics, Technion Haifa 32000, Israel
2Department of Mathematical and Statistical Sciences University of Alberta Edmonton, AB, Canada T6G 2G1
3É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
Studia Mathematica, Tome 178 (2007) no. 1, pp. 91-98
Cet article a éte moissonné depuis la source Institute of Mathematics Polish Academy of Sciences

Voir la notice de l'article

We show that, given an $n$-dimensional normed space $X$, a sequence of $N = (8/\varepsilon)^{2n}$ independent random vectors $(X _i)_{i=1}^N$, uniformly distributed in the unit ball of $X^*$, with high probability forms an $\varepsilon$-net for this unit ball. Thus the random linear map $\varGamma:\mathbb R \rightarrow \mathbb{R}^N$ defined by $\varGamma x = (\langle x, X_i\rangle)_{i=1}^N$ embeds $X$ in $\ell^N_\infty$ with at most $1+\varepsilon$ norm distortion. In the case $X = \ell_2^n$ we obtain a random $1+\varepsilon$-embedding into $\ell_\infty^N$ with asymptotically best possible relation between $N$, $n$, and $\varepsilon$.
DOI : 10.4064/sm178-1-6
Keywords: given n dimensional normed space nbsp sequence varepsilon independent random vectors uniformly distributed unit ball * high probability forms varepsilon net unit ball random linear map vargamma mathbb rightarrow mathbb defined vargamma langle rangle embeds ell infty varepsilon norm distortion ell obtain random varepsilon embedding ell infty asymptotically best possible relation between varepsilon

Y. Gordon  1   ; A. E. Litvak  2   ; A. Pajor  3   ; N. Tomczak-Jaegermann  2

1 Department of Mathematics, Technion Haifa 32000, Israel
2 Department of Mathematical and Statistical Sciences University of Alberta Edmonton, AB, Canada T6G 2G1
3 É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 
@article{10_4064_sm178_1_6,
     author = {Y. Gordon and A. E. Litvak and A. Pajor and N. Tomczak-Jaegermann},
     title = {Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$},
     journal = {Studia Mathematica},
     pages = {91--98},
     year = {2007},
     volume = {178},
     number = {1},
     doi = {10.4064/sm178-1-6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/sm178-1-6/}
}
TY  - JOUR
AU  - Y. Gordon
AU  - A. E. Litvak
AU  - A. Pajor
AU  - N. Tomczak-Jaegermann
TI  - Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$
JO  - Studia Mathematica
PY  - 2007
SP  - 91
EP  - 98
VL  - 178
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4064/sm178-1-6/
DO  - 10.4064/sm178-1-6
LA  - en
ID  - 10_4064_sm178_1_6
ER  - 
%0 Journal Article
%A Y. Gordon
%A A. E. Litvak
%A A. Pajor
%A N. Tomczak-Jaegermann
%T Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$
%J Studia Mathematica
%D 2007
%P 91-98
%V 178
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4064/sm178-1-6/
%R 10.4064/sm178-1-6
%G en
%F 10_4064_sm178_1_6
Y. Gordon; A. E. Litvak; A. Pajor; N. Tomczak-Jaegermann. Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$. Studia Mathematica, Tome 178 (2007) no. 1, pp. 91-98. doi: 10.4064/sm178-1-6

Cité par Sources :