Encontrar las coordenadas de los puntos de la matriz de distancia.

Question

Tengo un conjunto de puntos (con coordenadas desconocidas) y la matriz de distancia. Necesito encontrar las coordenadas de estos puntos para trazarlos y mostrar la solución de mi algoritmo.

Puedo establecer uno de estos puntos en la coordenada (0,0) para simplificar y encontrar los otros. ¿Alguien puede decirme si es posible encontrar las coordenadas de los otros puntos y, en caso afirmativo, cómo?

¡Gracias por adelantado!

EDITAR Olvidé decir que necesito las coordenadas solo en xy

Answer 1

Hacer esto con los ángulos, como Jyrki sugerido, es complicado y difícil de generalizar a dimensiones diferentes. Aquí hay una respuesta que es esencialmente una generalización de WimC, que también corrige un error en su respuesta. En el final, voy a mostrar por qué esto funciona, ya que la prueba es simple y agradable.

El algoritmo

Dada una matriz de distancias $D_{ij}$, definir $$M_{ij} = \frac {D^2_{1j}+D^2_{i1}-D^2_{ij}} 2 \,.$$ Una cosa que es bueno saber que en caso de que la dimensionalidad de los datos que genera la matriz de distancias que no se sabe es que el más pequeño (Euclidiana) de la dimensión en la que los puntos pueden ser incorporados está dado por el rango $k$ de la matriz $M$. No incrustación es posible si $M$ no es positiva semi-definida.

Las coordenadas de los puntos puede ser obtenido por el autovalor de la descomposición: si escribimos $M = USU^T$, entonces la matriz $X = U \sqrt S$ (usted puede tomar la raíz cuadrada de elemento por elemento) da las posiciones de los puntos (cada fila corresponde a un punto). Tenga en cuenta que, si los puntos de datos pueden ser incorporados en $k$-dimensiones del espacio, sólo $k$ columnas de $X$ va a ser distinto de cero (correspondiente a $k$ cero autovalores de a $M$).

¿Por qué funciona esto?

Si $D$ proviene de las distancias entre los puntos, entonces hay $\mathbf x_i \in \mathbb R^m$ tal que $$D_{ij}^2 = (\mathbf x_i - \mathbf x_j)^2 = \mathbf x_i^2 + \mathbf x_j^2 - 2\mathbf x_i \cdot \mathbf x_j \,.$$ A continuación, la matriz de $M$ definido anteriormente adquiere una particular y agradable forma: $$M_{ij} = (\mathbf x_i - \mathbf x_1) \cdot (\mathbf x_j - \mathbf x_1) \equiv \sum_{a=1}^m \tilde x_{ia} \tilde x_{ja}\,,$$ donde los elementos $\tilde x_{ia} = x_{ia} - x_{1a}$ pueden ser montados en un $n \times m$ matriz $\tilde X$. En la forma de la matriz, $$M = \tilde X \tilde X^T \,.$$ Dicha matriz se llama matriz de Gram. Puesto que el original de vectores se dan en $m$ dimensiones, el rango de $M$ es en la mayoría de las $m$ (asumiendo $m \le n$).

Los puntos se obtiene haciendo que el autovalor de la descomposición descrita anteriormente no tiene que coincidir exactamente con los puntos que se pusieron en el cálculo de la matriz de distancias. Sin embargo, ellos pueden ser obtenidos a partir de ellos una rotación y una traslación. Esto puede ser demostrado por ejemplo, hacer una descomposición de valor singular de a $\tilde X$, y demostrando que si $\tilde X \tilde X^T = X X^T$ (donde $X$ puede ser obtenido a partir de la autovalor de descomposición, como en el anterior, $X = U\sqrt S$), $X$ debe ser el mismo que $\tilde X$ hasta una transformación ortogonal.

Answer 2

Supongo que esto es en $\mathbb{R}^2$. Usted puede calcular los posibles puntos de $v_j \in \mathbb{R}^2$ como sigue. Primer lugar, calcular la matriz de Gram $M$ a partir de la matriz de distancias $D$:

$$M_{i,j} = \frac{(D_{1,i})^2 + (D_{1, j})^2 - (D_{i, j})^2}{2}$$

para $i, j \in \{1,\dotsc, n\}$. (Tenga en cuenta que la primera fila y la columna de $M$ consta de ceros.) Este es un positivo semi-definida la matriz de rango en la mayoría de los dos. Voy a asumir el caso genérico donde el rango es dos (no todos los puntos en una sola línea).

Encontrar una base ortonormales $\{b_1, b_2\}$ para la columna espacio de $M$ (por ejemplo, mediante la aplicación de Gram-Schmidt). Deje $m_j$ el valor del $j$-ésima columna de a $M$. A continuación, tome $v_j = (\langle b_1, m_j \rangle, \langle b_2, m_j \rangle) \in \mathbb{R}^2$ donde $\langle \cdot, \cdot \rangle$ es la distancia euclídea producto interior en $\mathbb{R}^n$. Los puntos de $v_j$ va a satisfacer su matriz de distancias.