JEDNOSTKA NAUKOWA KATEGORII A+

Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$

Tom 178 / 2007

Y. Gordon, A. E. Litvak, A. Pajor, N. Tomczak-Jaegermann Studia Mathematica 178 (2007), 91-98 DOI: 10.4064/sm178-1-6

Streszczenie

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$.

Autorzy

  • Y. GordonDepartment of Mathematics, Technion
    Haifa 32000, Israel
    e-mail
  • A. E. LitvakDepartment of Mathematical
    and Statistical Sciences
    University of Alberta
    Edmonton, AB, Canada T6G 2G1
    e-mail
  • A. PajorÉ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
    e-mail
  • N. Tomczak-JaegermannDepartment of Mathematical
    and Statistical Sciences
    University of Alberta
    Edmonton, AB, Canada T6G 2G1
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek