Построение системы координат по набору расстояний

Введение

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

Допустим, у нас имеется (n > 2) точек и известны все расстояния между ними. Потенциальная мерность пространства равна (n-1). Надо определить, пространству какой мерности принадлежат заданные точки, а также координаты точек в данном пространстве.

1. Преобразование девиации

Пусть задана некая симметричную матрицу М размерности N с нулевым следом (элементы главной диагонали равны нулю). Нам надо определить преобразование в некоторую новую матрицу U. При этом значения исходной матрицы должны рассчитываться из новой по правилам сложения расстояний:



Тогда значения матрицы M можно выразить через спектр U как взвешенную сумму разности квадратов компонент собственных векторов:



Здесь — набор собственных чисел матрицы U, а — матрица собственных векторов, соответствующих собственным числам. Длина векторов нормирована к 1.
Общим видом матрицы U, удовлетворяющим условию (1.1), является выражение:



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



Подставляя (1.3) в (1.4) с учетом симметрии M, получаем тождество:



из которого определяем искомые выражения для вектора и константы:




Таким образом вектором в (1.3) является вектор средних значений строки (столбца) исходной матрицы (в терминах графов — средняя кардинальность/степень вершины графа), а константой — среднее значение матрицы в целом (средняя степень вершин всего графа):



Преобразование (1.3') назовем преобразованием девиации, поскольку оно отражает отклонение (девиацию) значений исходной матрицы от средних значений. Результат преобразования будем называть матрицей девиации.

2. Свойства матрицы девиации

Матрица является вырожденной (нулевой детерминант и одно из собственных значений) — следствие требования лапласиановости.
Элементы главной диагонали девиации отражают средние значения исходной матрицы:



След девиации связан со средним значением исходной матрицы и может быть выражен через сумму собственных значений:



Произведение собственных чисел пропорционально потенциалу девиации — ненулевому минору матрицы:



Девиация является обратимой. На основании матрицы девиации можно восстановить исходную:

3. Матрица Грина, собственная система координат

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

Исходный набор расстояний представим в виде симметричной матрицы квадратов расстояний между точками. Обозначим данную матрицу как D2, где двойка означает квадрат. Применение операции девиации к матрице квадратов расстояний дает матрицу Грина G:



Спектр матрицы Грина обладает следующими свойствами:

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

Таким образом спектр матрицы Грина определяет собственную систему координат исходного набора точек. Вес каждой координаты определяется значением спектра (собственным числом). Центр новой системы координат называется центроидом. На главной диагонали матрицы Грина расположены квадраты расстояния от центроида до вершин:



Сумма всех таких расстояний (след) определяет средний радиус множества R2. Данный радиус равен сумме значений спектра и связан со средним значением исходной матрицы расстояний в соответствии с формулой (2.2):



Центроид набора минимизирует средний радиус набора. То есть для любого другого положения центроида средний радиус набора будет иметь большее значение. Добавление самого центроида в исходный набор точек не изменяет спектр, поскольку центроид нового набора совпадает со старым.

4. Спектры некоторых наборов

Спектры трех вершин (треугольники)

У нас в руках появился молоток. Ищем гвозди.
Для одной/двух точек строить матрицу Грина смысла особого нет. Две нетождественные точки всегда принадлежат одной прямой, то есть одномерному пространству.
А вот для трех точек уже появляются варианты. Самый простой случай — вершины равностороннего треугольника. Если длина стороны равна 1, то матрица Грина будет иметь вид:



След данной матрицы равен 1, а потенциал (1/3)^2 — (1/6)^2 = 1/9 — 1/36 = 1/12.
Считаем спектр (в скобках приведены квадраты расстояний между точками):



Здесь слева показаны собственные значения спектра, а справа — соответствующие им значения векторов (координат).
Видим, что:

• Спектр имеет два значения. Это объяснимо — невырожденный треугольник всегда принадлежит 2-мерному пространству (плоскости).
• Оба собственных значения равны. Это является следствием симметрии равностороннего треугольника.

Проверим свойства спектра: сумма собственных чисел равна 1, произведение — 1/2 * 1/2 = 1/4 = 1/12 * 3. Все верно.

Попутно заметим, что спектр трех вершин связан с площадью образуемого ими треугольника (разновидность формулы Герона):



Соответственно квадрат площади равностороннего 1-треугольника равен 3/4 * 1/4 = 3/16.

Движемся дальше. Если точки принадлежат одной прямой, то спектр должен содержать только одно значение.
Рассчитаем значение спектра для трех точек отрезка (две по краям и одна посередине) . Получаем:



Действительно, спектр содержит только одну компоненту. Центроид находится посередине отрезка, как и ожидалось.

Зададим каверзный вопрос — какому пространству принадлежит невозможный треугольник, то есть тот, в котором нарушено неравенство треугольника?


Если спектр содержит отрицательные значения, то это означает, что в евклидовом пространстве набор точек с такими характеристиками реализоваться не может,- координаты точек становятся мнимыми. Можно использовать данное свойство спектра для проверки валидности матрицы расстояний.

Передышка

Мы определили преобразование девиации и применили его к матрице квадратов расстояний. Получившаяся матрица Грина отражает свойства пространства исходного набора точек.

Отметим, что матрица квадратов расстояний эквивалентна матрице резистивных расстояний. Соответственно матрица Грина является обратной матрицей по отношению к матрице Кирхгофа (лапласиана графа).

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

Продолжение...