how to compute the original vector from a distance matrix?

I have a small question about vector and matrix.

Suppose a vector V = {v1, v2, ..., vn}. I generate a n-by-n distance matrix M define开发者_如何学Cd as:

M_ij = | v_i - v_j | such that i,j belong to [1, n].

That is, each element M_ij in the square matrix is the absolute distance of two elements in V.

For example, I have a vector V = {1, 3, 3, 5}, the distance matrix will be M=[ 0 2 2 4; 2 0 0 2; 2 0 0 2; 4 2 2 0; ]

It seems pretty simple. Now comes to the question. Given such a matrix M, how to obtain the initial V?

Thank you.

Based on some answer for this question, it seems that the answer is not unique. So, now suppose that all the initial vector has been normalized to 0 mean and 1 variance. The question is: Given such a symmetric distance matrix M, how to decide the initial normalized vector?

You can't. To give you an idea of why, consider these two cases:

V1 = {1,2,3}

M1 = [ 0 1 2 ; 1 0 1 ; 2 1 0 ]

V2 = {3,4,5}

M2 = [ 0 1 2 ; 1 0 1 ; 2 1 0 ]

As you can see, a single M could be the result of more than one V. Therefore, you can't map backwards.

There is no way to determine the answer uniquely, since the distance matrix is invariant to adding a constant to all elements and to multiplying all the values by -1. Assuming that element 1 is equal to 0, and that the first nonzero element is positive, however, you can find an answer. Here is the pseudocode:

# Assume v[1] is 0
v[1] = 0
# e is value of first non-zero vector element
e = 0
# ei is index of first non-zero vector element
ei = 0
for i = 2...n:
  # if all vector elements have been 0 so far
  if e == 0:
    # get the current distance from element 1 and its index
    # this new element may still be 0
    e = d[1,i]
    ei = i
    v[i] = e
  elseif d[1,i] == d[ei,i] + v[ei]: # v[i] <= v[1]
    # v[i] is to the left of v[1] (assuming v[ei] > v[1])
    v[i] = -d[1,i]
  else:
    # some other case; v[i] is to the right of v[1]
    v[i] = d[1,i]

I don't think it is possible to find the original vector, but you can find a translation of the vector by taking the first row of the matrix.

If you let M_ij = | v_i - v_j | and you translate all v_k for k\in [1,n] you will get M_ij = | v-i + 1 - v_j + 1 | = | v_i - v_j |

Hence, just take the first row as the vector and find one initial point to translate the vector to.

Correction:

Let v_1 = 0, and let l_k = | v_k | for k\in [2,n] and p_k the parity of v_k

Let p_1 = 1

for(int i = 2; i < n; i++)
   if( | l_i - l_(i+1) | != M_i(i+1) )
      p_(i+1) = - p_i
   else
      p_(i+1) = p_i

doing this for all v_k for k\in [2,n] in order will show the parity of each v_k in respect to the others

Then you can find a translation of the original vector with the same or opposite direction

Update (For Normalized vector):

  Let d = Sqrt(v_1^2 + v_2^2 + ... + v_n^2)

  Vector = {0, v_1 / d, v_2 / d, ... , v_n / d}
            or
           {0, -v_1 / d, -v_2 / d, ... , -v_n / d}