Uniqueness of Ordinal Embedding
Matthäus Kleindeßner, Ulrike von Luxburg · Conference on Learning Theory · 2014
Ordinal embedding refers to the following problem: all we know about an unknown set of points x1, . . . , xn ∈ R are ordinal constraints of the form ‖xi−xj‖ < ‖xk−xl‖; the task is to construct a realization y1, . . . , yn ∈ R 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.