Tengo un % de la matriz $F=XDX^T$, donde $D$ $m\times m$ y diagonal y $X$ $n\times m$.
Ahora, puedo calcular $F^{-1}$.
¿Hay un método eficiente para actualizar $F^{-1}$ si se actualiza $D$ $D'=D+G$, donde $G$ es una matriz diagonal escasa?
Respuesta
¿Demasiados anuncios?
Sí, hay una forma muy eficiente para calcular la actualización de la $F^{-1}$. Comenzar escribiendo $X$ en términos de sus columnas: $X = [x_1 x_2 \dots x_m]$. De ello se sigue que: $$ XGX^T = \sum_{i=1}^{m} G_{ii} x_ix_i^T = \sum_{i\in S} G_{ii} x_ix_i^T $$ donde $S \subset \{1,\dots,m\}$ es el conjunto de índices para que $G_{ii}$ es distinto de cero. Supongamos que $S$ contiene $r$ índices. Desde $G$ es escasa, por supuesto, $r$ es mucho menor que $m$. Si montamos las columnas de a $X$ correspondiente a los índices de $S$, obtenemos una nueva matriz $Y$, tal que: $$ XGX^T = YHY^T $$ donde$Y$$m \times r$, e $H$ es una matriz diagonal cuya diagonal se compone de todos los distinto de cero entradas a lo largo de la diagonal de a $G$. Ahora aplique el Woodbury matriz identidad: $$ (F+YHY^T)^{-1} = F^{-1} - F^{-1}Y(H^{-1}+Y^TF^{-1}Y)^{-1}Y^TF^{-1} $$ La informática de la mano izquierda directamente es costosa, ya que requiere la inversión de una $m\times m$ matriz. Sin embargo, desde la $F^{-1}$ ya ha sido calculada, podemos calcular el lado derecho de manera eficiente; el inverso de a $r\times r$ matriz, y $r$ es mucho menor que $m$.
