Correspondência puramente rotativa de mínimos quadrados

Alguém poderia recomendar um método para o seguinte problema dos mínimos quadrados:

encontre que minimize: , em que é uma unidade (rotação) matriz. $R \in \mathbb{R}^{3 \times 3}$ $\sum\limits_{i=0}^N (Rx_i - b_i)^2 \rightarrow \min$ $R$

Eu poderia obter uma solução aproximada minimizando $\sum\limits_{i=0}^N (Ax_i - b_i)^2 \rightarrow \min$ (arbitrário $A \in \mathbb{R}^{3 \times 3}$ ), usando matriz $A$ e:

computação SVD: $A = U \Sigma V^T$ , largando $\Sigma$ e aproximando $R \approx U V^T$
computando a decomposição polar: $A = U P$ , diminuindo apenas a escala simétrica (e positiva definida no meu caso) $P$ e aproximando $R \approx U$

Eu também poderia usar a decomposição QR, mas não seria isométrica (dependeria da escolha do sistema de coordenadas).

Alguém sabe uma maneira de fazer isso, pelo menos aproximadamente, mas com melhor aproximação do que os dois métodos acima?

linear-algebra least-squares svd Sergiy Migdalskiy
fonte

Usei o algoritmo de Kabsch para um problema semelhante, que é essencialmente o método SVD que você mencionou en.wikipedia.org/wiki/Kabsch_algorithm, se não estou errado, o método svd minimiza a equação, não sei o que você quer dizer com ' melhor 'método?

Isti_spl 20/01

OMG Acabei de receber a mesma resposta IRL. Obrigado! Aparentemente, remover funciona a menos que seja negativo; nesse caso, a rotação ideal inclui uma reflexão (e qualquer rotação é igualmente ruim). Isso tecnicamente responde à pergunta, no entanto, alguém sabe de um método mais barato do que calcular SVD? É um SVD 3x3, mas eu preciso fazer muitos deles (isso é para simulação FEM, e o problema é calculado para cada FE). Além disso, o problema é aparentemente chamado de problema de Wahba e aparentemente aparece na aeronáutica para determinar uma embarcação. orientação.

Σ

$\Sigma$

d e t (U V^{T})

$det(UV^T)$

Sergiy Migdalskiy

Eu já vi esses problemas relacionados: scicomp.stackexchange.com/questions/7552/…

isti_spl 20/01/14

e este: dsp.stackexchange.com/questions/1911/…

isti_spl 20/01/14

@isti_spl: Você poderia migrar seu comentário para uma resposta?

Geoff Oxberry

Respostas:

O problema é chamado de problema de Wahba , um algoritmo para ele é chamado algoritmo de Kabsch , e o posterior mais popular é chamado de método Davenport q . Aparentemente, é usado e estudado em aeronáutica para determinar uma orientação de embarcação. Existem muitas críticas sobre os métodos.

Cuidado que o melhor ajuste pode incluir reflexão.

O método Kabsch calcula uma matriz de covariância 3x3 SVD e descarta o termo (módulo uma reflexão, que geralmente é explicado pela negação da última coluna de no SVD). É muito simples generalizar para outro número de dimensões. $\Sigma$ $U$

O método Davenport q é frequentemente apontado como o primeiro algoritmo prático, talvez alguém possa comentar o porquê. Ele também constrói uma matriz de covariância 3x3, mas depois parametriza a matriz de rotação em função de um quaternion, e o problema passa a ser o cálculo do vetor autovalor de valor próprio máximo de uma matriz 4x4 simétrica.

(Algumas das) implementações numéricas mais populares são chamadas QUEST e FOMA . Esses métodos geralmente são uma variação do tema de calcular o valor próprio máximo escrevendo e otimizando o polinômio característico (um quártico) e resolvendo-o analiticamente (cálculos bastante envolvidos, passando por fórmulas de Kardano) ou com iteração de Newton.

Schuster também desenvolveu e analisou algumas variantes iterativas de algoritmos.

Sergiy Migdalskiy
fonte

Para um pouco de história na comunidade aeroespacial, leia os Problemas Humildes de Markley.

Damien