Dichotomies, structure, and concentration in normed spaces

Abstract

We use probabilistic, topological and combinatorial methods to establish the following deviation inequality: For any normed space $X=({\mathbb{R}}^n,\Vert \cdot \Vert )$ there exists an invertible linear map $T:{\mathbb{R}}^n\to {\mathbb{R}}^n$ with \[ \mathbb P\left( \big| \|TG\| -\mathbb E\|TG\| \big| > \varepsilon \mathbb E\|TG\| \right) \leq C\exp \left( -c\max\{ \varepsilon^2, \varepsilon \} \log n \right),\quad \varepsilon>0, \] where $G$ is the standard $n$-dimensional Gaussian vector and $C,c>0$ are universal constants. It follows that for every $\epsilon \in (0,1)$ and for every normed space $X=({\mathbb{R}}^n,\Vert \cdot \Vert )$ there exists a $k$-dimensional subspace of $X$ which is $(1+\epsilon )$-Euclidean and $k\ge c\epsilon \log n/\log \frac{1}{\epsilon }$. This improves by a logarithmic on $\epsilon$ term the best previously known result due to G. Schechtman.

26 pages; title changed, main result improved, referees' comments incorporated