2026-08-04T00:52:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16048 2024-03-06T10:56:50Z ddc:004 open_access

ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p Eskenazis, Alexandros Dimension reduction ε-isometric embedding Maurey’s empirical method change of measure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandros Eskenazis 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.40 urn:nbn:de:0030-drops-160486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.40 eng https://creativecommons.org/licenses/by/4.0/legalcode