$\epsilon$-isometric dimension reduction for incompressible subsets of ${\ell }_p$

Abstract

Fix $p\in [1,\infty )$, $K\in (0,\infty )$ and a probability measure $\mu$. We prove that for every $n\in \mathbb{N}$, $\epsilon \in (0,1)$ and $x_1,\dots ,x_n\in L_p(\mu )$ with $\Vert {\max }_{i\in \{1,\dots ,n\}}|x_i|{\Vert }_{L_p(\mu )}\le K$, there exists $d\le \frac{32e^2(2K{)}^{2p}\log n}{{\epsilon }^2}$ and vectors $y_1,\dots ,y_n\in {\ell }_p^d$ such that $$\forall i,j\in \{1,\dots ,n\},\Vert x_i-x_j{\Vert }_{L_p(\mu )}^p-\epsilon \le \Vert y_i-y_j{\Vert }_{{\ell }_p^d}^p\le \Vert x_i-x_j{\Vert }_{L_p(\mu )}^p+\epsilon .$$ Moreover, the argument implies the existence of a greedy algorithm which outputs $\{y_i{\}}_{i=1}^n$ after receiving $\{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 classical factorization theory of $L_p(\mu )$ spaces. Motivated by the above embedding, we introduce the notion of $\epsilon$-isometric dimension reduction of the unit ball ${\mathbf{B}}_E$ of a normed space $(E,\Vert \cdot {\Vert }_E)$ and we prove that ${\mathbf{B}}_{{\ell }_p}$ does not admit $\epsilon$-isometric dimension reduction by linear operators for any value of $p\ne 2$.