Encontrar la diagonal de la matriz inversa

Question

He calculado el Cholesky de una matriz semidifinita positiva $\Theta$ . Sin embargo, deseo conocer los elementos diagonales de la inversa de $\Theta^{-1}_{ii}$ . ¿Es posible hacer esto usando el cholesky que he calculado? O bien, encontrar los valores propios por sí solos (sin las matrices ortonormales de un SVD) ayudará a esta causa.

¿Hay alguna otra sugerencia o descomposición alternativa que ayude a encontrar la diagonal de la matriz inversa?

Edición: He visto que proyecciones aleatorias hace maravillas para invertir matrices. ¿Podría aplicarse algo así en este caso?

Answer 1

Me topé con esta pregunta al tratar de responder a una pregunta similar

Quiero una matriz diagonal que se aproxime lo mejor posible a la inversa de una matriz $\textbf{B} \succ 0$ .

Publicaré mi respuesta en que pregunta en caso de que ayude a otros (y tal vez OP). En este caso, "mejor" significa más cercano en el $\ell_2$ sentido.

$$\textbf{d}^*(\textbf{B}) = {argmin}_{\textbf{d}} \tfrac 1 2 \| \textbf{B} diag(\textbf{d}) - \textbf{I} \|_F^2$$

Esto es separable en $d_i$ y diferenciable. Poniendo el gradiente a cero llegamos a la solución de forma cerrada (y muy barata)

$[\textbf{d}^*]_i = \frac {b_{ii} } { \| \textbf{b}_i \|^2}$

(Nota: en los números complejos, necesitarías conjugar)

No me extrañaría que esto se supiera desde hace 100 años, pero no he podido encontrarlo fácilmente.

Answer 2

Si tienes la descomposición de Cholesky, puedes calcular fácilmente la inversa de la matriz completa. Como

$$\Theta = R^* R$$

donde $R$ es triangular superior, entonces se puede encontrar $\Theta^{-1}$ resolviendo

$$R^* R X = I$$

donde $I$ es la identidad. Este último sistema puede resolverse por sustitución hacia delante y hacia atrás.

Si sólo quiere las entradas diagonales de $X$ Si no se hace nada, se puede ahorrar la mitad del cálculo deteniendo el proceso de sustitución hacia atrás (para cada columna) cuando se llega a la entrada diagonal.

Answer 3

Tang y Saad tienen un método que utiliza vectores aleatorios (no necesariamente proyecciones):

Un método de sondeo para calcular la diagonal de la matriz inversa

Answer 4

Creo que no podemos tener una complejidad $<n^3/3$ . En efecto, dejemos $\Theta=LL^*$ donde $L$ es triangular inferior. Claramente $\Theta^{-1}={L^*}^{-1}L^{-1}$ ; deja que $L^{-1}=[u_{i,j}]$ . Entonces (F) ${\Theta^{-1}}_{i,i}=\sum_{j\geq i}|u_{j,i}|^2$ . Entonces debemos conocer el $(|u_{j,i}|)$ y (en mi opinión) debemos conocer el $(u_{j,i})$ Es decir $L^{-1}$ . La complejidad del cálculo de $L^{-1}$ es $\sim n^3/3$ (véase. Una rápida inversión de la matriz triangular por R. Mahfoudhi). En el segundo paso, el cálculo de la $({\Theta^{-1}}_{i,i})$ (con (F)) está en $O(n^2)$ .