Чисто вращательное совпадение наименьших квадратов

Может ли кто-нибудь порекомендовать метод для следующей задачи наименьших квадратов:

найти который минимизирует: , где - унитарное (вращение) матрица. $R \in \mathbb{R}^{3 \times 3}$ $\sum\limits_{i=0}^N (Rx_i - b_i)^2 \rightarrow \min$ $R$

Я мог бы получить приблизительное решение, минимизировав $\sum\limits_{i=0}^N (Ax_i - b_i)^2 \rightarrow \min$ (произвольный $A \in \mathbb{R}^{3 \times 3}$ ), приняв матрица $A$ и:

вычисление SVD: $A = U \Sigma V^T$ , отбрасывание $\Sigma$ и аппроксимация $R \approx U V^T$
Вычисление полярного разложения: $A = U P$ , отбрасывание симметричного (и положительно определенного в моем случае) только по шкале $P$ и приближение $R \approx U$

Я также мог бы использовать QR-разложение, но оно не было бы изометрическим (это зависело бы от выбора системы координат).

Кто-нибудь знает способ сделать это, хотя бы приблизительно, но с лучшим приближением, чем два метода выше?

linear-algebra least-squares svd Сергей Мигдальский
источник

Я использовал алгоритм Kabsch для подобной проблемы, которая, по существу , метод SVD вы упомянули en.wikipedia.org/wiki/Kabsch_algorithm , если я не ошибаюсь метод SVD минимизирует уравнение, я не уверен , что вы подразумеваете под " лучший метод?

isti_spl

OMG я только что получил тот же ответ IRL. Благодаря! Очевидно, что drop работает, если только отрицателен, и в этом случае оптимальное вращение включает отражение (и любое вращение одинаково плохо). Это технически отвечает на вопрос, однако, кто-нибудь знает более дешевый метод, чем вычисление SVD? Это SVD 3x3, но мне нужно сделать много (это для моделирования FEM, и проблема вычисляется для каждого FE). Также, эта проблема, очевидно, называется проблемой Вахбы, и она, очевидно, появляется в аэронавтике, чтобы определить ремесло. ориентации.

Σ

$\Sigma$

d e t (U V^{T})

$det(UV^T)$

Сергей Мигдальский

Я видел эти связанные проблемы: scicomp.stackexchange.com/questions/7552/…

isti_spl

и вот этот: dsp.stackexchange.com/questions/1911/…

isti_spl

@isti_spl: Не могли бы вы перенести свой комментарий в ответ?

Джефф Оксберри

Ответы:

Эта проблема называется проблемой Вахбы , один алгоритм для нее называется алгоритмом Кабша , а более поздний, более популярный, называется методом Davenport q . По-видимому, он использовался и изучался в аэронавтике для определения ориентации корабля. Есть много отзывов о методах.

Остерегайтесь, что лучшая подгонка может включать отражение.

Метод Кабша вычисляет ковариационную матрицу 3x3 SVD и удаляет член (по модулю одно отражение, которое обычно учитывается путем отрицания последнего столбца в SVD). Очень просто обобщить на другое количество измерений. $\Sigma$ $U$

Метод Davenport q часто рекламируется как первый практический алгоритм, возможно, кто-то может прокомментировать, почему. Он также создает ковариационную матрицу 3x3, но затем параметризует матрицу вращения как функцию кватерниона, и возникает проблема вычисления собственного вектора максимального значения симметричной матрицы 4x4.

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

Шустер также разработал и проанализировал некоторые варианты итерационных алгоритмов.

Сергей Мигдальский
источник

Для некоторой истории в аэрокосмическом сообществе, прочитайте « Скромные проблемы » Маркли.

Дэмиен