Czysto obrotowe dopasowanie najmniejszych kwadratów

11

Czy ktoś mógłby polecić metodę dla następującego problemu najmniejszych kwadratów:

znajdź który minimalizuje: , gdzie jest jednostką (obrót) matryca.N i = 0 ( R x i - b i ) 2minRR3×3i=0N(Rxibi)2minR

Mógłbym uzyskać przybliżone rozwiązanie, minimalizując (arbitralne A \ in \ mathbb {R} ^ {3 \ times 3} ), biorąc macierz A i:AR3×3i=0N(Axibi)2minAR3×3A

  • obliczanie SVD: A=UΣVT , upuszczanie Σ i przybliżanie RUVT
  • obliczanie rozkładu biegunowego: A=UP , upuszczanie symetryczne tylko w skali (i dodatnie w moim przypadku) P i przybliżanie RU

Mógłbym również użyć rozkładu QR, ale nie byłby izometryczny (zależałoby od wyboru układu współrzędnych).

Czy ktoś wie, jak to zrobić, przynajmniej w przybliżeniu, ale z lepszym przybliżeniem niż dwie powyższe metody?

Sergiy Migdalskiy
źródło
4
Użyłem algorytmu Kabscha do podobnego problemu, którym jest w zasadzie metoda SVD, o której wspominałeś en.wikipedia.org/wiki/Kabsch_algorytm, jeśli się nie mylę, metoda svd minimalizuje równanie, nie jestem pewien, co rozumiesz przez „ lepsza metoda?
isti_spl
2
OMG Właśnie dostałem tę samą odpowiedź IRL. Dzięki! Najwyraźniej upuszczenie działa, chyba że d e t ( U V T ) jest ujemne, w którym to przypadku optymalny obrót obejmuje odbicie (a każdy obrót jest równie zły). To technicznie odpowiada na pytanie, czy jednak ktoś wie o tańszej metodzie niż obliczanie SVD? Jest to SVD 3x3, ale muszę zrobić wiele z nich (dotyczy to symulacji MES, a problem obliczany jest dla każdego FE). Problem najwyraźniej nazywany jest problemem Wahby i najwyraźniej pojawia się w lotnictwie w celu ustalenia jednostki orientacja. Σdet(UVT)
Sergiy Migdalskiy
widziałem podobne problemy: scicomp.stackexchange.com/questions/7552/…
isti_spl
@isti_spl: Czy możesz przenieść swój komentarz do odpowiedzi?
Geoff Oxberry

Odpowiedzi:

9

Problem nazywa się problemem Wahby , jeden algorytm nazywa się algorytmem Kabscha , a później bardziej popularny nazywa się metodą Davenport q . Najwyraźniej jest wykorzystywany i badany w lotnictwie w celu określenia orientacji statku. Istnieje wiele recenzji na temat metod.

Uwaga: najlepsze dopasowanie może obejmować odbicie.

Metoda Kabscha oblicza macierz kowariancji 3x3 SVD i upuszcza wartość (odbicie modulo jeden, co zwykle jest uwzględniane przez zanegowanie ostatniej kolumny U w SVD). Uogólnienie na inną liczbę wymiarów jest bardzo proste.ΣU

Metoda q Davenporta jest często reklamowana jako pierwszy praktyczny algorytm, być może ktoś może komentować dlaczego. Konstruuje również macierz kowariancji 3x3, ale następnie parametryzuje macierz obrotu jako funkcję czwartorzędu, a problemem staje się obliczenie wektora własnego wartości maksymalnej dla symetrycznej macierzy 4x4.

(Niektóre z) najpopularniejszych implementacji numerycznych nazywane są QUEST i FOMA . Metody te są zwykle wariacją na temat obliczania maksymalnej wartości własnej przez zapisanie i optymalizację charakterystycznego wielomianu (kwartyk) i albo rozwiązywanie go analitycznie (dość skomplikowane obliczenia, przechodzenie przez formuły Kardano), albo z iteracją Newtona.

Schuster opracował również i przeanalizował niektóre warianty algorytmów iteracyjnych.

Sergiy Migdalskiy
źródło
2
Aby zapoznać się z historią społeczności lotniczej, przeczytaj Humble Problems autorstwa Markleya.
Damien