Identidad de la matriz de Woodbury

Teorema de rangos matriciales

En matemáticas (específicamente álgebra lineal ), la identidad de la matriz de Woodbury , que lleva el nombre de 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 para la inversa de la matriz original. Los nombres alternativos para esta fórmula son lema de inversión matricial , fórmula de Sherman-Morrison-Woodbury o simplemente fórmula de Woodbury . Sin embargo, la identidad apareció en varios periódicos antes del informe 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 conformables : 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 en bloques .

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

La identidad de la matriz 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 hay 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 probar este resultado, comenzaremos demostrando uno más simple. Reemplazando A y C con la matriz identidad I , obtenemos otra identidad un poco más simple: Para recuperar la ecuación original a partir de esta identidad reducida , reemplaza 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 esta manera, y de manera similar. La segunda identidad es la llamada identidad de paso ^[7] que obtenemos 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}}$

Sumando todo, 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+uv}}.}$$

Inversa de una suma

Si n = k y U = V = I _n 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 los anteriores, es válido incluso si es singular y tiene una estructura recursiva que cede 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 B ⁻¹ exista 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 entre 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 (Moore-Penrose) . Sin embargo, si y son semidefinidos positivos , y (lo que implica que en sí mismos son semidefinidos positivos), 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 algunos . ${\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 probar comprobando que multiplicado por su supuesto inverso en el lado derecho de la identidad de Woodbury da la matriz de 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 ya se ha calculado A ⁻¹ y se desea calcular ( A  +  UCV ) ⁻¹ . Con la inversa de A disponible, sólo es necesario encontrar la inversa de C ⁻¹  +  VA ⁻¹ U para obtener el resultado utilizando el lado derecho de la identidad. Si C tiene una dimensión mucho más pequeña 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 mediante una matriz de bajo rango UCV , por ejemplo utilizando 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 del tamaño de un 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 sólo 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 de que C sea la matriz identidad I , la matriz se conoce en álgebra lineal numérica y en ecuaciones diferenciales parciales numéricas como matriz de capacitancia . ^[4] ${\displaystyle I+VA^{-1}U}$

Ver también

• Fórmula de Sherman-Morrison
• complemento de Schur
• Lema del determinante matricial , fórmula para una actualización de rango k a un determinante
• matriz reversible
• Pseudoinverso de Moore-Penrose § Actualización del pseudoinverso

Notas

1. Max A. Woodbury, Inversión de matrices modificadas , Memorándum Rept. 42, Grupo de Investigación Estadística, Universidad de Princeton, Princeton, Nueva Jersey, 1950, 4pp MR 38136
2. Max A. Woodbury, La estabilidad de las matrices de entrada y salida . Chicago, Illinois, 1949. 5 págs. MR 32564
3. Guttmann, Luis (1946). "Métodos de ampliación para calcular la matriz inversa". Ana. Matemáticas. Estatista . 17 (3): 336–343. doi : 10.1214/aoms/1177730946 .
4. Hager, William W. (1989). "Actualización de la inversa de una matriz". Revisión SIAM . 31 (2): 221–239. doi :10.1137/1031049. JSTOR  2030425. SEÑOR  0997457.
5. Higham, Nicolás (2002). Precisión y estabilidad de algoritmos numéricos (2ª ed.). SIAM . pag. 258.ISBN​ 978-0-89871-521-7. SEÑOR  1927606.
6. "Discusión sobre MathOverflow". Desbordamiento matemático .
7. Henderson, HV; Searle, SR (1981). "Sobre derivar la inversa de una suma de matrices" (PDF) . Revisión SIAM . 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 rangos con aplicación al centrado", Revista SIAM sobre análisis y aplicaciones de matrices , 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: Prensa de la Universidad de Princeton. pag. 638.ISBN​ 9780691151205.
10. Schott, James R. (2017). Análisis matricial para estadística (Tercera ed.). Hoboken, Nueva Jersey: John Wiley & Sons, Inc. p. 219.ISBN​ 9781119092483.

• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.7.3. Fórmula de Woodbury", Recetas numéricas: el arte de la informática 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". MundoMatemático .