Abstract
Suppose that we wish to estimate a low-dimensional vector x from a set of binary pairwise comparisons of the form “x is closer to p than to q” for various choices of vectors p and q. The problem of estimating x from this type of observation arises in a variety of contexts, including nonmetric multidimensional scaling, “unfolding”, and ranking problems, often because it provides a powerful and flexible model of preference. In this talk I will describe both theoretical bounds for how well we can expect to estimate x under a randomized model for p and q, as well as practical algorithms for doing so efficiently in a noisy setting. I will also show how we can significantly improve our performance by adaptively changing the distribution for choosing p and q. In doing so, I will also draw enlightening connections between this problem and the literature of 1-bit compressive sensing. Finally, I will describe how this technique can be extended to localizing items as well, and show that this provides a simple but effective method for large-scale nonmetric multidimensional scaling.