Publisher = {JMLR Workshop and Conference Proceedings},

Title = {Local Ordinal Embedding},

Url = {http://jmlr.org/proceedings/papers/v32/terada14.pdf},

Abstract = {We study the problem of ordinal embedding: given a set of ordinal constraints of the form $distance(i,j) < distance(k,l)$ for some_quadruples $(i,j,k,l)$ of indices, the goal is to construct a point configuration $\hat{\bm{x}}_1, ..., \hat{\bm{x}}_n$ in $\R^p$ that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know ``local ordinal information'' in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing.},

Author = {Yoshikazu Terada and Ulrike V. Luxburg},

Editor = {Tony Jebara and Eric P. Xing},

Year = {2014},

Booktitle = {Proceedings of the 31st International Conference on Machine Learning (ICML-14)},

Pages = {847-855}

}