Implementação de matriz esparsa do filtro Kalman?

8

Eu tenho um código de modelagem baseado em Kalman Filter que desenvolvi para um aplicativo de mapeamento ionosférico regional quase em tempo real. O código assimila dados de diferentes sensores em um mapa (descrito por um conjunto de funções básicas) usando um filtro Kalman.

Estou tentando escalar isso para uma região maior e mais sensores, no entanto, a parte da álgebra matricial do Filtro Kalman está ficando muito lenta, devido às matrizes grandes (milhares de linhas / colunas) envolvidas. Eu suspeito que a melhor maneira de atacar o problema de tempo de execução é usar o fato de que essas matrizes geralmente são muito esparsas, com 80% ou mais do total de elementos zero. A razão para isso é que cada sensor possui um parâmetro de polarização estimado conjuntamente com os coeficientes do mapa. Isso aparece como um 1 na coluna para esse sensor na matriz Kalman H, com zero nas colunas para todos os outros sensores e coeficientes de mapa. Existem centenas de sensores, cada um contribuindo com 8 a 10 observações em cada época, portanto, muitos zeros.

Eu poderia analisar a implementação dos componentes do filtro Kalman usando algoritmos esparsos, especificamente multiplicação e inversão *, mas me pergunto se existe uma abordagem ainda melhor que reencaminhe o filtro Kalman de uma forma diferente, mais adequada para os casos em que as matrizes são escasso? Sei que poderia usar um filtro Kalman de conjunto ou algo semelhante, mas, se possível, gostaria de manter a otimização do filtro Kalman linear puro; o volume total de dados não é proibitivo, apenas as grandes matrizes esparsas que resultam do modelo linear.

Em termos de implementação, isso é feito em IDL, no entanto, a álgebra da matriz principal é feita por meio de chamadas para bibliotecas externas otimizadas de LA (especificamente ATLAS).

* Eu sei que uma implementação ideal do filtro Kalman evita inversão e, ao invés disso, usa uma decomposição UD. Estou pensando em tentar implementar algo assim, para que possa ser a resposta, mas estou buscando se há uma solução melhor, dada a escassez das matrizes.

Bogdanovist
fonte
1
Eu acho que essa pergunta seria melhor se você incluísse a quantidade mínima de matemática para descrever o problema. Muitas pessoas aqui estão familiarizadas com álgebra linear, mas não com o processo de filtragem subjacente de Kalman. Descrever a matriz H (seja ela qual for) e as equações que a envolvem, que você está tentando resolver, deve levar a uma resposta melhor.
Bill Barth
Você talvez esteja certo. No entanto, os esquemas de filtragem da Kalman são um tópico importante para eles mesmos. Seria pedir demais a alguém para aprender como o Kalman Filters funciona com a minha pergunta e a partir disso, elaborar uma resposta. Isso seria um trabalho em nível de trabalho de pesquisa (presumo que seja assim). Acho que qualquer pessoa que esteja em condições de responder à pergunta não precisará de detalhes adicionais.
Bogdanovist

Respostas:

7

AA1LUAAAA1

Para a filtragem Kalman em particular, em vez de computar

Sk=(HkPk1,kHkT+Rk)1

Sk1SkLDLTHkRkP

Rk

Brian Borchers
fonte
Se eu fosse você, começaria a procurar no EnKF esse problema.
Brian Borchers
2

Temos um algoritmo robusto para o filtro Ensemble Kalman (e Kalman regular). É adequado para matrizes esparsas e computação paralela, pois é baseado em matrizes ortogonais e está relacionado aos algoritmos de raiz quadrada ou UD.

Teria o prazer de enviar o papel

Thomas, SJ, J. Hacker e J. Anderson, (2009): Uma formulação robusta do filtro de conjunto Kalman Quart J. Royal Met. Soc, vol. 135, 507-521,

(O PDF do editor é gratuito .)

Stephen Thomas
fonte
2
Olá Stephen. Obrigado por se juntar ao scicomp. Entendo que a pergunta era bastante geral, de modo que é impossível dar uma resposta específica. No entanto, também em vista do benefício de outros visitantes, talvez você possa fornecer mais informações sobre o que seu algoritmo realmente faz e fornecer um link estável, por exemplo. via doi, para a referência.
Jan
Apenas postar o resumo aqui seria uma boa maneira de "explicar" o link para os padrões do Stack Exchange.
dmckee --- ex-moderador gatinho
Embora eu concorde com Jan, os EE que lidam com KFs (como eu!) Geralmente não lêem publicações meteorológicas. O fato de o artigo ser recomendado como resposta a um problema notoriamente sutil é motivação suficiente para que eu o busque.
Damien
O filtro Kalman do conjunto (EnKF) pode ser interpretado no contexto da teoria da regressão linear. As equações do filtro são equivalentes às equações normais para uma estimativa dos mínimos quadrados ponderados que minimiza uma função quadrática. A resolução das equações normais é numericamente não confiável e sujeita a grandes erros quando o problema está mal condicionado. Um algoritmo numericamente confiável e eficiente é apresentado, com base na minimização de uma funcionalidade alternativa. O método baseia-se em rotações ortogonais, é altamente paralelo e não matrizes quadradas para calcular a atualização da análise.
Stephen Thomas
0

Há muito tempo, tive a chance de trabalhar na redução de dimensionalidade, que lida com o processamento de dados que caem em conjuntos grandes. A idéia básica por trás disso é que ele processa os dados através de algumas etapas para orientá-lo da maneira que a maioria das informações pode ser calculada a partir dele.

Também funciona muito bem para matrizes e é amplamente utilizado. A melhor parte é que você nem precisa programá-lo, pois já existem bibliotecas padrão. As principais ferramentas matemáticas como Matlab e Mathematica também suportam essa funcionalidade diretamente.

Existem dois algoritmos principais que conseguem isso - Análise de Componentes Principais e Decomposição de Valor Singular.

O que esses algoritmos realmente alcançam é encontrar os dados que realmente afetam sua leitura por uma margem significativa. A internet está cheia de informações sobre esses algoritmos. Isso mostrará como o Apache está fazendo isso.

Rorschach
fonte
-1

Desculpas por não ter contribuído para a discussão por um tempo - mas eu ficaria feliz em publicar o resumo do artigo -, mas também de bom grado entrar nas razões pelas quais os cálculos são organizados de maneira diferente das abordagens padrão do KF do EnKF

Stephen Thomas
fonte
O resumo é:
Stephen Thomas
Você queria que este fosse um comentário ou edite para sua outra resposta?
precisa