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
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$.
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
Affiliations des auteurs :
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
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
@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
