DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.55

Dimensionality of Hamming Metrics and Rademacher Type

Authors: Alexandros Eskenazis

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

Let X be a finite-dimensional normed space. We prove that if the Hamming cube {-1,1}ⁿ embeds into X with bi-Lipschitz distortion at most D ≥ 1, then dim(X) ≳ sup_{p ∈ [1,2]} n^p/(D^p 𝖳_p(X)^p), where 𝖳_p(X) is the Rademacher type p constant of X. This estimate yields a mutual refinement of distortion lower bounds which follow from works of Oleszkiewicz (1996) and Ivanisvili, van Handel and Volberg (2020). The proof relies on a combination of semigroup techniques on the biased hypercube with the Borsuk-Ulam theorem from algebraic topology.

Cite as

Alexandros Eskenazis. Dimensionality of Hamming Metrics and Rademacher Type. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eskenazis:LIPIcs.SoCG.2024.55,
  author =	{Eskenazis, Alexandros},
  title =	{{Dimensionality of Hamming Metrics and Rademacher Type}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.55},
  URN =		{urn:nbn:de:0030-drops-200004},
  doi =		{10.4230/LIPIcs.SoCG.2024.55},
  annote =	{Keywords: Hamming cube, Rademacher type, metric embeddings, Borsuk-Ulam theorem}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2022.40

ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p

Authors: Alexandros Eskenazis

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

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.

Cite as

Alexandros Eskenazis. ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SoCG.2022.40},
  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}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2017.50

A Spectral Gap Precludes Low-Dimensional Embeddings

Authors: Assaf Naor

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

We prove that if an n-vertex O(1)-expander embeds with average distortion D into a finite dimensional normed space X, then necessarily the dimension of X is at least n^{c/D} for some universal constant c>0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X)> c(log n)^2/D^2 of Linial, London and Rabinovich, strengthens a theorem of Matousek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.

Cite as

Assaf Naor. A Spectral Gap Precludes Low-Dimensional Embeddings. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{naor:LIPIcs.SoCG.2017.50,
  author =	{Naor, Assaf},
  title =	{{A Spectral Gap Precludes Low-Dimensional Embeddings}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.50},
  URN =		{urn:nbn:de:0030-drops-71822},
  doi =		{10.4230/LIPIcs.SoCG.2017.50},
  annote =	{Keywords: Metric embeddings, dimensionality reduction, expander graphs, nonlinear spectral gaps, nearest neighbor search, complex interpolation, Markov type.}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2016.83

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost

Authors: Alexandr Andoni, Assaf Naor, and Ofer Neiman

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

Transportation cost metrics, also known as the Wasserstein distances W_p, are a natural choice for defining distances between two pointsets, or distributions, and have been applied in numerous fields. From the computational perspective, there has been an intensive research effort for understanding the W_p metrics over R^k, with work on the W_1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W_2 metric, also known as the root-mean square (RMS) bipartite matching distance, is often a more suitable choice in many application areas, e.g. in graphics. Yet, the geometry of this metric space is currently poorly understood, and efficient algorithms have been elusive. For example, there are no known non-trivial algorithms for nearest-neighbor search or sketching for this metric. In this paper we take the first step towards explaining the lack of efficient algorithms for the W_2 metric, even over the three-dimensional Euclidean space R^3. We prove that there are no meaningful embeddings of W_2 over R^3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W_2 over R^3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Omega(sqrt(log(n))) for pointsets of size n equipped with the W_2 metric; and 2) any sketching algorithm of size s must incur Omega(sqrt(log(n))/sqrt(s)) approximation. Our results follow from a more general statement, asserting that W_2 over R^3 contains the 1/2-snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first non-embeddability/non-sketchability results for W_2.

Cite as

Alexandr Andoni, Assaf Naor, and Ofer Neiman. Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{andoni_et_al:LIPIcs.ICALP.2016.83,
  author =	{Andoni, Alexandr and Naor, Assaf and Neiman, Ofer},
  title =	{{Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{83:1--83:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.83},
  URN =		{urn:nbn:de:0030-drops-62028},
  doi =		{10.4230/LIPIcs.ICALP.2016.83},
  annote =	{Keywords: Transportation metric, embedding, snowflake, sketching}
}

4 Search Results for "Naor, Assaf"

Dimensionality of Hamming Metrics and Rademacher Type

Abstract

Cite as

ε-Isometric Dimension Reduction for Incompressible Subsets of 𝓁_p

Abstract

Cite as

A Spectral Gap Precludes Low-Dimensional Embeddings

Abstract

Cite as

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost

Abstract

Cite as

Thanks for your feedback!

Could not send message