when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-160486
URL:

### ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p

 pdf-format:

### Abstract

Fix p ∈ [1,∞), K ∈ (0,∞) and a probability measure μ. We prove that for every n ∈ ℕ, ε ∈ (0,1) and x₁,…,x_n ∈ L_p(μ) with ‖max_{i ∈ {1,…,n}}|x_i|‖_{L_p(μ)} ≤ K, there exists d ≤ (32e² (2K)^{2p}log n)/ε² and vectors y₁,…, y_n ∈ 𝓁_p^d such that
∀i,j∈{1,…,n}, ‖x_i-x_j‖^p_{L_p(μ)}-ε ≤ ‖y_i-y_j‖_{𝓁_p^d}^p ≤ ‖x_i-x_j‖^p_{L_p(μ)}+ε.
Moreover, the argument implies the existence of a greedy algorithm which outputs {y_i}_{i = 1}ⁿ after receiving {x_i}_{i = 1}ⁿ 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 ε-isometric dimension reduction of the unit ball B_E of a normed space (E,‖⋅‖_E) and we prove that B_{𝓁_p} does not admit ε-isometric dimension reduction by linear operators for any value of p≠2.

### BibTeX - Entry

@InProceedings{eskenazis:LIPIcs.SoCG.2022.40,
author =	{Eskenazis, Alexandros},
title =	{{\epsilon-Isometric Dimension Reduction for Incompressible Subsets of 𝓁\underlinep}},
booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
pages =	{40:1--40:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-227-3},
ISSN =	{1868-8969},
year =	{2022},
volume =	{224},
editor =	{Goaoc, Xavier and Kerber, Michael},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
}