ε-Isometric Dimension Reduction for Incompressible Subsets of ℓp

Abstract

Fix p∈[1,∞)$$p\in [1,\infty )$$, K∈(0,∞)$$K\in (0,\infty )$$, and a probability measure μ$$\mu $$. We prove that for every n∈N$$n\in \mathbb {N}$$, ε∈(0,1)$$\varepsilon \in (0,1)$$, and x1,…,xn∈Lp(μ)$$x_1,\ldots ,x_n\in L_p(\mu )$$ with ‖maxi∈{1,…,n}|xi|‖Lp(μ)≤K$$\big \Vert \max _{i\in {1,\ldots ,n}} |x_i| \big \Vert {L_p(\mu )} \le K$$, there exist d≤32e2(2K)2plognε2$$d\le \frac{32e^2 (2K)^{2p}\log n}{\varepsilon ^2}$$ and vectors y1,…,yn∈ℓpd$$y_1,\ldots , y_n \in \ell p^d$$ such that ∀i,j∈{1,…,n},‖xi-xj‖Lp(μ)p-ε≤‖yi-yj‖ℓpdp≤‖xi-xj‖Lp(μ)p+ε.$$\begin{aligned} {\forall },,i,j\in {1,\ldots ,n}, \quad \Vert x_i-x_j\Vert ^p{L_p(\mu )}-\varepsilon\le & {} \Vert y_i-y_j\Vert {\ell p^d}^p\le \Vert x_i-x_j\Vert ^p{L_p(\mu )}+\varepsilon . \end{aligned}$$Moreover, the argument implies the existence of a greedy algorithm which outputs {yi}i=1n$${y_i}{i=1}^n$$ after receiving {xi}i=1n$${x_i}{i=1}^n$$ as input. The proof relies on a derandomized version of Maurey’s empirical method (1981) combined with a combinatorial idea of Ball (1990) and a suitable change of measure. Motivated by the above embedding, we introduce the notion of ε$$\varepsilon $$-isometric dimension reduction of the unit ball BE$${\textbf {B}}_E$$ of a normed space (E,‖·‖E)$$(E,\Vert \cdot \Vert E)$$ and we prove that Bℓp$${\textbf {B}}{\ell _p}$$ does not admit ε$$\varepsilon $$-isometric dimension reduction by linear operators for any value of p≠2$$p\ne 2$$.