Implementação de matriz esparsa do filtro Kalman?

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.

$A$$A^{-1}$$LU$$A$$A$$A$$A^{-1}$

Para a filtragem Kalman em particular, em vez de computar

$S_{k}=(H_{k}P_{k-1,k}H_{k}^{T}+R_{k})^{-1}$

$S_{k}^{-1}$$S_{k}$$LDL^{T}$$H_{k}$$R_{k}$$P$

$R_{k}$

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 .)

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.

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