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

11

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

найти который минимизирует: , где R - унитарное (вращение) матрица.RR3×3i=0N(Rxibi)2minR

Я мог бы получить приблизительное решение, минимизировав i=0N(Axibi)2min (произвольный AR3×3 ), приняв матрица A и:

  • вычисление SVD: A=UΣVT , отбрасывание Σ и аппроксимация RUVT
  • Вычисление полярного разложения: A=UP , отбрасывание симметричного (и положительно определенного в моем случае) только по шкале P и приближение RU

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

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

Сергей Мигдальский
источник
4
Я использовал алгоритм Kabsch для подобной проблемы, которая, по существу , метод SVD вы упомянули en.wikipedia.org/wiki/Kabsch_algorithm , если я не ошибаюсь метод SVD минимизирует уравнение, я не уверен , что вы подразумеваете под " лучший метод?
isti_spl
2
OMG я только что получил тот же ответ IRL. Благодаря! Очевидно, что drop работает, если только отрицателен, и в этом случае оптимальное вращение включает отражение (и любое вращение одинаково плохо). Это технически отвечает на вопрос, однако, кто-нибудь знает более дешевый метод, чем вычисление SVD? Это SVD 3x3, но мне нужно сделать много (это для моделирования FEM, и проблема вычисляется для каждого FE). Также, эта проблема, очевидно, называется проблемой Вахбы, и она, очевидно, появляется в аэронавтике, чтобы определить ремесло. ориентации. д е т ( U V T )Σdet(UVT)
Сергей Мигдальский
Я видел эти связанные проблемы: scicomp.stackexchange.com/questions/7552/…
isti_spl
и вот этот: dsp.stackexchange.com/questions/1911/…
isti_spl
@isti_spl: Не могли бы вы перенести свой комментарий в ответ?
Джефф Оксберри

Ответы:

9

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

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

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

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

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

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

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