Matriz de distancia euclidiana

En matemáticas , una matriz de distancia euclidiana es una matriz n × n que representa el espaciamiento de un conjunto de n puntos en el espacio euclidiano . Para los puntos en el espacio k -dimensional ℝ ^k , los elementos de su matriz de distancia euclidiana A están dados por los cuadrados de las distancias entre ellos. Es decir ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

${\displaystyle {\begin{aligned}A&=(a_{ij});\\a_{ij}&=d_{ij}^{2}\;=\;\lVert x_{i}-x_{j}\rVert ^{2}\end{aligned}}}$

donde denota la norma euclidiana en ℝ ^k . ${\displaystyle \|\cdot \|}$

${\displaystyle A={\begin{bmatrix}0&d_{12}^{2}&d_{13}^{2}&\dots &d_{1n}^{2}\\d_{21}^{2}&0&d_{23}^{2}&\dots &d_{2n}^{2}\\d_{31}^{2}&d_{32}^{2}&0&\dots &d_{3n}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots &\\d_{n1}^{2}&d_{n2}^{2}&d_{n3}^{2}&\dots &0\\\end{bmatrix}}}$

En el contexto de matrices de distancias (no necesariamente euclidianas) , las entradas se suelen definir directamente como distancias, no como sus cuadrados. Sin embargo, en el caso euclidiano, se utilizan los cuadrados de las distancias para evitar el cálculo de raíces cuadradas y simplificar los teoremas y algoritmos pertinentes.

Las matrices de distancias euclidianas están estrechamente relacionadas con las matrices de Gram (matrices de productos escalares , que describen normas de vectores y ángulos entre ellos). Estas últimas se analizan fácilmente utilizando métodos de álgebra lineal . Esto permite caracterizar las matrices de distancias euclidianas y recuperar los puntos que las realizan. Una realización, si existe, es única hasta las transformaciones rígidas , es decir, las transformaciones que preservan la distancia del espacio euclidiano ( rotaciones , reflexiones , traslaciones ). ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

En aplicaciones prácticas, las distancias son mediciones ruidosas o provienen de estimaciones de disimilitud arbitrarias (no necesariamente métricas ). El objetivo puede ser visualizar dichos datos mediante puntos en el espacio euclidiano cuya matriz de distancia se aproxime a una matriz de disimilitud dada lo mejor posible; esto se conoce como escalamiento multidimensional . Alternativamente, dados dos conjuntos de datos ya representados por puntos en el espacio euclidiano, uno puede preguntarse qué tan similares son en forma, es decir, qué tan estrechamente pueden estar relacionados por una transformación que preserve la distancia ; esto es el análisis de Procrustes . Algunas de las distancias también pueden faltar o venir sin etiquetar (como un conjunto desordenado o multiconjunto en lugar de una matriz), lo que lleva a tareas algorítmicas más complejas, como el problema de realización de grafos o el problema de la autopista de peaje (para puntos en una línea). ^{[1] [2]}

Propiedades

Por el hecho de que la distancia euclidiana es una métrica , la matriz A tiene las siguientes propiedades.

• Todos los elementos en la diagonal de A son cero (es decir, es una matriz hueca ); por lo tanto, la traza de A es cero.
• A es simétrico (es decir). ${\displaystyle a_{ij}=a_{ji}}$
• ${\displaystyle {\sqrt {a_{ij}}}\leq {\sqrt {a_{ik}}}+{\sqrt {a_{kj}}}}$(por la desigualdad triangular )
• ${\displaystyle a_{ij}\geq 0}$

En dimensión k , una matriz de distancia euclidiana tiene un rango menor o igual a k +2 . Si los puntos están en la posición general , el rango es exactamente min( n , k +2). ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

Las distancias se pueden reducir en cualquier potencia para obtener otra matriz de distancias euclidianas. Es decir, si es una matriz de distancias euclidianas, entonces es una matriz de distancias euclidianas para cada 0< s <1 . ^[3] ${\displaystyle A=(a_{ij})}$ ${\displaystyle ({a_{ij}}^{s})}$

Relación con la matriz de Gram

La matriz de Gram de una secuencia de puntos en un espacio k -dimensional ℝ ^k es la matriz n × n de sus productos puntuales (aquí se piensa que un punto es un vector desde 0 hasta ese punto): ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle G=(g_{ij})}$ ${\displaystyle x_{i}}$

${\displaystyle g_{ij}=x_{i}\cdot x_{j}=\|x_{i}\|\|x_{j}\|\cos \theta }$, donde es el ángulo entre el vector y . ${\displaystyle \theta }$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

En particular

${\displaystyle g_{ii}=\|x_{i}\|^{2}}$es el cuadrado de la distancia de desde 0 . ${\displaystyle x_{i}}$

Así, la matriz de Gram describe normas y ángulos de vectores (de 0 a) . ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

Sea la matriz k × n que contiene como columnas. Entonces ${\displaystyle X}$ ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$

${\displaystyle G=X^{\textsf {T}}X}$, porque (viendo como un vector columna). ${\displaystyle g_{ij}=x_{i}^{\textsf {T}}x_{j}}$ ${\displaystyle x_{i}}$

Las matrices que se pueden descomponer como , es decir, matrices de Gram de alguna secuencia de vectores (columnas de ), son bien entendidas: son precisamente matrices semidefinidas positivas . ${\displaystyle X^{\textsf {T}}X}$ ${\displaystyle X}$

Para relacionar la matriz de distancia euclidiana con la matriz de Gram, observe que

${\displaystyle d_{ij}^{2}=\|x_{i}-x_{j}\|^{2}=(x_{i}-x_{j})^{\textsf {T}}(x_{i}-x_{j})=x_{i}^{\textsf {T}}x_{i}-2x_{i}^{\textsf {T}}x_{j}+x_{j}^{\textsf {T}}x_{j}=g_{ii}-2g_{ij}+g_{jj}}$

Es decir, las normas y los ángulos determinan las distancias. Nótese que la matriz de Gram contiene información adicional: distancias desde 0 .

Por el contrario, las distancias entre pares de n +1 puntos determinan productos escalares entre n vectores ( 1≤ i ≤ n ): ${\displaystyle d_{ij}}$ ${\displaystyle x_{0},x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{i}-x_{0}}$

${\displaystyle g_{ij}=(x_{i}-x_{0})\cdot (x_{j}-x_{0})={\frac {1}{2}}\left(\|x_{i}-x_{0}\|^{2}+\|x_{j}-x_{0}\|^{2}-\|x_{i}-x_{j}\|^{2}\right)={\frac {1}{2}}(d_{0i}^{2}+d_{0j}^{2}-d_{ij}^{2})}$

(esto se conoce como identidad de polarización ).

Caracterizaciones

Para una matriz A de n × n , una secuencia de puntos en un espacio euclidiano de dimensión k ℝ ^k se denomina realización de A en ℝ ^k si A es su matriz de distancias euclidianas. Se puede suponer sin pérdida de generalidad que (porque la traducción por preserva las distancias). ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle x_{1}=\mathbf {0} }$ ${\displaystyle -x_{1}}$

Teorema ^[4]  ( criterio de Schoenberg , ^[5] demostrado independientemente por Young y Householder ^[6] )  :  Una matriz hueca simétrica n × n A con entradas reales admite una realización en ℝ ^k si y solo si la matriz ( n -1) × ( n -1) definida por ${\displaystyle G=(g_{ij})_{2\leq i,j\leq n}}$

${\displaystyle g_{ij}={\frac {1}{2}}(a_{1i}^{2}+a_{1j}^{2}-a_{ij}^{2})}$

es semidefinida positiva y tiene rango como máximo k .

Esto se desprende de la discusión anterior porque G es semidefinida positiva de rango como máximo k si y solo si se puede descomponer como donde X es una matriz k × n ^{. [7]} Además, las columnas de X dan una realización en ℝ ^k . Por lo tanto, cualquier método para descomponer G permite encontrar una realización. Los dos enfoques principales son variantes de la descomposición de Cholesky o el uso de descomposiciones espectrales para encontrar la raíz cuadrada principal de G , consulte Matriz definida#Descomposición . ${\displaystyle G=X^{\textsf {T}}X}$

El enunciado del teorema distingue el primer punto . Una variante más simétrica del mismo teorema es la siguiente: ${\displaystyle x_{1}}$

Corolario ^[8]  —  Una matriz hueca simétrica n × n A con entradas reales admite una realización si y sólo si A es semidefinida negativa en el hiperplano , es decir ${\displaystyle H=\{v\in \mathbf {R} ^{n}\colon e^{\textsf {T}}v=0\}}$

${\displaystyle v^{\textsf {T}}Av\leq 0}$para todos aquellos que . ${\displaystyle v\in \mathbf {R} ^{n}}$ ${\displaystyle \textstyle \sum _{i=1}^{n}v_{i}=0}$

Otras caracterizaciones involucran determinantes de Cayley-Menger . En particular, estos permiten mostrar que una matriz hueca simétrica n × n es realizable en ℝ ^k si y solo si cada submatriz principal ( k + 3) × ( k + 3) es. En otras palabras, una semimétrica en un número finito de puntos es encajable isométricamente en ℝ ^k si y solo si cada k + 3 puntos son. ^[9]

En la práctica, las condiciones de precisión o rango pueden fallar debido a errores numéricos, ruido en las mediciones o debido a que los datos no provienen de distancias euclidianas reales. Los puntos que alcanzan distancias óptimamente similares se pueden encontrar mediante una aproximación semidefinida (y una aproximación de bajo rango, si se desea) utilizando herramientas algebraicas lineales como la descomposición en valores singulares o la programación semidefinida . Esto se conoce como escalamiento multidimensional . Las variantes de estos métodos también pueden tratar con datos de distancia incompletos.

Los datos no etiquetados, es decir, un conjunto o multiconjunto de distancias no asignadas a pares particulares, son mucho más difíciles de manejar. Tales datos surgen, por ejemplo, en la secuenciación de ADN (específicamente, la recuperación del genoma a partir de una digestión parcial ) o la recuperación de fase . Dos conjuntos de puntos se denominan homométricos si tienen el mismo multiconjunto de distancias (pero no están necesariamente relacionados por una transformación rígida). Decidir si un multiconjunto dado de n ( n -1)/2 distancias se puede realizar en una dimensión dada k es fuertemente NP-hard . En una dimensión esto se conoce como el problema de la autopista; es una pregunta abierta si se puede resolver en tiempo polinomial. Cuando el multiconjunto de distancias se da con barras de error, incluso el caso unidimensional es NP-hard . Sin embargo, existen algoritmos prácticos para muchos casos, por ejemplo, puntos aleatorios. ^{[10] [11] [12]}

Unicidad de las representaciones

Dada una matriz de distancias euclidianas, la secuencia de puntos que la realizan es única hasta las transformaciones rígidas – estas son isometrías del espacio euclidiano: rotaciones , reflexiones , traslaciones y sus composiciones. ^[1]

Teorema  —  Sean y dos secuencias de puntos en el espacio euclidiano k -dimensional ℝ ^k . Las distancias y son iguales (para todo 1≤ i , j ≤ n ) si y solo si existe una transformación rígida de ℝ ^k que se asigne a (para todo 1≤ i ≤ n ). ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle y_{1},y_{2},\ldots ,y_{n}}$ ${\displaystyle \|x_{i}-x_{j}\|}$ ${\displaystyle \|y_{i}-y_{j}\|}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

En las aplicaciones, cuando las distancias no coinciden exactamente, el análisis de Procrustes tiene como objetivo relacionar dos conjuntos de puntos lo más cercanos posible a través de transformaciones rígidas, generalmente utilizando la descomposición en valores singulares . El caso euclidiano ordinario se conoce como el problema de Procrustes ortogonal o el problema de Wahba (cuando las observaciones se ponderan para tener en cuenta las incertidumbres variables). Los ejemplos de aplicaciones incluyen la determinación de las orientaciones de los satélites, la comparación de la estructura de las moléculas (en quimioinformática ), la estructura de las proteínas ( alineación estructural en bioinformática ) o la estructura ósea ( análisis estadístico de la forma en biología).

Véase también

• Matriz de adyacencia
• Coplanaridad
• Geometría de distancia
• Matriz hueca
• Matriz de distancia
• Matriz aleatoria euclidiana
• Escalamiento multidimensional clásico , una técnica de visualización que aproxima una matriz de disimilitud arbitraria mediante una matriz de distancia euclidiana
• Determinante de Cayley-Menger
• Incrustación semidefinida

Notas

1. Dokmanic y otros (2015)
2. Entonces (2007)
3. Maehara, Hiroshi (2013). "Incrustaciones euclidianas de espacios métricos finitos". Matemáticas discretas . 313 (23): 2848–2856. doi : 10.1016/j.disc.2013.08.029 . ISSN  0012-365X.Teorema 2.6
4. So (2007), Teorema 3.3.1, pág. 40
5. Schoenberg, IJ (1935). "Observaciones al artículo de Maurice Fréchet" Sur La Definición Axiomatique D'Une Classe D'Espace Distancias Vectoriellement Aplicable Sur L'Espace De Hilbert "". Anales de Matemáticas . 36 (3): 724–732. doi :10.2307/1968654. ISSN  0003-486X. JSTOR  1968654.
6. Young, Gale; Householder, AS (1 de marzo de 1938). "Discusión de un conjunto de puntos en términos de sus distancias mutuas". Psychometrika . 3 (1): 19–22. doi :10.1007/BF02287916. ISSN  1860-0980. S2CID  122400126.
7. So (2007), Teorema 2.2.1, pág. 10
8. So (2007), Corolario 3.3.3, p. 42
9. Menger, Karl (1931). "Nueva base de la geometría euclidiana". American Journal of Mathematics . 53 (4): 721–745. doi :10.2307/2371222. JSTOR  2371222.
10. Lemke, Paul; Skiena, Steven S.; Smith, Warren D. (2003). "Reconstrucción de conjuntos a partir de distancias entre puntos". En Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.). Geometría discreta y computacional . Vol. 25. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 597–631. doi :10.1007/978-3-642-55566-4_27. ISBN 978-3-642-62442-1.
11. Huang, Shuai; Dokmanić, Ivan (2021). "Reconstrucción de conjuntos de puntos a partir de distribuciones de distancia". IEEE Transactions on Signal Processing . 69 : 1811–1827. arXiv : 1804.02465 . doi :10.1109/TSP.2021.3063458. S2CID  4746784.
12. Jaganathan, Kishore; Hassibi, Babak (2012). "Reconstrucción de números enteros a partir de distancias por pares". arXiv : 1212.2386 [cs.DM].

Referencias

• Dokmanic, Ivan; Parhizkar, Reza; Ranieri, Juri; Vetterli, Martin (2015). "Matrices de distancia euclidianas: teoría esencial, algoritmos y aplicaciones". Revista IEEE de procesamiento de señales . 32 (6): 12–30. arXiv : 1502.07541 . doi :10.1109/MSP.2015.2398954. ISSN  1558-0792. S2CID  8603398.
• James E. Gentle (2007). Álgebra matricial: teoría, cálculos y aplicaciones en estadística. Springer-Verlag . p. 299. ISBN 978-0-387-70872-0.
• Anthony Man-Cho (2007). Un enfoque de programación semidefinida para el problema de realización de grafos: teoría, aplicaciones y extensiones (PDF) (PhD).
• Liberti, Leo; Lavor, Carlile; Maculan, Nelson; Mucherino, Antonio (2014). "Geometría de distancias euclidianas y aplicaciones". SIAM Review . 56 (1): 3–69. arXiv : 1205.0349 . doi :10.1137/120875909. ISSN  0036-1445. S2CID  15472897.
• Alfakih, Abdo Y. (2018). Matrices de distancia euclidianas y sus aplicaciones en la teoría de la rigidez . Cham: Springer International Publishing. doi :10.1007/978-3-319-97846-8. ISBN . 978-3-319-97845-1.