8
$\begingroup$

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$?

$\endgroup$
5
  • 3
    $\begingroup$ I think it's at least the fourth time this question has been asked here. $\endgroup$ May 21, 2012 at 23:54
  • 2
    $\begingroup$ If I may point to my answer to one of these previous questions: mathoverflow.net/questions/7794/76487#76487 . Short version: The problem is NP-hard; search under the phrase "distance geometry." $\endgroup$ May 22, 2012 at 0:03
  • $\begingroup$ @Joseph - thank you, I had the feeling that I was missing some magic incantation to find the relevant literature. $\endgroup$ May 22, 2012 at 6:05
  • $\begingroup$ @Gjergji my apologies for the duplication. FWIW I did try to search for this question but I didn't quite turn up anything on my own. $\endgroup$ May 22, 2012 at 6:11
  • $\begingroup$ But what is the regularity of this reconstruction map? Is it Lipchitz? $\endgroup$ Aug 15, 2023 at 1:29

3 Answers 3

3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ What is $D$ in the above? $\endgroup$ Apr 2, 2023 at 3:26
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The link is dead, try this instead $\endgroup$
    – J.J. Green
    Aug 25, 2016 at 16:14
1
$\begingroup$

.... R cmdscale

$\endgroup$
4
  • $\begingroup$ "Impenetrability!", as Humpty Dumpty said. $\endgroup$ May 22, 2012 at 0:05
  • 2
    $\begingroup$ I believe that the poster means that the OP should use the cmdscale command in the R system for statistical computing. $\endgroup$
    – Igor Rivin
    May 22, 2012 at 0:30
  • $\begingroup$ I beleive that if that's what the poster means, then that's what the poster should say. $\endgroup$ May 22, 2012 at 6:13
  • $\begingroup$ @Gerry: no argument there $\endgroup$
    – Igor Rivin
    May 22, 2012 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.