Filtrado lineal en un espacio de estados de alta dimensión

Question

Estoy trabajando con modelos de espacio de estados lineales gaussianos de la forma:

$$y_t=F_t\Theta_t+v_t$$ $$\Theta_t=G_t\Theta_{t-1}+w_t$$ $$v_t \sim N(0, V_t)$$ $$w_t \sim N(0, W_t)$$

Dónde $y_t$ es mi serie temporal observada (normalmente multivariante) y $\Theta_t$ es el estado del sistema en el momento $t$ . $F_t$ y $G_t$ son las ecuaciones del sistema y de la observación, respectivamente.

En general, he estado infiriendo estos modelos utilizando el Filtrado/Suavizado de Kalman, pero ahora estoy trabajando con datos/modelos que tienen espacios de estado muy grandes (~500 dimensiones) y encuentro que las implementaciones del Filtro de Kalman que he probado tardan demasiado en ejecutarse.

Cabe destacar que la matriz $G_t$ y $F_t$ suelen ser bastante escasos en mis modelos.

Busco consejo sobre extensiones o alternativas al filtro de Kalman que me permitan inferir este tipo de Modelo Lineal Dinámico. Mi idea inicial es utilizar una representación dimensional reducida del espacio de estado, pero no estoy seguro de cómo implementar esto o qué aspecto tendría exactamente.

Agradecería mucho referencias o enlaces a código disponible (preferiblemente R o C++).

Gracias.

Answer 1

No necesitas hacer nada más que explotar la estructura de tu problema.

En particular, no computar, ni almacenar, ni de ninguna otra forma consumir tiempo y espacio, ocupándose de las partes del cálculo que simplemente serán cero. Averigua dónde cambiarán las cosas que necesitas cambiar y sólo almacena y actualiza esos . Además, algunas personas comprimen en exceso los pasos del cálculo ("mira, lo he escrito en una línea menos de álgebra"), pero en el proceso pueden enmascarar algunas de las oportunidades de explotar el cálculo redundante. Algunos algoritmos no calculan explícitamente la ganancia de Kalman como un paso, por ejemplo, pero ahí puede haber un aumento de velocidad (he visto algunos algoritmos que la calculan implícitamente tres veces).

Además, hay otras cosas obvias que deben evitarse

• no multiplicar por 1.

• no añadas cero.

No me refiero a "comprueba este cálculo en el código y sáltatelo" (eso es casi inútil), me refiero a que averigües dónde habrías hecho este cálculo utilizando tu conocimiento de la estructura del problema y nunca llegues ahí en el código.

Además:

• no calcule lo mismo dos veces (en el peor de los casos, podría considerar la memoización, pero es mucho mejor evitar siquiera considerar calcular lo que sabe que ya sabrá; no haga en el software lo que su cerebro puede anticipar fácilmente y puede simplemente evitar por completo).

  Por ejemplo, si ya estás calculando una cosa, no te des la vuelta y calcules su transposición; ya la tienes (esto es un subconjunto de calcular la misma cosa dos veces).

  A menudo puede haber algún tipo de estructura de bloques (o estructuras similares), a veces con algunas eficiencias entre ellos (como que un bloque esté estrechamente relacionado con otro) o dentro de los bloques (por ejemplo, simetrías o asimetrías).

Dedicar algo de tiempo a pensar en los cálculos evitables que estás haciendo puede suponer una gran diferencia. Haz primero las cosas más importantes (me refiero a las que te evitarán muchos cálculos, no a las que te llevarán más tiempo poner en práctica); puede que descubras que no necesitas obtener hasta el último gramo de ganancia cuando puedes obtener el 85% de ella por menos de la mitad del trabajo.

Pero, del mismo modo, no sobreoptimices hasta el punto de interferir en las cosas que el hardware y las librerías numéricas pueden hacer bien (esto depende de la naturaleza precisa de tu hardware y librerías). Algunas de estas cosas pueden ser sutiles, pero no te dejes llevar por pequeñas ganancias (o incluso ganancias negativas si no tienes cuidado).

Answer 2

Algunas reflexiones:

1. Utilice la Woodbury-Matrix fórmula, si ayuda, cuando estás calculando la matriz de ganancia de Kalman. Usualmente esa matriz inversa es la que toma más tiempo calcular. Con esto usted podría ser capaz de escribir esa inversa en términos de la inversa de una matriz más pequeña. Por eso te pregunté por tu dimensión de observación.

2. Si $F_t$ , $G_t$ , $V_t$ y $W_t$ son diagonales en bloque, o dispersas como dices, podrías ser capaz de "desacoplarlas". Recuerdo vagamente que son diagonales en bloque, y si tu primera distribución de estado tiene componentes no correlacionados, seguirán sin estarlo después de cada iteración del filtro de Kalman. Así que sólo puedes ajustar modelos de espacio de estados individuales a estos componentes. Demostrarlo es sencillo. Sólo tienes que escribir las ecuaciones del filtro de Kalman en términos de matrices de bloques, y comprobar para asegurarse de que los bloques fuera de diagonal son $\mathbf{0}$ matrices.

3. Utiliza el "filtro de información". Nunca lo he usado yo mismo, pero aparentemente sólo tienes que hacer un seguimiento de la matriz de covarianza inversa, o matriz de precisión, en cada paso de tiempo. Usted nunca tiene que invertir nada. Pero tiene otros inconvenientes. He olvidado cuáles eran.