Using distance matrix to find coordinate points of set of points

Question

Given a distance matrix and a set of points, how do you figure out the coordinates of these points?

Edit: This is on a plane.

This question was answered here but in trying different distance matrices, I really couldn't use this answer because the M matrix had negative values, as did my eigenvectors. So when you took the square root, the program (in R) outputs "NaN" for those associated entries. I'm guessing this will happen every time D(i,j)^2 is greater than D(1,j)^2 + D(i,1)^2.

For example, say I have a distance matrix:

0    73   102  496  432  184
73    0   303  392  436  233
102  303    0  366  207  353
496  392  366    0  172  103
432  436  207  172    0  352
184  233  353  103  352    0

Using the equation M(i,j) = (0.5)(D(1,j)^2+D(i,1)^2-D(i,j)^2), I get (which already has negative entries):

0      0.0      0.0      0.0      0.0      0.0
0   5329.0 -38038.0  48840.5    928.5  -7552.0
0 -38038.0  10404.0  61232.0  77089.5 -40174.5
0  48840.5  61232.0 246016.0 201528.0 134631.5  
0    928.5  77089.5 201528.0 186624.0  48288.0
0  -7552.0 -40174.5 134631.5  48288.0  33856.0

Then I get non - zero eigenvalues & eigenvectors:

477718.27  101845.63   16474.30  -13116.72 -100692.49


        [,1]       [,2]        [,3]        [,4]        [,5]
 0.00000000  0.0000000  0.00000000  0.00000000  0.00000000
-0.05928626  0.3205747  0.84148945  0.04869546 -0.42806691
-0.16650486 -0.5670946 -0.04507520 -0.58222690 -0.55647098
-0.73371713  0.2827320  0.07386302 -0.45957443  0.40627254
-0.59727407 -0.4623603  0.07806418  0.64968004 -0.03617241
-0.27144823  0.5309625 -0.52755471  0.15920983 -0.58372335

Since there are both negative eigenvalues and eigenvectors, when we compute sqrt(eigenvector(i)*eigenvalue(i)), we'll have negative values. Here is my final output:

[,1]     [,2]      [,3]     [,4]      [,5]
   0   0.0000   0.00000  0.00000   0.00000
 NaN 180.6907 117.74103      NaN 207.61291
 NaN      NaN       NaN 87.38939 236.71174
 NaN 169.6910  34.88326 77.64089       NaN
 NaN      NaN  35.86158      NaN  60.35139
 NaN 232.5429       NaN      NaN 242.43877

Is this the only clear way of computing the coordinate points without using angles? If it is, do we have to fix the distance matrix so D(i,j)^2 is not greater than D(1,j)^2 + D(i,1)^2.

Thanks.

Answer 1

Your data is inconsistent

Your coordinates are not consistent with positions of points in ℝ⁴, let alone a space of lower dimension. You can tell that fact by computing the Menger determinant of your squared distance matrix:

D <- as.matrix(read.table(textConnection("\
0    73   102  496  432  184
73    0   303  392  436  233
102  303    0  366  207  353
496  392  366    0  172  103
432  436  207  172    0  352
184  233  353  103  352    0")))
n <- nrow(D)
det(rbind(cbind(D^2, 1), c(rep(1, n), 0)))
# Result: 3.38761e+25

If your coordinates really came from points in a space of dimension less than five, then this determinant would have to be zero. As it is not, your distances are inconsistent, or the points form a simplex in a space of sufficiently high dimension.

But no mater the dimension, your data is still inconsistent since it violates the triangle inequality in several cases:

a b c   ac   abc    ab    bc
1 2 4: 496 > 465 =  73 + 392
1 3 4: 496 > 468 = 102 + 366
1 3 5: 432 > 309 = 102 + 207
1 6 4: 496 > 287 = 184 + 103
2 1 3: 303 > 175 =  73 + 102
2 6 4: 392 > 336 = 233 + 103
3 1 6: 353 > 286 = 102 + 184
5 4 6: 352 > 275 = 172 + 103

Going from a to c directly can never take longer than going via b, but according to your data it does.

Simple planar approach

If you had data consistent with points in the plane (i.e. all Menger determinants for combinations of four points evaluate to zero), you could use the following to obtain coordinates:

distance2coordinates <- function(D) {
  n <- nrow(D)
  maxDist <- which.max(D)
  p1 <- ((maxDist - 1) %% n) + 1
  p2 <- ((maxDist - 1) %/% n) + 1
  x2 <- D[p1, p2]
  r1sq <- D[p1,]^2
  r2sq <- D[p2,]^2
  x <- (r1sq - r2sq + x2^2)/(2*x2)
  y <- sqrt(r1sq - x^2)
  p3 <- which.max(y)
  x3 <- x[p3]
  y3 <- y[p3]
  plus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 - y)^2)
  minus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 + y)^2)
  y[minus < plus] <- -y[minus < plus]
  coords <- data.frame(x = x, y = y)
  return(coords)
}

The idea is that you choose two points with maximal distance as starting points. You place on in the origin and the other on the positive x axis. Then you can compute all other x coordinates from this, as the intersection of two circles, following the equations

I:     x²       + y² = r₁²
II:   (x - x₂)² + y² = r₂²
I-II:  2*x*x₂ = r₁² - r₂² + x₂²

Given these x coordinates, you can obtain y coordinates as well, up to sign. You then choose a third point, sufficiently far away from either of these two starting points, to decide on the sign.

This approach makes no attempt at all to handle imprecise input. It assumes exact data, and will only use part of the distance matrix to find the points. It will not find the point set most closely matching all of the input data.

On your data, this will fail, since some arguments to the square root will be negative. This means that the two circles involved don't intersect at all, hence the triangle inequality is violated.

If it is, do we have to fix the distance matrix so D(i,j)^2 is not greater than D(1,j)^2 + D(i,1)^2.

D(i,j) ≤ D(i,k) + D(k,j) would help, i.e. for all triples and without squares. This would ensure that the triangle inequality holds everywhere. The result still need not be planar; for that you'd have to fix all those Menger determinants.

Answer 2

This is a simple python function to calculate what you need, solving hyperspheres.

import sympy
import numpy as np
def give_coords(distances):
    """give coordinates of points for which distances given

    coordinates are given relatively. 1st point on origin, 2nd on x-axis, 3rd 
    x-y plane and so on. Maximum n-1 dimentions for which n is the number
    of points

     Args:
        distanes (list): is a n x n, 2d array where distances[i][j] gives the distance 
            from i to j assumed distances[i][j] == distances[j][i]

     Returns:
        numpy.ndarray: cordinates in list form n dim

     Examples:
        >>> a = sympy.sqrt(2)
        >>> distances = [[0,1,1,1,1,1],
                         [1,0,a,a,a,a],
                         [1,a,0,a,a,a],
                         [1,a,a,0,a,a],
                         [1,a,a,a,0,a],
                         [1,a,a,a,a,0]]
        >>> give_coords(distances)
        array([[0, 0, 0, 0, 0],
               [1, 0, 0, 0, 0],
               [0, 1, 0, 0, 0],
               [0, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [0, 0, 0, 0, 1]], dtype=object)

        >>> give_coords([[0, 3, 4], [3, 0, 5], [4, 5, 0]])
        array([[0, 0],
        [3, 0],
        [0, 4]], dtype=object)        

    """
    distances = np.array(distances)

    n = len(distances)
    X = sympy.symarray('x', (n, n - 1))

    for row in range(n):
        X[row, row:] = [0] * (n - 1 - row)

    for point2 in range(1, n):

        expressions = []

        for point1 in range(point2):
            expression = np.sum((X[point1] - X[point2]) ** 2) 
            expression -= distances[point1,point2] ** 2
            expressions.append(expression)

        X[point2,:point2] = sympy.solve(expressions, list(X[point2,:point2]))[1]

    return X