Lost without a compass: Nonmetric triangulation and landmark multidimensional scaling

Suppose that we wish to determine the location of a point x* ∈ ℝ^k by comparing the distance from x* to various points x₁, x₂, ..., x_k ℝ^k with known position. In this paper we consider the scenario where we are only provided with (possibly noisy or contradictory) relations of the form ∥x* - x_i∥₂ <; ∥x* - x_j∥₂. We propose a simple algorithm that uses convex optimization techniques to estimate x* from such data and we provide simulations demonstrating its effectiveness in practice.