Uniqueness of Ordinal Embedding

Matthäus Kleindessner, Ulrike Luxburg
Proceedings of The 27th Conference on Learning Theory, PMLR 35:40-67, 2014.

Abstract

Ordinal embedding refers to the following problem: all we know about an unknown set of points x_1,\ldots, x_n ∈\mathbbR^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 ∈\mathbbR^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 this Paper

BibTeX
@InProceedings{pmlr-v35-kleindessner14, title = {Uniqueness of Ordinal Embedding}, author = {Kleindessner, Matthäus and Luxburg, Ulrike}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {40--67}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/kleindessner14.pdf}, url = {https://proceedings.mlr.press/v35/kleindessner14.html}, abstract = {Ordinal embedding refers to the following problem: all we know about an unknown set of points x_1,\ldots, x_n ∈\mathbbR^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 ∈\mathbbR^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.} }
Endnote
%0 Conference Paper %T Uniqueness of Ordinal Embedding %A Matthäus Kleindessner %A Ulrike Luxburg %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-kleindessner14 %I PMLR %P 40--67 %U https://proceedings.mlr.press/v35/kleindessner14.html %V 35 %X Ordinal embedding refers to the following problem: all we know about an unknown set of points x_1,\ldots, x_n ∈\mathbbR^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 ∈\mathbbR^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.
RIS
TY - CPAPER TI - Uniqueness of Ordinal Embedding AU - Matthäus Kleindessner AU - Ulrike Luxburg BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-kleindessner14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 40 EP - 67 L1 - http://proceedings.mlr.press/v35/kleindessner14.pdf UR - https://proceedings.mlr.press/v35/kleindessner14.html AB - Ordinal embedding refers to the following problem: all we know about an unknown set of points x_1,\ldots, x_n ∈\mathbbR^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 ∈\mathbbR^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. ER -
APA
Kleindessner, M. & Luxburg, U.. (2014). Uniqueness of Ordinal Embedding. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:40-67 Available from https://proceedings.mlr.press/v35/kleindessner14.html.

Related Material