3
$\begingroup$

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?

  • 0
    Thanks for the Reference of J-L Theorem. Although I don't need it now. This is useful for my future work.2012-06-18

2 Answers 2

1

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.

  • 0
    Yes, this is indeed a classic reference for the problem.2012-06-15
1

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.

  • 0
    Thanks. The article is very useful for my to know more about my problem statement.2012-06-18