Localizing Users And Items From Paired Comparisons
Matthew Robert O'shaughnessy, Georgia Institute of Technology
Mark Andrew Davenport, Georgia Institute of Technology

Suppose that we wish to determine an embedding of points given only paired comparisons of the form "user x prefers item q_i to item q_j." Such observations arise in a variety of contexts, including applications such as recommendation systems, targeted advertisement, and psychological studies. In this paper we first present an optimization-based framework for localizing new users and items when an existing embedding is known. We demonstrate that user localization can be formulated as a simple constrained quadratic program, and that although item localization produces a set of non-convex constraints, we can make the problem convex by strategically combining comparisons to produce a set of convex linear constraints. Finally, we show that by iteratively applying this method to every user and item, we can recover an accurate embedding, allowing us to iteratively improve a given embedding or even generate an embedding from scratch.