Евклидова матрица расстояний

В математике евклидова матрица расстояний — это размера n × n матрица , представляющая расстояние между набором из n точек в евклидовом пространстве .За баллы $x_{1},x_{2},\ldots ,x_{n}$ в k -мерном пространстве ℝ ^к , элементы их евклидовой матрицы расстояний A представляют собой квадраты расстояний между ними.То есть

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

где $\|\cdot \|$ обозначает евклидову норму на ℝ ^к .

$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}}$

В контексте (не обязательно евклидовых) матриц расстояний элементы обычно определяются непосредственно как расстояния, а не их квадраты.Однако в евклидовом случае квадраты расстояний используются, чтобы избежать вычисления квадратных корней и упростить соответствующие теоремы и алгоритмы.

Матрицы евклидовых расстояний тесно связаны с матрицами Грама (матрицами скалярных произведений , описывающими нормы векторов и углы между ними).Последние легко анализируются методами линейной алгебры .Это позволяет охарактеризовать матрицы евклидовых расстояний и восстановить точки. $x_{1},x_{2},\ldots ,x_{n}$ которые это осознают.Реализация, если она существует, уникальна с точностью до жестких преобразований , то есть сохраняющих расстояние преобразований евклидова пространства ( поворотов , отражений , перемещений ).

В практических приложениях расстояния представляют собой зашумленные измерения или получаются из произвольных оценок несходства (не обязательно метрических ).Целью может быть визуализация таких данных с помощью точек евклидова пространства, чья матрица расстояний максимально приближает заданную матрицу несходства — это известно как многомерное масштабирование .В качестве альтернативы, учитывая два набора данных, уже представленных точками в евклидовом пространстве, можно задаться вопросом, насколько они похожи по форме, то есть насколько тесно они могут быть связаны с помощью преобразования, сохраняющего расстояние — это анализ Прокруста .Некоторые расстояния также могут отсутствовать или быть немаркированными (в виде неупорядоченного набора или мультимножества вместо матрицы), что приводит к более сложным алгоритмическим задачам, таким как проблема реализации графа или проблема магистрали (для точек на линии).

Характеристики

Поскольку евклидово расстояние является метрикой , матрица A обладает следующими свойствами.

• Все элементы на диагонали A равны нулю (т.е. это пустая матрица ); следовательно, равен нулю след A .
• A симметричен т.е. ( $a_{ij}=a_{ji}$).
• ${\sqrt {a_{ij}}}\leq {\sqrt {a_{ik}}}+{\sqrt {a_{kj}}}$ (по неравенству треугольника )
• $a_{ij}\geq 0$

В размерности k евклидова матрица расстояний имеет ранг меньше или равный k +2 . Если точки $x_{1},x_{2},\ldots ,x_{n}$ находятся в общем положении , ранг равен min( n , k + 2).

Расстояния можно уменьшить в любой степени, чтобы получить другую евклидову матрицу расстояний. То есть, если $A=(a_{ij})$ является евклидовой матрицей расстояний, тогда $({a_{ij}}^{s})$ является евклидовой матрицей расстояний для каждого 0< s <1 .

Связь с матрицей Грама

Матрица Грама последовательности точек $x_{1},x_{2},\ldots ,x_{n}$ в k -мерном пространстве ℝ ^к это размера n × n матрица $G=(g_{ij})$ их скалярных произведений (здесь точка $x_{i}$ рассматривается как вектор от 0 до этой точки):

$g_{ij}=x_{i}\cdot x_{j}=\|x_{i}\|\|x_{j}\|\cos \theta$, где $\theta$ угол между вектором $x_{i}$ и $x_{j}$.

В частности

$g_{ii}=\|x_{i}\|^{2}$ это квадрат расстояния $x_{i}$ от 0 .

Таким образом, матрица Грама описывает нормы и углы векторов (от 0 до) $x_{1},x_{2},\ldots ,x_{n}$.

Позволять $X$ — матрица размера k × n, содержащая $x_{1},x_{2},\ldots ,x_{n}$ как столбцы.Затем

$G=X^{\textsf {T}}X$, потому что $g_{ij}=x_{i}^{\textsf {T}}x_{j}$ (видя $x_{i}$ как вектор-столбец).

Матрицы, которые можно разложить как $X^{\textsf {T}}X$, то есть матрицы Грама некоторой последовательности векторов (столбцы $X$), хорошо понятны — это именно положительные полуопределенные матрицы .

Чтобы связать матрицу евклидовых расстояний с матрицей Грама, заметим, что

$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}$

То есть нормы и углы определяют расстояния.Обратите внимание, что матрица Грамма содержит дополнительную информацию: расстояния от 0 .

И наоборот, расстояния $d_{ij}$ между парами из n +1 точек $x_{0},x_{1},\ldots ,x_{n}$ определить скалярное произведение между n векторами $x_{i}-x_{0}$ ( 1≤ i ≤ n ):

$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})$

(это известно как поляризационная идентичность ).

Характеристики

Для размера n × n матрицы A последовательность точек $x_{1},x_{2},\ldots ,x_{n}$ в k -мерном евклидовом пространстве ℝ ^к называется реализацией A ​ в ℝ ^к если A — их евклидова матрица расстояний.Без ограничения общности можно предположить, что $x_{1}=\mathbf {0}$ (поскольку перевод выполнен $-x_{1}$ сохраняет дистанцию).

Теорема  ( критерий Шенберга , независимо показано Young & Householder ) — Симметричная полая размера n × n матрица A с вещественными элементами допускает реализацию в ℝ ^к тогда и только тогда, когда ( n -1)×( n -1) матрица $G=(g_{ij})_{2\leq i,j\leq n}$ определяется

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

положительно полуопределен и имеет ранг не выше k .

Это следует из предыдущего обсуждения, поскольку G положительно полуопределена ранга не выше k тогда и только тогда, когда ее можно разложить как $G=X^{\textsf {T}}X$ где X — матрица размера k × n . Более того, столбцы X дают реализацию в ℝ ^к .Следовательно, любой метод разложения G позволяет найти реализацию.Двумя основными подходами являются варианты разложения Холецкого или использование спектрального разложения для нахождения главного квадратного корня из G , см. Определенная матрица#Разложение .

В формулировке теоремы выделяется первый пункт $x_{1}$. Более симметричный вариант той же теоремы следующий:

Следствие — Симметричная полая размера n × n матрица A с вещественными элементами допускает реализацию тогда и только тогда, когда A отрицательно полуопределен на гиперплоскости $H=\{v\in \mathbf {R} ^{n}\colon e^{\textsf {T}}v=0\}$, то есть

$v^{\textsf {T}}Av\leq 0$ для всех $v\in \mathbf {R} ^{n}$ такой, что $\textstyle \sum _{i=1}^{n}v_{i}=0$.

Другие характеристики включают определители Кэли-Менгера .В частности, это позволяет показать, что симметричная полая матрица размера n × n реализуема в ℝ ^к тогда и только тогда, когда каждая ( k +3) × ( k +3) главная подматрица является .Другими словами, полуметрика в конечном числе точек изометрически вкладывается в ℝ ^к тогда и только тогда, когда каждые k +3 точки есть.

На практике условия определенности или ранга могут не выполняться из-за числовых ошибок, шума в измерениях или из-за того, что данные не получены с фактических евклидовых расстояний.Точки, которые реализуют оптимально одинаковые расстояния, затем могут быть найдены с помощью полуопределенной аппроксимации (и аппроксимации низкого ранга, если желательно) с использованием линейных алгебраических инструментов, таких как разложение по сингулярным значениям или полуопределенное программирование .Это известно как многомерное масштабирование .Варианты этих методов также могут работать с неполными данными о расстоянии.

Гораздо сложнее иметь дело с немаркированными данными, то есть набором или мультимножеством расстояний, не присвоенных конкретным парам.Такие данные возникают, например, при секвенировании ДНК (в частности, восстановлении генома из частичного переваривания ) или фазовом извлечении .Два набора точек называются гомометрическими, если они имеют одинаковый мультимножество расстояний (но не обязательно связаны жестким преобразованием).Решение о том, может ли данный мультинабор из n ( n -1)/2 расстояний быть реализован в данном измерении k, является сильно NP-трудным .В одном измерении это известно как проблема магистрали; остается открытым вопрос, можно ли ее решить за полиномиальное время.Когда мультинабор расстояний задается с погрешностями, даже одномерный случай является NP-трудным .Тем не менее, практические алгоритмы существуют для многих случаев, например, для случайных точек.

Уникальность представлений

Учитывая евклидову матрицу расстояний, последовательность точек, реализующих ее, уникальна с точностью до жестких преобразований — это изометрии евклидова пространства: вращения , отражения , перемещения и их композиции.

Теорема — Позволять $x_{1},x_{2},\ldots ,x_{n}$ и $y_{1},y_{2},\ldots ,y_{n}$ — две последовательности точек в k -мерном евклидовом пространстве ℝ ^к .Расстояния $\|x_{i}-x_{j}\|$ и $\|y_{i}-y_{j}\|$ равны (для всех 1≤ i , j ≤ n ) тогда и только тогда, когда существует жесткое преобразование ℝ ^к картографирование $x_{i}$ к $y_{i}$ (для всех 1≤ i ≤ n ).

show Доказательство

Rigid transformations preserve distances so one direction is clear.Suppose the distances $\|x_{i}-x_{j}\|$ and $\|y_{i}-y_{j}\|$ are equal.Without loss of generality we can assume $x_{1}=y_{1}={\textbf {0}}$ by translating the points by $-x_{1}$ and $-y_{1}$, respectively.Then the (n-1)×(n-1) Gram matrix of remaining vectors $x_{i}=x_{i}-x_{1}$ is identical to the Gram matrix of vectors $y_{i}$ (2≤i≤n).That is, $X^{\textsf {T}}X=Y^{\textsf {T}}Y$, where X and Y are the k×(n-1) matrices containing the respective vectors as columns.This implies there exists an orthogonal k×k matrix Q such that QX=Y, see Definite symmetric matrix#Uniqueness up to unitary transformations.Q describes an orthogonal transformation of ℝk (a composition of rotations and reflections, without translations) which maps $x_{i}$ to $y_{i}$ (and 0 to 0).The final rigid transformation is described by $T(x)=Q(x-x_{1})+y_{1}$.

В приложениях, когда расстояния не совпадают точно, анализ Прокруста направлен на то, чтобы связать два набора точек как можно ближе с помощью жестких преобразований, обычно с использованием разложения по сингулярным значениям .Обычный евклидов случай известен как ортогональная проблема Прокруста или проблема Вахбы (когда наблюдения взвешиваются для учета различных неопределенностей).Примеры приложений включают определение ориентации спутников, сравнение структуры молекул (в хеминформатике ), структуры белка ( структурное выравнивание в биоинформатике ) или структуры кости ( статистический анализ формы в биологии).

См. также

• Матрица смежности
• Компланарность
• Геометрия расстояния
• Полая матрица
• Матрица расстояний
• Евклидова случайная матрица
• Классическое многомерное масштабирование — метод визуализации, аппроксимирующий произвольную матрицу несходства евклидовой матрицей расстояний.
• Определитель Кэли – Менгера
• Полуопределенное вложение

Ссылки

• Докманич, Иван; Пархизкар, Реза; Раньери, Юри; Веттерли, Мартин (2015). «Евклидовы матрицы расстояний: основная теория, алгоритмы и приложения». Журнал обработки сигналов IEEE . 32 (6): 12–30. arXiv : 1502.07541 . дои : 10.1109/MSP.2015.2398954 . ISSN   1558-0792 . S2CID   8603398 .
• Джеймс Э. Джентл (2007). Матричная алгебра: теория, вычисления и приложения в статистике . Спрингер-Верлаг . п. 299. ИСБН  978-0-387-70872-0 .
• Итак, Энтони Ман-Чо (2007). Подход полуопределенного программирования к проблеме реализации графов: теория, приложения и расширения (PDF) (доктор философии).
• Либерти, Лео; Лавор, Карлайл; Макулан, Нельсон; Мучерино, Антонио (2014). «Евклидова дистанционная геометрия и приложения». Обзор СИАМ . 56 (1): 3–69. arXiv : 1205.0349 . дои : 10.1137/120875909 . ISSN   0036-1445 . S2CID   15472897 .
• Альфаких, Абдо Ю. (2018). Евклидовы матрицы расстояний и их приложения в теории жесткости . Чам: Международное издательство Springer. дои : 10.1007/978-3-319-97846-8 . ISBN  978-3-319-97845-1 .