Convergence rates for ordinal embedding

04/30/2019
by   Jordan S. Ellenberg, et al.
0

We prove optimal bounds for the convergence rate of ordinal embedding (also known as non-metric multidimensional scaling) in the 1-dimensional case. The examples witnessing optimality of our bounds arise from a result in additive number theory on sets of integers with no three-term arithmetic progressions. We also carry out some computational experiments aimed at developing a sense of what the convergence rate for ordinal embedding might look like in higher dimensions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset