Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.40
URN: urn:nbn:de:0030-drops-160486
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16048/
Eskenazis, Alexandros
ε-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},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16048},
URN = {urn:nbn:de:0030-drops-160486},
doi = {10.4230/LIPIcs.SoCG.2022.40},
annote = {Keywords: Dimension reduction, \epsilon-isometric embedding, Maurey’s empirical method, change of measure}
}
| Keywords: | Dimension reduction, ε-isometric embedding, Maurey’s empirical method, change of measure | |
| Seminar: | 38th International Symposium on Computational Geometry (SoCG 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 01.06.2022 |
