Hay descomposición de una matriz simétrica que permitan la inversión de cualquier submatriz?

Question

Me da un $J \times J$ simétrica matriz $\Sigma$. Para un subconjunto de $\{1, ..., J\}$, $v$, deje $\Sigma_{v}$ denotar la asociada a la plaza de la submatriz. Estoy en la necesidad de un sistema eficaz para la inversión de $\Sigma_v$ para, potencialmente, cualquier subconjunto $v$. Esencialmente, voy a tener que invertir muchos diferentes submatricies $\Sigma_v$, pero no voy a saber que necesito para invertir en el avance de la ejecución de un programa; prefiero invertir en una buena matriz de descomposición en el principio, si existe (o de otro modo obtener toda la información necesaria, si no una descomposición).

Me he metido con el nombre de descomposición un poco, pero no era capaz de obligar a la inversa de una submatriz de ella.

ACTUALIZACIÓN: Al parecer, el plazo para el tipo de submatricies quiero invertir es "submatriz principal". Me pregunto si no puedo hacer algunos avances en este a través de la descomposición de Cholesky. Supongo que soy de contenido para calcular el $\Sigma_{jj} ^ {-1}$ cualquier $j \in \{1, 2, ..., J\}$ donde $\Sigma_{jj}$ denota la submatriz obtenida por eliminar filas/columnas mayor que $j$. Escribir $\Sigma = LL^T$ y deje $Q = L^{-1}$. Escribir $$ L = \begin{pmatrix}L_1 & \mathbf 0 \\ B & L_2\end{pmatrix}, Q = \begin{pmatrix}Q_1 & \mathbf 0 \\ C & Q_2\end{pmatrix} $$ donde$L_1$$Q_1$$j \times j$. De ello se desprende que $\Sigma_{jj} = L_1 L_1^T$$Q_1 = L_1 ^{-1}$, de modo que $\Sigma_{jj} ^{-1} = Q_1^T Q_1$. Así, una vez que tengo la descomposición de Cholesky, tengo los inversos de los líderes principales submatricies. Esto no resuelve el problema como se indica, ya que puede tener que lidiar con otro director submatricies, pero debe ser una útil solución parcial.

Answer 1

Me imagino que lo mejor que puedes hacer es tan sólo un rango en un momento de construcción hacia arriba o hacia abajo para conseguir el objetivo deseado sub-matriz de la porción. Para reducir la dimensión de una simple fórmula es

$$\mathbf{A}^{-1} = E - \frac{\mathbf{f}\mathbf{g}^T}{h}$$

Para ver esto, utilice el conocido inversa de la original y de mayor dimensión de la matriz $$\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d}^{-1} = \pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h}$$

tener $$\pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h}\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d} = \pmatrix{ \mathbf I & \mathbf 0 \\ \mathbf 0^T & 1}$$

Ahora para encontrar la cantidad de $A^{-1}$, fueron simplemente multiplicar la ecuación con $$\pmatrix{\mathbf{I} & -\mathbf{f}\frac{1}{h} \\ \mathbf{0}^T & 1}$$ dando $$ \pmatrix{\mathbf{E}- \mathbf{f}\frac{1}{h}\mathbf{g}^T & \mathbf{0} \\ \mathbf{g}^T & h}\pmatrix{\mathbf{A} & \mathbf{b} \\ \mathbf{c}^T & d} = \pmatrix{\mathbf{I} & -\mathbf{f}\frac{1}{h} \\ \mathbf{0}^T & 1}$$ La porción superior izquierda de esta ecuación de matriz es $$\left( \mathbf{E} - \mathbf{f}\frac{1}{h}\mathbf{g}^T\right)\mathbf{A} = \mathbf{I}$$ y muestra la fórmula.

Ir en otra dirección (adición de una fila y una columna) puede utilizar lo que se llama las fronteras del método como se describe en esta respuesta

Answer 2

Si observamos $\Sigma_j = \Sigma_{[1..j-1]\cup[j+1..J]}$ la matriz $\Sigma$ con la supresión de las $j$th de fila y de columna, las fórmulas para calcular la actualización de Cholesky de la descomposición son : $$\Sigma = \begin{bmatrix} A_{11}&A_{12}&A_{13}\\A_{12}^T&A_{22}&A_{23}\\A_{13}^T&A_{23}^T&A_{33} \end{bmatrix} $$ $$L = \begin{bmatrix} L_{11}&L_{12}&L_{13}\\0&L_{22}&L_{23}\\0&0&L_{33} \end{bmatrix} $$

$$\Sigma_j = \begin{bmatrix} A_{11}&A_{13}\\A_{13}^T&A_{33} \end{bmatrix} $$

$$L_j = \begin{bmatrix} L_{11}&L_{13}\\0&\mathsf{cholupdate}(L_{33},L_{23})\end{bmatrix} $$ donde $\mathsf{cholupdate}(A,B) = \mathsf{chol}(A^TA+B^TB)$. Estos cálculos a realizar en $O(n^2)$, así que si usted tiene $K$ deleciones, el cálculo de costos es $O(Kn^2)$.

Answer 3

La solución de adam W propuesto generaliza para clasificar a-$n$ actualizaciones; no es necesario llegar al repetirse rango-1 actualizaciones. En su etimología, podemos considerar $h$ una matriz en lugar de un escalar, y reemplazar la parte inferior derecha de la 1 con una matriz identidad y $\frac{1}{h}$$h^{-1}$. Todavía funciona.