Uniqueness of Ordinal Embedding
Abstract
Ordinal embedding refers to the following problem: all we know about an unknown set of points x_1,\ldots, x_n ∈\mathbb{R}^d are ordinal constraints of the form \|x_i - x_j\| < \|x_k - x_l\|; the task is to construct a realization y_1,\ldots, y_n ∈\mathbb{R}^d 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.
Cite
Text
Kleindessner and von Luxburg. "Uniqueness of Ordinal Embedding." Annual Conference on Computational Learning Theory, 2014.Markdown
[Kleindessner and von Luxburg. "Uniqueness of Ordinal Embedding." Annual Conference on Computational Learning Theory, 2014.](https://mlanthology.org/colt/2014/kleindessner2014colt-uniqueness/)BibTeX
@inproceedings{kleindessner2014colt-uniqueness,
title = {{Uniqueness of Ordinal Embedding}},
author = {Kleindessner, Matthäus and von Luxburg, Ulrike},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2014},
pages = {40-67},
url = {https://mlanthology.org/colt/2014/kleindessner2014colt-uniqueness/}
}