Revealing the Basis: Ordinal Embedding Through Geometry

Ordinal Embedding places n objects into R^d based on comparisons such as "a is closer to b than c." Current optimization-based approaches suffer from scalability problems and an abundance of low quality local optima. We instead consider a computational geometric approach based on selecting comparisons to discover points close to nearly-orthogonal "axes" and embed the whole set by their projections along each axis. We thus also estimate the dimensionality of the data. Our embeddings are of lower quality than the global optima of optimization-based approaches, but are more scalable computationally and more reliable than local optima often found via optimization. Our method uses \Theta(n d \log n) comparisons and \Theta(n^2 d^2) total operations, and can also be viewed as selecting constraints for an optimizer which, if successful, will produce an almost-perfect embedding for sufficiently dense datasets.