Finite Sample Prediction and Recovery Bounds for Ordinal Embedding

Understand

The goal of ordinal embedding is to represent items as points in a low-dimensional Euclidean space given a set of constraints in the form of distance comparisons like "item $i$ is closer to item $j$ than item $k$".

• Ordinal constraints like this often come from human judgments.
• To account for errors and variation in judgments, we consider the noisy situation in which the given constraints are independently corrupted by reversing the correct constraint with some probability.
• This paper makes several new contributions to this problem.