Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$
Studia Mathematica, Tome 178 (2007) no. 1, pp. 91-98
Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences
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
@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},
publisher = {mathdoc},
volume = {178},
number = {1},
year = {2007},
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
PB - mathdoc
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
%I mathdoc
%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 :