3 Search Results for "Naor, Assaf"


Document
ε-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-dev.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
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-dev.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
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-dev.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}
}
  • Refine by Author
  • 2 Naor, Assaf
  • 1 Andoni, Alexandr
  • 1 Eskenazis, Alexandros
  • 1 Neiman, Ofer

  • Refine by Classification
  • 1 Mathematics of computing → Approximation
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Random projections and metric embeddings

  • Refine by Keyword
  • 1 Dimension reduction
  • 1 Markov type.
  • 1 Maurey’s empirical method
  • 1 Metric embeddings
  • 1 Transportation metric
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail