Identidad matricial de Woodbury

Teorema de rangos matriciales

En matemáticas , específicamente en álgebra lineal , la identidad matricial de Woodbury (nombrada en honor a Max A. Woodbury ^{[1] [2]} ) dice que la inversa de una corrección de rango k de alguna matriz se puede calcular haciendo una corrección de rango k a la inversa de la matriz original. Los nombres alternativos para esta fórmula son lema de inversión de matrices , fórmula de Sherman-Morrison-Woodbury o simplemente fórmula de Woodbury . Sin embargo, la identidad apareció en varios artículos antes del informe de Woodbury. ^{[3] [4]}

La identidad de la matriz de Woodbury es ^[5] $${\displaystyle \left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},}$$

donde A , U , C y V son matrices conformes : A es n × n , C es k × k , U es n × k y V es k × n . Esto se puede derivar utilizando la inversión de matrices por bloques .

Si bien la identidad se utiliza principalmente en matrices, se cumple en un anillo general o en una categoría Ab .

La identidad matricial de Woodbury permite el cálculo económico de inversas y soluciones de ecuaciones lineales. Sin embargo, se sabe poco sobre la estabilidad numérica de la fórmula. No existen resultados publicados sobre sus límites de error. La evidencia anecdótica ^[6] sugiere que puede divergir incluso en ejemplos aparentemente benignos (cuando tanto la matriz original como la modificada están bien condicionadas ).

Discusión

Para demostrar este resultado, comenzaremos por demostrar uno más simple. Reemplazando A y C por la matriz identidad I , obtenemos otra identidad un poco más simple: Para recuperar la ecuación original a partir de esta identidad reducida , reemplazamos por y por . $${\displaystyle \left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.}$$ ${\displaystyle U}$ ${\displaystyle A^{-1}U}$ ${\displaystyle V}$ ${\displaystyle CV}$

Esta identidad en sí misma puede verse como la combinación de dos identidades más simples. Obtenemos la primera identidad de así, y de manera similar La segunda identidad es la llamada identidad de empuje ^[7] que obtenemos de después de multiplicar por a la derecha y por a la izquierda. $${\displaystyle I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P,}$$ $${\displaystyle (I+P)^{-1}=I-(I+P)^{-1}P,}$$ $${\displaystyle (I+P)^{-1}=I-P(I+P)^{-1}.}$$ $${\displaystyle (I+UV)^{-1}U=U(I+VU)^{-1}}$$ $${\displaystyle U(I+VU)=(I+UV)U}$$ ${\displaystyle (I+VU)^{-1}}$ ${\displaystyle (I+UV)^{-1}}$

Poniendo todo junto, donde la primera y segunda igualdad provienen de la primera y segunda identidad, respectivamente. $${\displaystyle \left(I+UV\right)^{-1}=I-UV\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.}$$

Casos especiales

Cuando son vectores, la identidad se reduce a la fórmula de Sherman-Morrison . ${\displaystyle V,U}$

En el caso escalar, la versión reducida es simplemente $${\displaystyle {\frac {1}{1+uv}}=1-{\frac {uv}{1+vu}}.}$$

Inversa de una suma

Si n = k y U = V = In es la matriz identidad, _entonces

$${\displaystyle {\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}}$$

Continuando con la fusión de los términos del extremo derecho de la ecuación anterior se obtiene la identidad de Hua. $${\displaystyle \left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{A}\right)^{-1}.}$$

Otra forma útil de la misma identidad es $${\displaystyle \left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},}$$

que, a diferencia de las anteriores, es válida incluso si es singular y tiene una estructura recursiva que da como resultado si el radio espectral de es menor que uno. Es decir, si la suma anterior converge, entonces es igual a . ${\displaystyle B}$ $${\displaystyle \left({A}-{B}\right)^{-1}=\sum _{k=0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}}$$ ${\displaystyle A^{-1}B}$ ${\displaystyle (A-B)^{-1}}$

Esta forma se puede utilizar en expansiones perturbativas donde B es una perturbación de A.

Variaciones

Teorema del inverso del binomio

Si A , B , U , V son matrices de tamaños n × n , k × k , n × k , k × n , respectivamente, entonces $${\displaystyle \left(A+UBV\right)^{-1}=A^{-1}-A^{-1}UB\left(B+BVA^{-1}UB\right)^{-1}BVA^{-1}}$$

siempre que A y B + BVA ⁻¹ UB sean no singulares. La no singularidad de este último requiere que exista B ^{−1 ya que es igual a} B ( I + VA ⁻¹ UB ) y el rango de este último no puede exceder el rango de B . ^[7]

Dado que B es invertible, los dos términos B que flanquean la cantidad paréntesis inversa en el lado derecho se pueden reemplazar con ( B ⁻¹ ) ⁻¹ , lo que da como resultado la identidad de Woodbury original.

Una variación para cuando B es singular y posiblemente incluso no cuadrado: ^[7] $${\displaystyle (A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.}$$

También existen fórmulas para ciertos casos en los que A es singular. ^[8]

Pseudoinversa con matrices semidefinidas positivas

En general, la identidad de Woodbury no es válida si una o más inversas se reemplazan por pseudoinversas (de Moore–Penrose) . Sin embargo, si y son semidefinidas positivas , y (lo que implica que es en sí misma semidefinida positiva), entonces la siguiente fórmula proporciona una generalización: ^{[9] [10]} ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle V=U^{\mathrm {H} }}$ ${\displaystyle A+UCV}$ $${\displaystyle {\begin{aligned}\left(XX^{\mathrm {H} }+YY^{\mathrm {H} }\right)^{+}&=\left(ZZ^{\mathrm {H} }\right)^{+}+\left(I-YZ^{+}\right)^{\mathrm {H} }X^{+\mathrm {H} }EX^{+}\left(I-YZ^{+}\right),\\Z&=\left(I-XX^{+}\right)Y,\\E&=I-X^{+}Y\left(I-Z^{+}Z\right)F^{-1}\left(X^{+}Y\right)^{\mathrm {H} },\\F&=I+\left(I-Z^{+}Z\right)Y^{\mathrm {H} }\left(XX^{\mathrm {H} }\right)^{+}Y\left(I-Z^{+}Z\right),\end{aligned}}}$$

donde se puede escribir como porque cualquier matriz semidefinida positiva es igual a para algún . ${\displaystyle A+UCU^{\mathrm {H} }}$ ${\displaystyle XX^{\mathrm {H} }+YY^{\mathrm {H} }}$ ${\displaystyle MM^{\mathrm {H} }}$ ${\displaystyle M}$

Derivaciones

Prueba directa

La fórmula se puede demostrar comprobando que multiplicada por su supuesta inversa en el lado derecho de la identidad de Woodbury da la matriz identidad: ${\displaystyle (A+UCV)}$ $${\displaystyle {\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{I-U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}}$$

Pruebas alternativas

Aplicaciones

Esta identidad es útil en ciertos cálculos numéricos donde A ⁻¹ ya se ha calculado y se desea calcular ( A  +  UCV ) ⁻¹ . Con la inversa de A disponible, solo es necesario encontrar la inversa de C ⁻¹  +  VA ⁻¹ U para obtener el resultado usando el lado derecho de la identidad. Si C tiene una dimensión mucho menor que A , esto es más eficiente que invertir A  +  UCV directamente. Un caso común es encontrar la inversa de una actualización de bajo rango A  +  UCV de A (donde U solo tiene unas pocas columnas y V solo unas pocas filas), o encontrar una aproximación de la inversa de la matriz A  +  B donde la matriz B puede aproximarse por una matriz de bajo rango UCV , por ejemplo usando la descomposición en valores singulares .

Esto se aplica, por ejemplo, en el filtro de Kalman y en los métodos recursivos de mínimos cuadrados , para reemplazar la solución paramétrica , que requiere la inversión de una matriz de tamaño de vector de estado, con una solución basada en ecuaciones de condición. En el caso del filtro de Kalman, esta matriz tiene las dimensiones del vector de observaciones, es decir, tan pequeñas como 1 en caso de que solo se procese una nueva observación a la vez. Esto acelera significativamente los cálculos del filtro, a menudo en tiempo real.

En el caso en que C es la matriz identidad I , la matriz se conoce en álgebra lineal numérica y ecuaciones diferenciales parciales numéricas como la matriz de capacitancia . ^[4] ${\displaystyle I+VA^{-1}U}$

Véase también

• Fórmula de Sherman-Morrison
• Complemento de Schur
• Lema del determinante matricial , fórmula para una actualización de rango k de un determinante
• Matriz invertible
• Pseudoinversa de Moore–Penrose § Actualización de la pseudoinversa

Notas

1. Max A. Woodbury, Inversión de matrices modificadas , Memorándum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp MR 38136
2. Max A. Woodbury, La estabilidad de las matrices de entrada y salida . Chicago, Ill., 1949. 5 págs. MR 32564
3. Guttmann, Louis (1946). "Métodos de ampliación para calcular la matriz inversa". Ann. Math. Statist . 17 (3): 336–343. doi : 10.1214/aoms/1177730946 .
4. Hager, William W. (1989). "Actualización de la inversa de una matriz". SIAM Review . 31 (2): 221–239. doi :10.1137/1031049. JSTOR  2030425. MR  0997457.
5. Higham, Nicholas (2002). Precisión y estabilidad de algoritmos numéricos (2.ª ed.). SIAM . p. 258. ISBN 978-0-89871-521-7.Señor 1927606  .
6. "Discusión de MathOverflow". MathOverflow .
7. Henderson, HV; Searle, SR (1981). "Sobre la derivación de la inversa de una suma de matrices" (PDF) . SIAM Review . 23 (1): 53–60. doi :10.1137/1023004. hdl : 1813/32749 . JSTOR  2029838.
8. Kurt S. Riedel, "Una identidad de Sherman–Morrison–Woodbury para matrices de aumento de rango con aplicación al centrado", SIAM Journal on Matrix Analysis and Applications , 13 (1992)659-662, doi :10.1137/0613040 preimpresión MR 1152773
9. Bernstein, Dennis S. (2018). Matemáticas escalares, vectoriales y matriciales: teoría, hechos y fórmulas (edición revisada y ampliada). Princeton: Princeton University Press. pág. 638. ISBN 9780691151205.
10. Schott, James R. (2017). Análisis matricial para estadística (tercera edición). Hoboken, Nueva Jersey: John Wiley & Sons, Inc., pág. 219. ISBN 9781119092483.

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.7.3. Fórmula de Woodbury", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8

Enlaces externos

• Algunas identidades matriciales
• Weisstein, Eric W. "Fórmula de Woodbury". MathWorld .