유클리드 거리 행렬

수학에서, 유클리드 거리 행렬은 유클리드 공간의 n개 점 집합의 간격을 나타내는 n×n 행렬이다.k차원 공간 δ의^k $점{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}{}_{}}$, x${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$(\$displaystyle x_{1$},$x_{2},\ldots,x_{n})$에 대해 유클리드 거리 행렬 A의 요소는 그 사이의 거리의 제곱으로 주어진다.그것은

$디스플레이 스타일A&=(a_{ij});\\a_{ij}&=d_{ij}^2}\;=\;\lVert x_{i}-x_{j}\rVert ^{2}\end{aligned}}$

여기서$‖(\displaystyle \\cdot \)$은 the의^k 유클리드 규격을 나타냅니다.

${\displaystyle A=bgin{bmatrix}^{2}&d_{13}^{2}&\dots&\d_{1n}^{2}^2}&\d_{2n}^{2}&\d_{2n}^{2}&\d_{2}^{2}^2}&d}^2}^2}&d}$

(꼭 유클리드라고는 할 수 없는) 거리 행렬의 맥락에서 엔트리는 일반적으로 정사각형이 아닌 거리로 직접 정의된다.그러나, 유클리드 사례에서, 거리의 제곱은 제곱근 계산을 피하고 관련 이론과 알고리즘을 단순화하기 위해 사용된다.

유클리드 거리 행렬은 그램 행렬과 밀접하게 관련되어 있다.후자는 선형대수의 방법을 사용하여 쉽게 분석됩니다.이를 통해 유클리드 거리 행렬을 특성화하고 이를 실현하는 x ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ {\$displaystyle x_{1$},$x_{2$},\$ldots,x_{n}$ $점$을 복구할 수 있습니다.실현이 존재하는 경우, 유클리드 공간의 거리 보존 변환(회전, 반사, 변환)과 같은 견고한 변환까지 유일하다.

실제 적용에서 거리는 노이즈가 많은 측정치이거나 임의의 차이점 추정치(메트릭이 반드시 필요한 것은 아님)에서 비롯됩니다.목표는 거리 행렬이 가능한 한 주어진 차이 행렬에 가까운 유클리드 공간의 점으로 이러한 데이터를 시각화하는 것일 수 있습니다. 이를 다차원 스케일링이라고 합니다.또는, 유클리드 공간의 점으로 이미 표현된 두 세트의 데이터가 주어진다면, 사람들은 그것들이 얼마나 비슷한 모양인지, 즉 거리 보존 변환에 의해 얼마나 밀접하게 관련될 수 있는지 물어볼 수 있다. 이것이 프로크러스테스 분석이다.거리 중 일부는 누락되거나 레이블이 지정되지 않은 상태(매트릭스 대신 순서 없는 집합 또는 다중 집합)로 표시될 수 있으며, 이로 인해 그래프 실현 문제 또는 턴파이크 문제(선상의 ^[1][2]점)와 같은 보다 복잡한 알고리즘 작업이 발생할 수 있습니다.

특성.

유클리드 거리가 미터법이라는 사실에 의해 행렬 A는 다음과 같은 성질을 가진다.

• A의 대각선상의 모든 원소는 0(즉, 중공 매트릭스)이므로 A의 트레이스는 0입니다.
• A는 대칭입니다(${\displaystyle {즉}_{}}$, ${\displaystyle {\mathrm{ij}}_{}}$ $=$ ${\displaystyle a_{}}$ ${\displaystyle j_{}}${$displaystyle a_{ij$}=$a_{$ji$}}).$
• ${\displaystyle \sqrt{{}_{}}\sqrt{a_{}}}$ i j${\displaystyle \sqrt{{}_{}}a\sqrt{{}_{}}}$ ${\displaystyle \sqrt{a_{}}}$ ${\displaystyle \sqrt{k_{}}}$ + a k j$$($displaystyle$ { $a$_ { $ij$} ) \ $leq$( \ displayrt$${ $a$_ { $ik$} ) + { \ $scrt${ $a$_ { $kj$} $$} （ triangle 부등식 ）
• ${\displaystyle a_{ij}\geq 0}$

차원 k에서, 유클리드 거리 행렬은 k+2 이하의 순위를 가진다.${\displaystyle {x\mathrm{}}_{}{}_{}}$, ${\displaystyle {x\mathrm{}}_{}}$2,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ $(\$ 포인트가$$ 일반 위치에 있는 경우 순위는 정확히 min(n, k + 2)입니다.

거리는 다른 유클리드 거리 행렬을 얻기 위해 어떤 거듭제곱으로도 축소될 수 있다.즉, A ${\displaystyle =}$ ( ${\displaystyle {}_{}{j}_{}}$) { $displaystyle$ A = ( $a$_ { $ij$} )이 유클리드 거리 행렬이라면$,{\displaystyle }$ ( ${\displaystyle {{}_{}}^{}}$ $j$) { $display$ { a _ { ij$}^{s}}$는 모든 0<s < ^[3]1에 대한 유클리드 거리 행렬이다.

그램 행렬과의 관계

k차원 공간 is의^k $점{\displaystyle {}_{}}$ x${\displaystyle {}_{}{}_{}}$, ${\displaystyle {x\mathrm{}}_{}}$2,${\displaystyle \dots ,}$ ${\displaystyle x_{}}$n {\$displaystyle x_{$1},$x_{n}$의 그램 행렬은 점곱의 n×n $행렬{\displaystyle }$ G $=$(${\displaystyle g_{}}$ ${\displaystyle i_{}}$j$)$ {$displaystyle$ G=($g_{ij})$ {$display$ style$x_ij}$이라고 생각됨

${\displaystyle g_{}}$ ${\displaystyle i_{}}$ j ${\displaystyle {}_{}}$ ${\displaystyle x_{}}$ i${\displaystyle {}_{}{}_{}}$ x ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ $x$ i display x ${\displaystyle i_{}}$ display ${\displaystyle x_{}}$ ${\displaystyle \mathrm{display}{}_{}}$x j cos${\displaystyle }$displaydisplay ${\displaystyle \mathrm{display}}$display 、 \ $display$ $style$ $g _$ { i } = \ $x _${$i }$\ $cos$\ $theta$ $\}$ 。$여기$서$$\ $display$style \ $teta$}는$$x $사이$의 $벡터{\displaystyle {}_{}}$ 각도입니다.

특히

${\displaystyle g_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \Vert }$ ‖ ${\displaystyle {}_{}}$ 2 { { $displaystyle$ $g$$_$ { i } = \ $x$_ { $i$} ^ {$$} $is$$$ 、 ${\displaystyle x_{}}$ i$0$ 0 0 $0{\displaystyle {}_{}}$ 0 0 g of of g 。

따라서 그램 매트릭스는 (0 ~ )${\displaystyle {}_{}{}_{}}$1, x${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle x_{}}$n(\$style x_{1$},$x_{$2},\$ldots,x_{$n$\})$의 기준과 각도를 나타냅니다.

X$(\displaystyle$ X$)$를 ${\displaystyle {x1\mathrm{}}_{}}$ ${\displaystyle {x2\mathrm{}}_{}}$,$(\$을 열로 $포함$하는 k×n 매트릭스로 $합니다{\displaystyle }$.그리고나서

${\displaystyle }$$G{\displaystyle {}_{}}$ ${\displaystyle =}$ ${\displaystyle X^{}}$ T$$ { $displaystyle$ G =$X ^$ { \ $textsf${ ${\displaystyle T_{}^{}{}_{}}$$$} X $\}$ 。$g$ i j$= x$ ${\displaystyle {\_}_{}}${ i j } = x _ { i }^{ \ $scapf${ $T$} $x$$$$$_ { $j$} $$（ ${\displaystyle x_{}}$ $i$） 。

${\displaystyle X^{}}$ ${\displaystyle T^{}}$ X$(\displaystyle$ X$^{\textsf {T}X$로 분해할 수 있는 행렬, 즉 X$(\displaystyle$의 열)$$의 그램 행렬은 정확히 양의 반정의 행렬이다.

유클리드 거리 행렬과 그램 행렬을 관련시키려면, 다음을 관찰하십시오.

$({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}}^{\sqf {T}}x_{j}=g_{i}-2g_{ij}+g_{jj}}$

즉, 규범과 각도가 거리를 결정합니다.Gram 매트릭스에는 0으로부터의 거리라는 추가 정보가 포함되어 있습니다.

반대로 n+1 $포인트{\displaystyle {}_{}}$ 쌍 ${\displaystyle {x\mathrm{}}_{}}$ 0,${\displaystyle {}_{}{}_{}}$ 1,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$({$displaystyle x_{0$},$x_{1},\ldots, x_{$n$$}) ${\displaystyle {사이}_{}}$의 ${\displaystyle {\mathrm{거리}}_{}}$ $dij({$$displaystyle d_{i}-x_0})$에 따라 n ${\displaystyle {벡터x}_{}{}_{}}$ - ${\displaystyle {0\mathrm{}}_{}}$(1 i in n ) 사이의 도트 곱이 결정됩니다.

${\displaystyle g_{i}=(x_{i}-x_{0})\cdot(x_{j}-x_{0})=slectfrac {1}{2}+\x_{j}-x_{0}\left(\x_{j}-{0})\x_{x}\x}^{j}$

(이것은 편광 아이덴티티라고 불립니다).

특성화

n×n 행렬 A의 경우, k차원 유클리드 공간 δ에서^k $점{\displaystyle {}_{}}$ ${\displaystyle {x1\mathrm{}}_{}}$ ${\displaystyle {x2\mathrm{}}_{}\dots ,}$ $(\$1},$x_{2$},\$ldots,x_{n})$의 시퀀스는 A가 유클리드 거리 행렬인 경우 δ에서의^k A의 실현이라고 한다.일반성을 잃지 않고 ${\displaystyle {x\mathrm{}}_{}}$ 1 $=$ $($ 스타일 $x_{1$}=\$mathbf {0})$이라고 가정할 수 있다(- ${\displaystyle {x\mathrm{}}_{}}$ 1$($ 스타일 $-x_{1$})로$$ 변환하면 거리가 유지되기 때문이다).

이는 G가 최대 k개의 포지티브 등급이기 때문에 앞에서 설명한 바와 같다. G는 G $= X$ ${\displaystyle T^{}}$X ${\textsf {T}}X$$}$로 분해될 수 있는 경우에만 k개의 포지티브 등급이기 때문이다. 여기서 X는 k×n ^[7]행렬이다.게다가 X열은 δ로^k 실현된다.따라서 G를 분해하는 모든 방법을 통해 실현을 찾을 수 있습니다.두 가지 주요 접근법은 콜레스키 분해의 변형 또는 스펙트럼 분해를 사용하여 G의 주요 제곱근을 구하는 것이다.확정행렬#분해 참조.

정리문은 첫 번째 $점{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 1$({$을 구별합니다.같은 정리의 보다 대칭적인 변종은 다음과 같습니다.

다른 특성화에는 케일리-맹거 행렬식이 포함된다.특히 대칭 중공 n×n 행렬은 모든 (k+3)×(k+3) 주요 서브매트릭스가 존재하는 경우에만 실현^k 가능하다는 것을 나타낼 수 있다.즉, 모든 k+3점이 ^[9]동일한 경우에만 최종 다수의 점에 대한 반미터가 등각적으로 δ에^k 포함된다.

실제로, 정의도 또는 순위 조건은 수치 오차, 측정 소음 또는 실제 유클리드 거리에서 도달하지 못한 데이터로 인해 실패할 수 있습니다.최적으로 유사한 거리를 실현하는 포인트는 단수값 분해 또는 반무한 프로그래밍과 같은 선형 대수 도구를 사용하여 반무한 근사(및 원한다면 낮은 순위 근사)에 의해 찾을 수 있다.이를 다차원 스케일링이라고 합니다.이러한 방법의 변형은 불완전한 거리 데이터도 처리할 수 있습니다.

라벨이 부착되지 않은 데이터, 즉 특정 쌍에 할당되지 않은 거리의 집합 또는 다중 집합은 처리하기가 훨씬 더 어렵다.예를 들어, 이러한 데이터는 DNA 염기서열 분석(특히 부분 소화에서 게놈 복구) 또는 위상 검색에서 발생합니다.거리의 다중 집합이 동일한 두 점 집합을 갖는 경우(강체 변환과 반드시 관련이 있는 것은 아님) 두 점 집합을 호모메트릭이라고 합니다.n(n-1)/2 거리의 주어진 멀티셋이 주어진 차원 k에서 실현될 수 있는지 여부를 결정하는 것은 매우 어려운 일이다.한 차원에서는 이것이 턴파이크 문제로 알려져 있으며, 다항식 시간 내에 해결될 수 있을지는 미해결 문제이다.거리의 멀티셋이 오차 막대로 지정되면 1차원 케이스도 NP-hard가 됩니다.그럼에도 불구하고, 실제 알고리즘은 많은 경우에 존재한다. 예를 들어 랜덤 포인트.^[10][11][12]

표현의 고유성

유클리드 거리 행렬이 주어졌을 때, 그것을 실현하는 점의 순서는 강성 변환까지 유일하다 – 이것들은 유클리드 공간의 등각성입니다: 회전, 반사, 변환 및 그 구성.^[1]

응용 프로그램에서 거리가 정확하게 일치하지 않는 경우 Procrustes 분석은 보통 특이값 분해를 사용하여 견고한 변환을 통해 두 점 집합을 최대한 가깝게 관련짓는 것을 목표로 합니다.일반적인 유클리드 사례는 직교 프로크루스테스 문제 또는 와바 문제로 알려져 있다. (다양한 불확실성을 설명하기 위해 관측치에 가중치를 부여할 때)응용 예로는 인공위성의 방향 결정, 분자 구조 비교(화학), 단백질 구조(생물 정보학에서의 구조 정렬) 또는 뼈 구조(생물학에서의 통계적 형상 분석)가 포함된다.

「 」를 참조해 주세요.

• 인접 행렬
• 코프라네리티
• 거리 형상
• 중공 행렬
• 거리 행렬
• 유클리드 랜덤 행렬
• 유클리드 거리 행렬에 의해 임의의 차분 행렬을 근사하는 시각화 기술인 고전적인 다차원 스케일링
• 케일리-멘거 행렬식
• 반무한 매립

메모들

레퍼런스

• Dokmanic, Ivan; Parhizkar, Reza; Ranieri, Juri; Vetterli, Martin (2015). "Euclidean Distance Matrices: Essential theory, algorithms, and applications". IEEE Signal Processing Magazine. 32 (6): 12–30. arXiv:1502.07541. doi:10.1109/MSP.2015.2398954. ISSN 1558-0792. S2CID 8603398.
• James E. Gentle (2007). Matrix Algebra: Theory, Computations, and Applications in Statistics. Springer-Verlag. p. 299. ISBN 978-0-387-70872-0.
• So, Anthony Man-Cho (2007). A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions (PDF) (PhD).
• Liberti, Leo; Lavor, Carlile; Maculan, Nelson; Mucherino, Antonio (2014). "Euclidean Distance Geometry and Applications". SIAM Review. 56 (1): 3–69. arXiv:1205.0349. doi:10.1137/120875909. ISSN 0036-1445. S2CID 15472897.
• Alfakih, Abdo Y. (2018). Euclidean Distance Matrices and Their Applications in Rigidity Theory. Cham: Springer International Publishing. doi:10.1007/978-3-319-97846-8. ISBN 978-3-319-97845-1.