Как рассчитать исходный вектор из матрицы расстояний?

Question

У меня небольшой вопрос о векторе и матрице.

Предположим, что вектор V = {v1, v2, ..., vn}. Я генерирую матрицу расстояний n-на-n, определенную как:

M_ij = | v_i - v_j | так что i, j принадлежат [1, n].

То есть каждый элемент M_ij в квадратной матрице является абсолютным расстоянием двух элементов в V.

Например, у меня есть вектор V = {1, 3, 3, 5}, матрица расстояний будет М = [ 0 2 2 4; 2 0 0 2; 2 0 0 2; 4 2 2 0; ]

Кажется, довольно просто. Теперь приходит к вопросу. Учитывая такую ​​матрицу М, как получить начальную V?

Спасибо.

Основываясь на каком-то ответе на этот вопрос, кажется, что ответ не уникален. Итак, теперь предположим, что весь начальный вектор был нормализован до 0 и 1 дисперсии. Вопрос в том, что, учитывая такую ​​симметричную матрицу расстояний M, как определить начальный нормализованный вектор?

Answer 1

Нет способа однозначно определить ответ, поскольку матрица расстояний инвариантна к добавлению константы ко всем элементам и умножению всех значений на -1.Предполагая, что элемент 1 равен 0, и что первый ненулевой элемент является положительным, вы можете найти ответ.Вот псевдокод:

# 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]

Answer 2

Вы не можете. Чтобы дать вам представление о том, почему, рассмотрим эти два случая:

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]

Как видите, один M может быть результатом более чем одного V. Следовательно, вы не можете отобразить в обратном направлении.

Answer 3

Я не думаю, что можно найти исходный вектор, но вы можете найти перевод вектора, взяв первую строку матрицы.

Если вы позволите M_ij = |v_i - v_j |и вы переводите все v_k для k \ in [1, n], вы получите M_ij = |vi + 1 - v_j + 1 |= |v_i - v_j |

Следовательно, просто возьмите первую строку в качестве вектора и найдите одну начальную точку для перевода вектора в.

Исправление:

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

делая этодля всех v_k для k \ in [2, n] по порядку будет отображаться четность каждого v_k по отношению к другим

Тогда можно найти перевод исходного вектора с тем же или противоположным направлением

Обновление (для нормализованного вектора):

  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}