Dadas dos matrices $X$ y $Y$ es fácil tomar la inversa de su producto de Kronecker:
$(X\otimes Y)^{-1} = X^{-1}\otimes Y^{-1}$
Ahora, supongamos que tenemos alguna matriz diagonal $\Lambda$ (o más generalmente una matriz fácilmente invertible, o una para la que ya conocemos la inversa). ¿Existe una expresión de forma cerrada o un algoritmo eficiente para calcular $(\Lambda + (X\otimes Y))^{-1}$ ?
Sí, lo hay.
Véase la ecuación 5 en http://books.nips.cc/papers/files/nips24/NIPS2011_0443.pdf
Stegle et al. Inferencia eficiente en modelos gaussianos matriciales con ruido de observación iid
Las matrices correspondientes a $X$ y $Y$ en el artículo citado son semidefinidos positivos y $\Gamma$ es un múltiplo de $I$ pero creo que lo que el PO pide es más general.
Sí, no es una respuesta completa, estoy de acuerdo... pero creo que la descomposición del valor propio que se da en el documento permitirá al menos una solución parcial.
Para profundizar más... la matriz debe ser diagonalizable.... tal vez se podría utilizar otro método de descomposición matricial en el caso general La expresión para la inversa se da aquí es.wikipedia.org/wiki/Eigendecomposition_of_a_matrix No lo he comprobado, pero creo que el \Gamma es un múltiplo de I puede ser tratado, es decir, esta restricción puede ser al menos paritalmente eliminada . Así que para calificar, no he dado una respuesta completa aquí (porque, no sé) - pero creo que este es el enfoque correcto ...
Dejemos que $C := \left\{ c_{i,j} \right\}_{i,j=1}^N$ y $A := \left\{ a_{i,j} \right\}_{i,j=1}^n$ sean matrices simétricas. Las descomposiciones espectrales de las dos matrices son $A = O^T D_A O$ y $C = U^T D_C U$ donde $D_A := Diag(\lambda_k)_{k=1}^n$ y $D_C := Diag(\mu_k)_{k=1}^N$ y $O \cdot O^T = O^T \cdot O = 1_n$ y $U \cdot U^T = U^T \cdot U = 1_N$ . Utilizamos la ecuación 5 del artículo citado para calcular el resolvente $G_{A \otimes C}(z) := \left(z 1_{ n N} - A \otimes C\right)^{-1}$ . Tenemos: \begin{eqnarray} G_{A \otimes C}(z) &=& \left( O^T \otimes U^T\right) \cdot \left( z 1_{ n N} - D_A \otimes D_C \right)^{-1} \cdot \left(O \otimes U \right) \\ &=& \left\{ \sum\limits_{k=1}^n O_{k,i} O_{k,j} U^T \cdot \left( z 1_{N} - \lambda_k D_C\right)^{-1} U \right\}_{i,j=1}^n \\ &=& \sum\limits_{p=0}^\infty \frac{1}{z^{1+p}} A^p \otimes C^p \\ &=& \frac{\sum\limits_{p=0}^{d-1} z^{d-1-p} \sum\limits_{l=d-p}^d (-1)^{d-l} {\mathfrak a}_{d-l} \left(A \otimes C\right)^{p-d+l}}{\sum\limits_{p=0}^d z^{d-p} (-1)^p {\mathfrak a}_p} \end{eqnarray} donde $\det( z 1_{n N} - A \otimes C) := \sum\limits_{l=0}^{n N} (-1)^l {\mathfrak a}_l z^{n N-l}$ . Las dos primeras líneas de la parte superior son sencillas. En la tercera línea expandimos la matriz inversa en una serie y finalmente en la cuarta línea sumamos la serie infinita utilizando el teorema de Cayley-Hamilton.
Utiliza el siguiente truco:
$$(\Lambda+A)^{-1}=A^{-1}(A^{-1}\Lambda+I)^{-1}$$ donde $A=X\bigotimes Y$ . Entonces podemos descomponer $\Lambda=\Lambda_1\bigotimes \Lambda_2$ por cualquier $\Lambda_1$ y $\Lambda_2$ porque $\Lambda$ es diagonal. Ahora tenemos $$A^{-1}\Lambda=X^{-1}\Lambda_1 \bigotimes Y^{-1}\Lambda_2$$ y utilizar el método mencionado por David Rohde
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
+1 ¿Cuál es el motivo de su pregunta?
2 votos
Tengo un problema de optimización convexo que estoy tratando de resolver, y el hessiano del objetivo tiene la forma anterior. Si puedo calcular el hessiano inverso de forma eficiente puedo utilizar el método de Newton, que es mucho más preferible que los métodos de gradiente.
0 votos
¿Has encontrado alguna forma de hacerlo que evite las descomposiciones de valores propios? También me he encontrado con Hessians con esta estructura y estaría interesado en algoritmos eficientes para resolver este problema.