Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics

ABSTRACT

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. The (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop several worst-case bounds and approximation algorithms on ordinal embedding. In particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.

REFERENCES

• 1: Richa Agarwala , Vineet Bafna , Martin Farach , Mike Paterson , Mikkel Thorup, On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics), SIAM Journal on Computing, v.28 n.3, p.1073-1085, Feb. 1999 [doi>10.1137/S0097539795296334]
• 2: Noga Alon, Tools from higher algebra, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
• 3: N. Alon , P. Frankl , V. Rodl, Geometrical realization of set systems and probabilistic communication complexity, Proceedings of the 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), p.277-280, October 21-23, 1985 [doi>10.1109/SFCS.1985.30]
• 4: Babilon, R., Matoušek, J., Maxová, J., and Valtr, P. 2003. Low-distortion embeddings of trees. J. Graph Algor. Appl. 7, 4, 399--409.
• 5: Mihai Bǎdoiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald Räcke , R. Ravi , Anastasios Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 6: Yair Bartal , Manor Mendel, Dimension reduction for ultrametrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: Barthelemy, J.-P., and Guenoche, A. 1991. Trees and Proximity Representations. John Wiley.
• 8: Bilu, Y., and Linial, N. 2004. Monotone maps, sphericity and bounded second eigenvalue. arXiv:math.CO/0401293.
• 9: Bourgain, J. 1985. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52, 1-2, 46--52.
• 10: 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
• 11: Mihai Bâdoiu, Approximation algorithm for embedding metrics into a two-dimensional space, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Mihai Bǎdoiu , Erik D. Demaine , Mohammad Taghi Hajiaghayi , Piotr Indyk, Low-dimensional embedding with extra information, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997866]
• 13: Benny Chor , Madhu Sudan, A Geometric Approach to Betweenness, SIAM Journal on Discrete Mathematics, v.11 n.4, p.511-523, Nov. 1998 [doi>10.1137/S0895480195296221]
• 14: Cunningham, J. P., and Shepard, R. N. 1974. Monotone mapping of similarities into a general metric space. J. Math. Psych. 11, 335--364.
• 15: Erdős, P., and Sachs, H. 1963. Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 12, 251--257.
• 16: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Journal of the ACM (JACM), v.46 n.4, p.437-449, July 1999 [doi>10.1145/320211.320212]
• 17: Farach, M., Kannan, S., and Warnow, T. 1995. A robust model for finding optimal evolutionary trees. Algorithmica 13, 1-2, 155--179.
• 18: Gupta, A. 2000. Embedding tree metrics into low-dimensional Euclidean spaces. Discrete Comput. Geom. 24, 1, 105--116.
• 19: Harding, E. F. 1966/1967. The number of partitions of a set of N points in k dimensions induced by hyperplanes. Proceedings of the Edinburgh Mathematical Society, Series II 15, 285--289.
• 20: Johan Håstad , Lars Ivansson , Jens Lagergren, Fitting points on the real line and its application to RH mapping, Journal of Algorithms, v.49 n.1, p.42-62, 1 October 2003 [doi>10.1016/S0196-6774(03)00083-X]
• 21: Holman, W. 1972. The relation between hierarchical and euclidean models for psychological distances. Psychometrika 37, 4, 417--423.
• 22: Indyk, P., and Matoušek, J. 2004. Low-distortion embeddings of finite metric spaces. In Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O'Rourke, Eds. CRC Press, Chap. 8, 177--196.
• 23: Ivansson, L. 2000. Computational aspects of radiation hybrid. Ph.D. thesis, Department of Numerical Analysis and Computer Science, Royal Institute of Technology.
• 24: Johnson, W. B., and Lindenstrauss, J. 1984. Extensions of lipshitz mapping into hilbert space. Contemp. Math. 26, 189--206.
• 25: Kruskal, J. B. 1964a. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29, 1--28.
• 26: Kruskal, J. B. 1964b. Non-metric multidimensional scaling. Psychometrika 29, 115--129.
• 27: Lee, J. R., and Naor, A. 2004. Embedding the diamond graph in L_p and dimension reduction in L₁. Geome. Funct. Anal. 14, 4, 745--747.
• 28: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--245.
• 29: Matoušek, J. 1990. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Commentationes Mathematicae Universitatis Carolinae 31, 3, 589--600.
• 30: Matoušek, J. 1997. On embedding expanders into l_p spaces. Israel Journal of Mathematics 102, 189--197.
• 31: Opatrny, J. 1979. Total ordering problem. SIAM J. Comput. 8, 111--114.
• 32: Shah, R., and Farach-Colton, M. 2004. On the complexity of ordinal clustering. J. Classification. To appear.
• 33: Shepard, R. N. 1962. Multidimensional scaling with unknown distance function I. Psychometrika 27, 125--140.
• 34: Torgerson, W. S. 1952. Multidimensional scaling I: Theory and method. Psychometrika 17, 4, 401--414.
• 35: Warren, H. E. 1968. Lower bounds for approximation by nonlinear manifolds. Trans. Amer. Math. Soc. 133, 167--178.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
Metrics, distortion, ordinal embedding, relaxation