Ортогональная проблема Прокруста: матричная алгебра анализа форм

Математическая формулировка: минимизация нормы Фробениуса

Представьте два набора из n точек в 3D-пространстве, записанных как матрицы A и B размера n на 3. Перед сравнением облака точек всегда центрируются (вычитается среднее арифметическое координат, чтобы совместить их центры масс в начале координат). Задача формулируется так: найти такую ортогональную матрицу Q (размера 3x3), которая минимизирует норму Фробениуса разности ||A - B*Q||_F. Ортогональность матрицы Q гарантирует, что облако точек B будет подвергнуто только жесткому геометрическому вращению или зеркальному отражению, без искажения пропорций, сжатия или деформации (в отличие от реального мифологического Прокруста). Раскрывая квадрат нормы Фробениуса через след матрицы, задача минимизации разности математически строго сводится к задаче максимизации следа произведения: Tr(A^T * B * Q).

Аналитическое решение через SVD

Решение этой задачи потрясает своей алгебраической прямолинейностью. Сначала вычисляется матрица кросс-ковариации двух наборов точек: C = B^T * A. Затем для этой крошечной матрицы C (размером всего 3x3) выполняется Сингулярное разложение: C = U * Sigma * V^T. Теорема Шёнемана доказывает, что искомая идеальная матрица поворота Q вычисляется простым перемножением ортогональных компонентов этого сингулярного разложения: Q = U * V^T. При этом сингулярные числа (диагональная матрица Sigma) вообще не участвуют в вычислении самого вращения, они лишь определяют меру остаточного несовпадения двух фигур (ошибку Прокруста). Алгоритм работает мгновенно и всегда гарантированно находит абсолютный глобальный оптимум.

Проблема зеркальных отражений

Поскольку матрица Q получается как произведение двух ортогональных матриц, она сама является ортогональной. Однако ортогональные матрицы имеют определитель либо +1 (чистое вращение), либо -1 (вращение с зеркальным отражением). Для многих физических задач (например, при сравнении стереоизомеров в химии) зеркальное отражение недопустимо: левая перчатка не должна превращаться в правую. Чтобы запретить отражение и получить строго матрицу вращения (из группы SO(3)), алгоритм слегка модифицируется. Вычисляется определитель матрицы U*V^T. Если он равен -1, то в матрице V знак последнего столбца меняется на противоположный (что соответствует наименьшему сингулярному числу), после чего Q пересчитывается. Это гарантирует наилучшее чистое вращение в трехмерном пространстве.

Обобщенный анализ Прокруста (GPA) в биоинформатике

Если необходимо выровнять не два, а сотни или тысячи облаков точек (например, 3D-модели человеческих черепов в антропологии или траектории движения молекул в молекулярной динамике), используется Обобщенный анализ Прокруста (Generalized Procrustes Analysis, GPA). В этом случае вводится понятие среднего (консенсусного) облака точек. Алгоритм работает итеративно: сначала все формы произвольно выравниваются по первой, вычисляется средняя форма. Затем каждая индивидуальная форма по очереди выравнивается по этому среднему консенсусу (решая классическую проблему Прокруста через SVD), после чего средняя форма пересчитывается. Процесс сходится за несколько итераций, позволяя извлекать чистые морфологические различия между биологическими видами, отфильтровав все шумы, связанные с положением объектов в пространстве и ракурсом сканирования.