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 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, and V. Rödl, Geometrical realization of set systems and probabilistic communication complexity, in Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, 1985, pp. 277--280.
• 4: R. Babilon, J. Matoušek, J. Maxová, and P. Valtr, Low-distortion embeddings of trees. Journal of Graph Algorithms and Applications, 7 (2003), pp. 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: Y. Bilu and N. Linial, Monotone maps, sphericity and bounded second eigenvalue. arXiv:math.CO/0401293, 2004.
• 8: J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., 52 (1985), pp. 46--52.
• 9: 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
• 10: 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
• 11: 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]
• 12: 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]
• 13: J. P. Cunningham and R. N. Shepard, Monotone mapping of similarities into a general metric space. Journal of Mathematical Psychology, 11 (1974), pp. 335--364.
• 14: P. Erdös and H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12 (1963), pp. 251--257.
• 15: 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]
• 16: M. Farach, S. Kannan, and T. Warnow. A robust model for finding optimal evolutionary trees, Algorithmica, 13 (1995), pp. 155--179.
• 17: A. Gupta, Embedding tree metrics into low-dimensional Euclidean spaces, Discrete Comput. Geom., 24:105--116 (2000).
• 18: E. F. Harding, 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 (1966/1967), pp. 285--289.
• 19: 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]
• 20: W. Holman, The relation between hierarchical and euclidean models for psychological distances, Psychometrika, 37 (1972), pp. 417--423.
• 21: P. Indyk and J. Matoušek, Low-distortion embeddings of finite metric spaces, in Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds., CRC Press, second ed., 2004, ch. 8, pp. 177--196.
• 22: L. Ivansson, Computational Aspects of Radiation Hybrid, PhD thesis, Royal Institute of Technology, 2000.
• 23: W. B. Johnson and J. Lindenstrauss, Extensions of lipshitz mapping into hilbert space, Contemporary Mathematics, 26 (1984), pp. 189--206.
• 24: J. B. Kruskal, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29 (1964), pp. 1--28.
• 25: J. B. Kruskal, Non-metric multidimensional scaling, Psychometrika, 29 (1964), pp. 115--129.
• 26: J. R. Lee and A. Naor, Embedding the diamond graph in Lp and dimension reduction in L1, Geometric and Functional Analysis, 14 (2004), pp. 745--747.
• 27: N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15 (1995), pp. 215--245.
• 28: J. Matoušek, On embedding expanders into lp spaces, Israel Journal of Mathematics, 102 (1997), pp. 189--197.
• 29: J. Opatrny, Total ordering problem, SIAM J. Computing, 8 (1979), pp. 111--114.
• 30: R. Shah and M. Farach-Colton, On the complexity of ordinal clustering, Journal of Classification (2004). To appear.
• 31: R. N. Shepard, Multidimensional scaling with unknown distance function I, Psychometrika, 27 (1962), pp. 125--140.
• 32: W. S. Torgerson, Multidimensional scaling I: Theory and method, Psychometrika, 17 (1952), pp. 401--414.
• 33: H. E. Warren, Lower bounds for approximation by nonlinear manifolds, Trans. Amer. Math. Soc., 133:167--178 (1968).