Embedding points in 2D based on distance estimates?

Question

Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose that we instead have, for some pairs of points, an approximation for the Euclidean distance between them.

Question: How can we find an approximation of the coordinates of these points (up to flip/rotations of the plane) in the plane?

I.e., we want to embed the points in the plane in a way that is as consistent as possible with the estimated distances. (Note: These distances might turn out to be inconsistent, since they're approximations.)

I need something that I can actually implement on a computer.

Motivation: This question arises from studying geometric graphs in the plane: we can approximate the Euclidean distance between vertices by studying the number of common neighbours. More common neighbours imply the vertices are more likely to be closer together. But not all pairs of vertices have common neighbours, in which case we don't have an estimate.

Answer 1

One standard thing is to simulate a network of springs, one per data that you have, such that each spring wants to have the length corresponding to your estimate. In other words, if $l_{ij}$ is your estimate, you can look at the energy $$H((x_i)) = \sum [l_{ij} - \|x_j-x_i\|]^2$$ or something similar. Of course the sum runs over all pairs for which you have an estimate. Then minimize H, which can be done numerically in a reasonably efficient way because of the shape of $H$.

Software packages like graphviz do that, and so does Mathematica IIRC.

Answer 2

For complete distance information, this is known as "multidimensional scaling" and heavily used in social sciences or psychology. Actually, there is a very simple approach in this case based on the singular value decomposition and this goes back to Householder and Young in the paper "Discussion of a set of points in terms of their mutual distances".

In the case of limited data, one can approach this via matrix completion, i.e. try to find a full distance matrix, i.e. a matrix $D$, such that $D_{i,j} = \|x_i-x_j\|$ for some points $x_i$ which has the known entries (up to an error) in the right places. See, e.g. "Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming" by Alfakih, Khandani and Wolkowicz or "Low-rank optimization for distance matrix completion" by Mishra, Meyer and Sepulchre.