Матрица евклидовых расстояний - Euclidean distance matrix

В математика, а Матрица евклидовых расстояний является п×п матрица представляющий интервал набора п точки в Евклидово пространство.Для очков ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ в k-мерное пространство ℝ^k, элементы их матрицы евклидовых расстояний А даются квадратами расстояний между ними.

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

куда ${\displaystyle \|\cdot \|}$ обозначает Евклидова норма на ℝ^k.

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

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

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

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

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

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

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

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

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

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

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

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

Особенно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

является положительно полуопределенный и имеет классифицировать в большинстве k.

Это следует из предыдущего обсуждения, потому что грамм положительно полуопределенный ранг не выше k тогда и только тогда, когда его можно разложить как ${\displaystyle G=X^{\textsf {T}}X}$ куда Икс является k×п матрица.^[7]Кроме того, столбцы Икс дать реализацию в ℝ^k.Поэтому любой способ разложить грамм позволяет найти реализацию. Два основных подхода - это варианты Разложение Холецкого или используя спектральные разложения найти главный квадратный корень из грамм, видеть Определенная матрица # Разложение.

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

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

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

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

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

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

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

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

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

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

Жесткие преобразования сохраняют расстояния, поэтому одно направление остается четким. ${\displaystyle \|x_{i}-x_{j}\|}$ и ${\displaystyle \|y_{i}-y_{j}\|}$ равны. Без ограничения общности можно считать ${\displaystyle x_{1}=y_{1}={\textbf {0}}}$ переводя точки на ${\displaystyle -x_{1}}$ и ${\displaystyle -y_{1}}$соответственно. (п-1)×(п-1) Матрица Грама оставшихся векторов ${\displaystyle x_{i}=x_{i}-x_{1}}$ идентична матрице Грама векторов ${\displaystyle y_{i}}$ (2≤я≤п).То есть, ${\displaystyle X^{\textsf {T}}X=Y^{\textsf {T}}Y}$, куда Икс и Y являются k×(п-1) матрицы, содержащие соответствующие векторы в виде столбцов. Это означает, что существует ортогональный k×k матрица Q такой, что QX=Y, видеть Определенная симметричная матрица # Единственность с точностью до унитарных преобразований.Q описывает ортогональное преобразование из ℝk (композиция вращений и отражений без переводов), которая отображает ${\displaystyle x_{i}}$ к ${\displaystyle y_{i}}$ (и 0 к 0Окончательное жесткое преобразование описывается формулой ${\displaystyle T(x)=Q(x-x_{1})+y_{1}}$.

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

Смотрите также

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

Примечания

1. Dokmanic et al. (2015)
2. Итак (2007)
3. Маэхара, Хироши (2013). «Евклидовы вложения конечных метрических пространств». Дискретная математика. 313 (23): 2848–2856. Дои:10.1016 / j.disc.2013.08.029. ISSN  0012-365X. Теорема 2.6.
4. Итак (2007), Теорема 3.3.1, с. 40
5. Шенберг, И. Дж. (1935). «Замечания к статье Мориса Фреше» Sur La Definition Axiomatique D'Une Classe D'Espace Vectoriellement, применимый к Sur L'Espace De Hilbert"". Анналы математики. 36 (3): 724–732. Дои:10.2307/1968654. ISSN  0003-486X. JSTOR  1968654.
6. Янг, Гейл; Домохозяин, А.С. (1938-03-01). «Обсуждение набора точек с точки зрения их взаимных расстояний». Психометрика. 3 (1): 19–22. Дои:10.1007 / BF02287916. ISSN  1860-0980. S2CID  122400126.
7. Итак (2007), Теорема 2.2.1, с. 10
8. Итак (2007), Следствие 3.3.3, с. 42
9. Менгер, Карл (1931). «Новые основы евклидовой геометрии». Американский журнал математики. 53 (4): 721–745. Дои:10.2307/2371222. JSTOR  2371222.
10. Лемке, Пол; Skiena, Steven S .; Смит, Уоррен Д. (2003). «Реконструкция множеств по промежуточным расстояниям». В Аронов, Борис; Басу, Саугата; Пах, Янош; Шарир, Миха (ред.). Дискретная и вычислительная геометрия. 25. Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 597–631. Дои:10.1007/978-3-642-55566-4_27. ISBN  978-3-642-62442-1.
11. Хуанг, Шуай; Докманич, Иван (2020). «Восстановление наборов точек из распределений расстояний». arXiv:1804.02465 [cs.DS ].
12. Джаганатан, Кишор; Хассиби, Бабак (2012). «Восстановление целых чисел по попарным расстояниям». arXiv:1212.2386 [cs.DM ].

Рекомендации

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