Material Detail

Uniqueness of ordinal embedding

Uniqueness of ordinal embedding

This video was recorded at 27th Annual Conference on Learning Theory (COLT), Barcelona 2014. Ordinal embedding refers to the following problem: all we know about an unknown set of points x1,…,xn∈Rd are ordinal constraints of the form ∥xi−xj∥<∥xk−xl∥; the task is to construct a realization y1,…,yn∈Rd that preserves these ordinal constraints. It has been conjectured since the 1960ies that upon knowledge of all ordinal constraints a large but finite set of points can be approximately reconstructed up to a similarity transformation. The main result of our paper is a formal proof of this conjecture.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.