Re: Distributing n points in space


I have n points i don't have any coordinates, only thing i have is
distance matrix por each pair of points distance from one to the
other, i want to put them all in k<n dimensional space, it is probably
impossible to do it precisly what i want is to distribiute points in
space in in the way that minimize sum of diference between proper
distance and the real one. Is there any solution of this, does the
problem have any official name?

Consider the Gram matrix G:
G_{ij} = (x_i).(x_j)
G must be positive semidefinite. The n x n positive semidefinite matrix G
is the Gram matrix for n points of R^k if and only if G has rank <= k, and
these points can be obtained using the diagonalization of G. If G has some
negative eigenvalues or rank > k, the best approximation, in some sense,
is obtained by using the (up to) k largest positive eigenvalues and
eigenvectors.

Now given the distance matrix D:
D_{ij} = |x_i - x_j|
we can designate one of the points (say x_n) as the origin, and then
G_{ij} = (D_{in}^2 + D_{jn}^2 - D_{ij}^2)/2

For example, suppose you have the 4 x 4 distance matrix
[ 0 2 2 3]
[ 2 0 3 2]
D = [ 2 3 0 1]
[ 3 2 1 0]

and you want k=2. This leads to

[ 9 4.5 3 0 ]
[ 4.5 4 -2 0 ]
G = [ 3 -2 1 0 ]
[ 0 0 0 0 ]

which has a negative eigenvalue. If lambda_1 and lambda_2 are the two
positive eigenvalues and u_1 and u_2 the corresponding orthonormal
eigenvectors, then we take the points of R^2 corresponding to the
rows of the matrix with columns sqrt(lambda_1) u_1 and sqrt(lambda_2) u_2,
namely

[-3.01692215332068070, .520107363143339496],
[-1.58230163082378516, -1.45887821879530888],
[-.540150726393245684, 1.36862161370595770],
[0., 0.]

which would have the distance matrix
[0. 2.444283121 2.618085777 3.061426293]
[2.444283121 0. 3.013442187 2.152209123]
[2.618085777 3.013442187 0. 1.471355813]
[3.061426293 2.152209123 1.471355813 0. ]
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: Maximum relative error in Multidimensional sca
    ... yes, it's a bit non-euclidean, but the magnitudes of the negative ... > "D need not be a Euclidean distance matrix. ... > and CMDSCALE chooses p as the number of positive eigenvalues. ...
    (comp.soft-sys.matlab)
  • Re: Distributing n points in space
    ... distance matrix por each pair of points distance from one to the ... The n x n positive semidefinite matrix G ... negative eigenvalues or rank> k, the best approximation, in some sense, ... Now given the distance matrix D: ...
    (sci.math)