Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
I think it's at least the fourth time this question has been asked here. –  Gjergji Zaimi May 21 '12 at 23:54
1  
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." –  Joseph O'Rourke May 22 '12 at 0:03
    
@Joseph - thank you, I had the feeling that I was missing some magic incantation to find the relevant literature. –  Jiahao Chen May 22 '12 at 6:05
    
@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. –  Jiahao Chen May 22 '12 at 6:11
add comment

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

.... R cmdscale

share|improve this answer
    
"Impenetrability!", as Humpty Dumpty said. –  Gerald Edgar May 22 '12 at 0:05
    
I believe that the poster means that the OP should use the cmdscale command in the R system for statistical computing. –  Igor Rivin May 22 '12 at 0:30
    
I beleive that if that's what the poster means, then that's what the poster should say. –  Gerry Myerson May 22 '12 at 6:13
    
@Gerry: no argument there –  Igor Rivin May 22 '12 at 12:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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