Fetching the paper…

Reading the bibliography…

2019

Convergence rates for ordinal embedding

Ellenberg, Jordan S., Jain, Lalit

Original
PDF
Post on X

Understand

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.

Convergence rates for ordinal embedding · Around

Built on

Kruskal, Joseph B., and Roger N. Shepard. ”A nonmetric variety of linear factor analysis.” Psychometrika 39, no. 2 (1974): 123-157
Original
1974
Earlier work this paper cites.
Gower, John C. ”Generalized procrustes analysis.” Psychometrika 40, no. 1 (1975): 33-51
1975
Earlier work this paper cites.
Borg, Ingwer, and Patrick Groenen. “Modern multidimensional scaling: Theory and applications.” Journal of Educational Measurement 40.3 (2003): 277-280
2003
Earlier work this paper cites.
Graham, Ron. ”On the growth of a Van der Waerden-like function.” Integers
2006
Earlier work this paper cites.

Similar

Agarwal, Sameer, Josh Wills, Lawrence Cayton, Gert Lanckriet, David Kriegman, and Serge Belongie. “Generalized non-metric multidimensional scaling.” In Artificial Intelligence and Statistics, pp. 11-18. 2007
2007
Cited alongside, same era.
Jamieson, Kevin G. and Nowak, Robert D, Low-dimensional embedding using adaptively selected ordinal data, Proceedings of Communication, Control, and Computing (Allerton)
2011
Cited alongside, same era.
Kleindessner, Matthäus and von Luxburg, Ulrike, Uniqueness of ordinal embedding, Proceedings of COLT
2014
Cited alongside, same era.

Then

Arias-Castro, Ery, Some theory for ordinal embedding, arXiv preprint arXiv:1501.02861 (2015)
Original
2015
Later among the works it cites.
Jain, Lalit, Kevin G. Jamieson, and Rob Nowak. ”Finite sample prediction and recovery bounds for ordinal embedding.” Advances In Neural Information Processing Systems
2016
Later among the works it cites.
Bower, Amanda, Lalit Jain, and Laura Balzano. “The Landscape of Non-Convex Quadratic Feasibility.” In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3974-3978. IEEE, 2018
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…