nach oben

Theory of Computing Systems

Erschienen in:

01.01.2016

Low Dimensional Embeddings of Doubling Metrics

verfasst von: Ofer Neiman

Erschienen in: Theory of Computing Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study several embeddings of doubling metrics into low dimensional normed spaces, in particular into ℓ ₂ and ℓ _∞. Doubling metrics are a robust class of metric spaces that have low intrinsic dimension, and often occur in applications. Understanding the dimension required for a concise representation of such metrics is a fundamental open problem in the area of metric embedding. Here we show that the n-vertex Laakso graph can be embedded into constant dimensional ℓ ₂ with the best possible distortion, which has implications for possible approaches to the above problem.

Since arbitrary doubling metrics require high distortion for embedding into ℓ ₂ and even into ℓ ₁, we turn to the ℓ _∞ space that enables us to obtain arbitrarily small distortion. We show embeddings of doubling metrics and their ”snowflakes” into low dimensional ℓ _∞ space that simplify and extend previous results.

Vorheriger Artikel Approximating the Sparsest k-Subgraph in Chordal Graphs

Nächster Artikel Online Knapsack Revisited

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

It is quite conceivable that 2 dimensions suffice, we used 3 to simplify the analysis.

Note that all the angles are less than π/8, 𝜃 _w,𝜃 _x≤1, so the higher terms of the Taylor expansion are indeed negligible.

Abraham, I., Bartal, Y., Neiman, O.: Embedding metric spaces in their intrinsic dimension. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pp. 363–372. Society for Industrial and Applied Mathematics, Philadelphia (2008)

Assouad, P.: Plongements lipschitziens dans ℝⁿ. Bull. Soc. Math. France 111(4), 429–448 (1983)MATHMathSciNet

Bo, B., Charikar, M.: On the impossibility of dimension reduction in l₁. J. ACM 52(5), 766–788 (2005)MathSciNetCrossRef

Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings of the 44th symposium on Theory of Computing, STOC ’12, pp 663–672. ACM, New York (2012)

Bollobás, B.: Extremal graph theory. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London (1978)MATH

Bartal, Y., Recht, B., Schulman, L.J.: Dimensionality reduction: beyond the johnson-lindenstrauss bound. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pp. 868–887. SIAM (2011)

Hubert Chan, T-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proceedings 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005)

Hubert Chan, T.-H., Gupta, A., Talwar, K.: Ultra-low-dimensional embeddings for doubling metrics. J. ACM 57(4) (2010)

Cheeger, J., Kleiner, B.: Differentiating maps into L ¹, and the geometry of BV functions. Annals of Math. 171(2), 1347–1385 (2010)MATHMathSciNetCrossRef

10.

Cheeger, J., Kleiner, B., Assaf Naor, A.: (logn)^Ω(1) integrality gap for the sparsest cut sdp. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09, pp 555–564. IEEE Computer Society, Washington (2009)

11.

Gottlieb, L.-A., Krauthgamer, R.: A nonlinear approach to dimension reduction. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pp. 888–899. SIAM (2011)

12.

Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and lowdistortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 03, pp. 534–543. IEEE Computer Society,Washington, DC (2003)

13.

Gottlieb, L.-A., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 08, pp. 591–600. Society for Industrial and Applied Mathematics, Philadelphia (2008)

14.

Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148–1184 (2006)MATHMathSciNetCrossRef

15.

Jaffe, A., Lee, J.R., Moharrami, M.: On the optimality of gluing over scales. In: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX ’09 / RANDOM ’09, pp. 190–201,Berlin, Springer-Verlag, Heidelberg (2009)

16.

Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839–858 (2005)MATHMathSciNetCrossRef

17.

Laakso, T.J.: Plane with A _∞-weighted metric not bi-Lipschitz embeddable to ℝ^N. Bull. London Math. Soc. 34(6), 667–676 (2002)

18.

Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215–245 (1995)MATHMathSciNetCrossRef

19.

Lee, J.R., Mendel, M., Naor, A.: Metric structures in l1: dimension, snowflakes, and average distortion. Eur. J. Comb. 26(8), 1180–1190 (2005)MATHMathSciNetCrossRef

20.

Lee, J.R., Naor, A.: Embedding the diamond graph in l _p and dimension reduction in l ₁, 745–747 (2004)

21.

Lang, U., Plaut, C.: Bilipschitz embeddings of metric spaces into space form. Geometriae Dedicata 87(1–3), 285–307 (2001)MATHMathSciNetCrossRef

22.

Lee, J.R.: Anastasios Sidiropoulos. Near-optimal distortion bounds for embedding doubling spaces into l1. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC ’11, pp. 765–772. ACM, New York (2011)

23.

Matouṡek, J.: Lectures on discrete geometry. Springer-Verlag, New York (2002)CrossRef

24.

Naor, A., Neiman, O.: Assouad’s theorem with dimension independent of the snowflaking. Revista Matematica Iberoamericana 28(4), 1–21 (2012)MathSciNetCrossRef

25.

Semmes, S.: On the nonexistence of bilipschitz parameterizations and geometric problems about a _∞ weights. Revista Matemática Iberoamericana 12, 337–410 (1996)

Titel: Low Dimensional Embeddings of Doubling Metrics
verfasst von: Ofer Neiman
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 1/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9567-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

Min-Sum 2-Paths Problems

Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs

On Two Continuum Armed Bandit Problems in High Dimensions

Approximating the Sparsest k-Subgraph in Chordal Graphs

Online Knapsack Revisited

Premium Partner