Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a set $D$ consist of all pairwise distance of $N$ unknown dimension points.

e.g. If there is 3 points, ${x_a,x_b,x_c}$

$$D=\{||x_a-x_b||,||x_b-x_c||,||x_a-x_c||\}$$

How can I find the minimum dimension of space which can place all these $N$ points on it and satisfy the distance constraints?

share|improve this question
    
Take a look a this link you may find it useful ocw.mit.edu/courses/mathematics/… –  clark Jun 14 '12 at 16:31
    
@clark: I am not sure if this is what the OP is after... The answer does not need Johnson-Lindenstrauss. –  Dirk Jun 14 '12 at 17:47
    
Thanks for the Reference of J-L Theorem. Although I don't need it now. This is useful for my future work. –  Rein Jun 18 '12 at 3:14
add comment

2 Answers 2

up vote 1 down vote accepted

For this topic I can recommend the pretty old paper "Discussion of a set of point in terms of their mutual distances" by Gale Young and A.S. Householder. Although it is from 1938 and uses not "up-to-date" mathematical language it is pretty accessible. By the way: The answer lies in computing the rank of one specific matrix and you can calculate a constellation of points which produce the desired distances by one SVD.

share|improve this answer
    
Yes, this is indeed a classic reference for the problem. –  bgins Jun 15 '12 at 10:38
    
Thanks very much! –  Rein Jun 18 '12 at 3:14
add comment

http://en.wikipedia.org/wiki/Distance_geometry

http://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant#Cayley.E2.80.93Menger_determinants

http://en.wikipedia.org/wiki/Multidimensional_scaling

The first article above concerns finding information about a finite set of given distances between them.

I think in the last one, one considers distances measured with random error, and there is uncertainty in ones estimate of the dimension of the Euclidean space in which the points would fit if they had been measured exactly.

Notice that for some finite metric spaces, there is no Euclidean space in which they can be embedded. For example: \begin{align} d(A,B) & = 1 \\ d(A,C) & = 1 \\ d(A,D) & = 1 \\ d(B,C) & = 1 \\ d(C,D) & = 1 \\ d(B,D) & = 2 \end{align} This puts $B$, $C$, and $D$ on a common straight line, and makes $A$ equidistant from all three. Draw the picture.

share|improve this answer
    
Thanks. The article is very useful for my to know more about my problem statement. –  Rein Jun 18 '12 at 3:18
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.