# Given pairwise distances of $N$ data points and find the minimal dimenion of space can fit the data

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?

-
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

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.

-
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

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.

-
Thanks. The article is very useful for my to know more about my problem statement. – Rein Jun 18 '12 at 3:18