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

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

{\ displaystyle {\ begin {align} A & = (a_ {ij}); \\ a_ {ij} & = d_ {ij} ^ {2} \; = \; \ lVert x_ {i} -x_ {j} \ rВерт ^ {2} \ конец {выровнено}}}

где обозначает евклидову норму на $ℝ$ $k$ . ${\ Displaystyle \ | \ 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}$

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

Свойства [ править ]

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

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

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

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

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

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

g_{ij}=x_{i}\cdot x_{j}=\|x_{i}\|\|x_{j}\|\cos \theta

, где - угол между вектором и .

\theta

x_{i}

x_{j}

В частности

g_{ii}=\|x_{i}\|^{2}

это квадрат расстояния от 0 .

x_{i}

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

Позвольте быть $k$ $\times$ $n$ матрица, содержащая как столбцы. потом $X$ $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 .

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

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

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

Характеристики [ править ]

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

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

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

является неотрицательно и имеет ранг в большинстве $к$ .

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

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

Следствие ^[8] - симметричный полая $п \times п$ матрица с вещественными элементами допускает реализацию , если и только если полуотрицательно на гиперплоскости , то есть $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 \times n$ реализуема в $ℝ k$ тогда и только тогда, когда каждая главная подматрица $(k +3) \times (k +3)$ реализуется . Другими словами, полуметрика на конечном числе точек изометрически вложима в $ℝ$ $k$ тогда и только тогда, когда все $k$ $+3$ точки вложены . ^[9]

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

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

[DPRZ-1] Dokmanic et al. (2015)

[2] Итак (2007)

[3] Maehara, Hiroshi (2013). «Евклидовы вложения конечных метрических пространств» . Дискретная математика . 313 (23): 2848–2856. DOI : 10.1016 / j.disc.2013.08.029 . ISSN 0012-365X . Теорема 2.6.

[4] So (2007) , теорема 3.3.1, стр. 40

[5] Шенберг, IJ (1935). «Замечания к статье Мориса Фреше« Sur La Definition Axiomatique D'Une Classe D'Espace Vectoriellement, применимый к Sur L'Espace De Hilbert » ». Анналы математики . 36 (3): 724–732. DOI : 10.2307 / 1968654 . ISSN 0003-486X . JSTOR 1968654 .

[6] Янг, Гейл; Хаусхолдер, А.С. (1938-03-01). «Обсуждение набора точек с точки зрения их взаимных расстояний». Психометрика . 3 (1): 19–22. DOI : 10.1007 / BF02287916 . ISSN 1860-0980 . S2CID 122400126 .

[7] So (2007) , теорема 2.2.1, стр. 10

[8] So (2007) , следствие 3.3.3, стр. 42

[9] Менгер, Карл (1931). «Новые основы евклидовой геометрии». Американский журнал математики . 53 (4): 721–745. DOI : 10.2307 / 2371222 . JSTOR 2371222 .

[10] Лемке, Пол; Skiena, Steven S .; Смит, Уоррен Д. (2003). «Реконструкция множеств с промежуточных расстояний». В Аронов, Борис; Басу, Саугата; Пах, Янош; Шарир, Миха (ред.). Дискретная и вычислительная геометрия . 25 . Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 597–631. DOI : 10.1007 / 978-3-642-55566-4_27 . ISBN 978-3-642-62442-1.

[11] Хуанг, Шуай; Докманич, Иван (2020). «Восстановление наборов точек из распределений расстояний». arXiv : 1804.02465 [ cs.DS ].

[12] Jaganathan, Кишор; Хассиби, Бабак (2012). «Восстановление целых чисел по попарным расстояниям». arXiv : 1212.2386 [ cs.DM ].

[1]