Ultra-low-dimensional embeddings for doubling metrics

ABSTRACT

We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain and of Johnson and Lindenstrauss imply that any metric on n points embeds into an O(log n)-dimensional Euclidean space with O(log n) distortion. Moreover, a simple "volume" argument shows that this bound is nearly tight: the uniform metric on n points requires Ω(log n/log log n) dimensions to embed with logarithmic distortion. It is natural to ask whether such a volume restriction is the only hurdle to low-dimensional low-distortion embeddings. Do doubling metrics, which do not have large uniform submetrics, embed in low dimensional Euclidean spaces with small distortion? In this paper, we answer the question positively and show that any doubling metric embeds into O(log log n) dimensions with o(log n) distortion. In fact, we give a suite of embeddings with a smooth trade-off between distortion and dimension: given an n-point metric (V,d) with doubling dimension dim_D, and any target dimension T in the range Ω(dim_D log log n) ≤ T ≤ O(log n), we embed the metric into Euclidean space ℝ^T with O(log n√dim_D/T) distortion.

REFERENCES

• 1: Ittai Abraham , Yair Bartal , T-H. Hubert Chan , Kedar Dhamdhere Dhamdhere , Anupam Gupta , Jon Kleinberg , Ofer Neiman , Aleksandrs Slivkins, Metric Embeddings with Relaxed Guarantees, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.83-100, October 23-25, 2005 [doi>10.1109/SFCS.2005.51]
• 2: Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132557]
• 3: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 4: Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132597]
• 5: Noga Alon. A parallel algorithmic version of the local lemma. Random Structures Algorithms, 2(4):367--378, 1991.
• 6: Noga Alon. Problems and results in extremal combinatorics. I. Discrete Math., 273(1--3):31--53, 2003.
• 7: Patrice Assouad. Plongements lipschitziens dans Rⁿ. Bull. Soc. Math. France, 111(4):429--448, 1983.
• 8: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 9: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 10: József Beck. An algorithmic approach to the Lovász local lemma. I. Random Structures Algorithms, 2(4):343--365, 1991.
• 11: Alina Beygelzimer , Sham Kakade , John Langford, Cover trees for nearest neighbor, Proceedings of the 23rd international conference on Machine learning, p.97-104, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143857]
• 12: Jean Bourgain. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Math., 52(1--2):46--52, 1985.
• 13: Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
• 14: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropou, Embedding ultrametrics into low-dimensional spaces, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137886]
• 15: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060624]
• 16: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation Algorithms for the 0-Extension Problem, SIAM Journal on Computing, v.34 n.2, p.358-372, 2005 [doi>10.1137/S0097539701395978]
• 17: Hubert T-H. Chan , Anupam Gupta , Bruce M. Maggs , Shuheng Zhou, On hierarchical routing in doubling metrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 18: K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom., 22(1):63--93, 1999.
• 19: Richard Cole , Lee-Ad Gottlieb, Searching dynamic point sets in spaces with bounded doubling dimension, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132599]
• 20: Sanjoy Dasgupta , Anupam Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures & Algorithms, v.22 n.1, p.60-65, January 2003 [doi>10.1002/rsa.10073]
• 21: Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
• 22: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 23: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 24: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 25: Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064117]
• 26: Piotr Indyk and Jiri Matoušek. Low-distortion embeddings of finite metric spaces. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 8, pages xviii+1539. Chapman & Hall/CRC, second edition, 2004.
• 27: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 28: Piotr Indyk , Assaf Naor, Nearest-neighbor-preserving embeddings, ACM Transactions on Algorithms (TALG), v.3 n.3, p.31-es, August 2007 [doi>10.1145/1273340.1273347]
• 29: William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 30: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 31: Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal scale-free compact routing schemes in networks of low doubling dimension, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.939-948, January 07-09, 2007, New Orleans, Louisiana
• 32: Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal-stretch name-independent compact routing in doubling metrics, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146412]
• 33: R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839--858, 2005.
• 34: Robert Krauthgamer , James R. Lee, The intrinsic dimensionality of graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780607]
• 35: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 36: D. G. Larman. A new theory of dimension. In Proc. London Math. Soc., 17, 1967.
• 37: James R. Lee and Assaf Naor. Embedding the diamond graph in L_p and dimension reduction in L₁. In Geometric and Functional Analysis (GAFA). Springer Verlag, 2003.
• 38: Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995. (Preliminary version in 35th FOCS, 1994).
• 39: Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993. (Preliminary version in 2nd SODA, 1991).
• 40: Jiří Matoušek. Bi-Lipschitz embeddings into low dimensional Euclidean spaces. Commentationes Mathematicae Universitatis Carolinae, 31(3):589--600, 1990.
• 41: Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276866]
• 42: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 43: D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509996]
• 44: Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007399]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications
      G.2.m Miscellaneous

General Terms:
Algorithms, Design, Measurement, Theory