ε-Isometric Dimension Reduction for Incompressible Subsets of $\ell _p

• Published in: Discrete & computational geometry 2023
• Main Author: Eskenazis, Alexandros
• Format: Article
• Language: English
• Subjects: Functional Analysis; Mathematics
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-023-00587-w

Fix $p\in [1,\infty )$ p ∈ [ 1 , ∞ ) , $K\in (0,\infty )$ K ∈ ( 0 , ∞ ) , and a probability measure $\mu $ μ . We prove that for every $n\in \mathbb {N}$ n ∈ N , $\varepsilon \in (0,1)$ε ∈ ( 0 , 1 ) , and $x_1,\ldots ,x_n\in L_p(\mu )$ x 1 , … , x n ∈ L p ( μ ) with $\big \Vert \max _{i\in \{1,\ldots ,n\}} |x_i| \big \Vert _{L_p(\mu )} \le K$ ‖ max i ∈ { 1 , … , n } | x i | ‖ L p ( μ ) ≤ K , there exist $d\le \frac{32e^2 (2K)^{2p}\log n}{\varepsilon ^2}$ d ≤ 32 e 2 ( 2 K ) 2 p log n ε 2 and vectors $y_1,\ldots , y_n \in \ell _p^d$ y 1 , … , y n ∈ ℓ p d such that $\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}$ ∀ i , j ∈ { 1 , … , n } , ‖ x i - x j ‖ L p ( μ ) p - ε ≤ ‖ y i - y j ‖ ℓ p d p ≤ ‖ x i - x j ‖ L p ( μ ) p + ε . Moreover, the argument implies the existence of a greedy algorithm which outputs $\{y_i\}_{i=1}^n$ { y i } i = 1 n after receiving $\{x_i\}_{i=1}^n$ { 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 ${\textbf {B}}_E$ of a normed space $(E,\Vert \cdot \Vert _E)$ ( E , ‖ · ‖ E ) and we prove that ${\textbf {B}}_{\ell _p}$ does not admit $\varepsilon $ ε -isometric dimension reduction by linear operators for any value of $p\ne 2$ p ≠ 2 .