Reconstructing an Euclidean point cloud from their pairwise distances

Question

I have a collection of points $P_1, ..., P_N$ in some Euclidean space $\mathbb R^m$ and the coordinates $x_1, x_2, ..., x_N$ respectively associated with them, where $x_i$ is the usual Cartesian tuple $x_i = (x_{i1}, x_{i2}, ..., x_{im})$. I can immediately calculate the pairwise distances between these points $r_{12}, r_{13}, ..., r_{N-1,N}$ under the usual Euclidean norm using Pythagoras' theorem (in $m$ dimensions), i.e. $r_{ij} = \left\Vert x_i - x_j \right\Vert$.

Suppose now I have the converse situation where I have the points $P_1, ..., P_N$ and all their associated pairwise distances $\{r_{ij}\}$, and I don't know their coordinates. What is known about the embeddability of these points in an Euclidean space, and is it possible to reconstruct the Cartesian coordinates for them? In other words, given an arbitrary collection of nonnegative numbers $\{r_{ij}\}$, how do I find all positive integers $m$ and enumerate all the possible sets of $N$ coordinates $x_1, x_2, ..., x_N \in \mathbb R^m$ that are consistent with the interpretation $r_{ij} = \left\Vert x_i - x_j \right\Vert$?

Answer 1

It is worth mentioning the following basic material.

Definition (Euclidean Distance Matrix or EDM). A real, symmetric, $n\times n$ matrix with elements $-\tfrac{1}{2}d_{ij}^2$ and a zero diagonal is called an EDM, if there exist $n$ points in some Euclidean space whose interpoint distances are $d_{ij}$.

Theorem (Schoenberg, 1935). A real, symmetric, $n\times n$ matrix with a zero diagonal is an EDM, if and only if the matrix $$M := (I-\tfrac{1}{n}ee^T)D(I-\tfrac{1}{n}ee^T),$$ is positive semidefinite (here $e$ denotes the vector of all ones).

Note 1: The above result opens paths into the study of radial positive definite functions.

Note 2: Igor mentioned the actual interesting problems related to EDMS are more along the lines of EDM Completion Problems (EDMCP), or multidimensional scaling (obtaining an embedding into Euclidean space with some error, in case an exact embedding does not exist, and so on).

Answer 2

If your distances are known exactly, the feasibility follows from the positive (semi) definiteness of the associated gram matrix (put one of the points, call it $p_0$ at the origin, then the $ij$-th entry equals $2<P_i, P_j> = d(P_i, P_0)^2 + d(P_j, P_0)^2 - d(P_i, P_j)^2).$ The reconstruction problem is a little tricky, and usually in practical applications, you either don't know all distances, all don't know them exactly. See this paper for a nice survey. (DISTANCE MATRIX RECONSTRUCTION FROM INCOMPLETE DISTANCE INFORMATION FOR SENSOR NETWORK LOCALIZATION), but be warned that this is a huge field, as "distance matrix reconstruction" or "multi-dimensional scaling" google searches will show.

Answer 3

.... R cmdscale