Woodbury matris identitet

Inom matematik (särskilt linjär algebra ) säger Woodbury-matrisidentiteten , uppkallad efter Max A. Woodbury, att inversen av en rang- k- korrigering av någon matris kan beräknas genom att göra en rang- k -korrigering till inversen av den ursprungliga matrisen . Alternativa namn för denna formel är matrisinversionslemma , Sherman–Morrison–Woodbury-formel eller bara Woodbury-formel . Men identiteten förekom i flera tidningar före Woodbury-rapporten.

Woodbury-matrisidentiteten är

$\left(A+UCV\right)^{ -1}=A^{-1}-A^{-1}U\vänster(C^{-1}+VA^{-1}U\höger)^{-1}VA^{-1},$

där A , U , C och V är konforma matriser : A är n × n , C är k × k , U är n × k och V är k × n . Detta kan härledas med blockvis matrisinversion .

Medan identiteten främst används på matriser, håller den i en allmän ring eller i en Ab-kategori .

Diskussion

För att bevisa detta resultat börjar vi med att bevisa ett enklare. Genom att ersätta A och C med identitetsmatrisen I får vi en annan identitet som är lite enklare:

$\left(I+UV\right)^{-1}=IU\left(I+VU\right)^{-1}V.$

För att återställa den ursprungliga ekvationen från denna reducerade identitet ställer du in $U=A^{-1}X$ och $V=CY$ .

Denna identitet i sig kan ses som en kombination av två enklare identiteter. Vi får den första identiteten från

$I=(I+P)^{-1}(I+P )=(I+P)^{-1}+(I+P)^{-1}P$ ,

Således,

$(I+P)^{-1}=I-(I+P)^{-1}P$ ,

och liknande

$(I+P)^{-1}=IP(I+P)^{-1}.$

Den andra identiteten är den så kallade push-through-identiteten

$(I+UV)^{-1}U=U(I+VU)^{-1}$

som vi får från

$U(I+VU)=(I+UV)U$

efter multiplicering med $)^{-1}}$$(I+UV)^{-1 }$ till höger och med till vänster.

Speciella fall

När $V,U$ är vektorer reduceras identiteten till Sherman–Morrison-formeln .

I det skalära fallet är den reducerade versionen helt enkelt

${\frac {1}{1+uv}}=1-{\frac {uv}{1+uv}}.$

Invers av en summa

Om n = k och U = V = I _n är identitetsmatrisen, då

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

Att fortsätta med sammanslagning av termerna längst till höger i ovanstående ekvation resulterar i Huas identitet

$\left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{ A}\höger)^{-1}.$

En annan användbar form av samma identitet är

$\left({A}-{B}\right)^{-1}={A}^ {-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},$

vilket, till skillnad från de ovan, är giltigt även om $B$ är singular och har en rekursiv struktur som ger

$\left({A}-{B}\right)^{-1}=\summa _{k= 0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}$

om spektralradien för $A^{-1}B$ är mindre än en. Det vill säga, om summan ovan konvergerar så är den lika med $(AB)^{-1}$ .

Denna form kan användas i störande expansioner där B är en störning av A .

Variationer

Binomial inverssats

Om A , B , U , V är matriser med storlekarna n × n , k × k , n × k , k × n , respektive

$\left(A+UBV\right)^ {-1}=A^{-1}-A^{-1}UB\vänster(B+BVA^{-1}UB\höger)^{-1}BVA^{-1}$

förutsatt att A och B + BVA ⁻¹ UB är ickesingular. Icke-singularitet hos den senare kräver att B ⁻¹ existerar eftersom den är lika med B ( I + VA ⁻¹ UB ) och rangordningen för den senare kan inte överstiga rangordningen B.

Eftersom B är inverterbar kan de två B- termerna som flankerar den inversa parentesstorheten på höger sida ersättas med ( B −1 ⁾ −1 ^, vilket resulterar i den ursprungliga Woodbury-identiteten.

En variant för när B är singular och möjligen till och med icke-kvadrat:

$(A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1} .$

Formler finns också för vissa fall där A är singular.

Pseudoinvers med positiva semidefinita matriser

I allmänhet är Woodburys identitet inte giltig om en eller flera inverser ersätts med ( Moore–Penrose) pseudoinverser . Men om $A$ och $C$ är positiva semidefinita , och $V=U^{\mathrm {H} }$ (vilket antyder att ${\ displaystyle A+UCV}$ är i sig positiv semidefinite), då ger följande formel en generalisering:

${\begin{aligned}(XX^{\mathrm {H} }+YY^{\mathrm {H} })^{+}&=(ZZ^{\mathrm {H} }) ^{+}+(I-YZ^{+})^{\mathrm {H} }X^{+\mathrm {H} }EX^{+}(I-YZ^{+}),\\Z& =(I-XX^{+})Y,\\E&=IX^{+}Y(IZ^{+}Z)F^{-1}(X^{+}Y)^{\mathrm {H } },\\F&=I+(IZ^{+}Z)Y^{\mathrm {H} }(XX^{\mathrm {H} })^{+}Y(IZ^{+}Z), \end{aligned}}$

där $A+UCU^{\mathrm {H} }$ kan skrivas som $XX^{\mathrm {H} }+YY^{\ mathrm {H} }$ eftersom alla positiva semidefinite matriser är lika med $MM^{\mathrm {H} }$ för vissa $M$ .

Avledningar

Direkt bevis

Formeln kan bevisas genom att kontrollera att $(A+UCV)$ gånger dess påstådda invers på höger sida av Woodbury-identiteten ger identitetsmatrisen:

${\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{- 1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{IU\left(C^{-1}+VA^{-1}U\höger )^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1 }U\höger)^{-1}VA^{-1}\höger\}\\={}&\vänster\{I+UCVA^{-1}\höger\}-\vänster\{U\vänster (C^{-1}+VA^{-1}U\höger)^{-1}VA^{-1}+UCVA^{-1}U\vänster(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\höger)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left( C^{-1}+VA^{-1}U\höger)\vänster(C^{-1}+VA^{-1}U\höger)^{-1}VA^{-1}\\ ={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}$

Alternativa bevis

Algebraiskt bevis

Tänk först på dessa användbara identiteter, ${\begin{aligned}U+UCVA^{-1}U&=UC\left(C^{-1}+VA^{-1} U\right)=\left(A+UCV\right)A^{-1}U\\\left(A+UCV\right)^{-1}UC&=A^{-1}U\left(C ^{-1}+VA^{-1}U\höger)^{-1}\end{aligned}}$ Nu, ${\begin{aligned}A^{-1}&=\left(A+UCV\right)^{-1}\left(A+UCV\right)A^{-1}\\&= \left(A+UCV\right)^{-1}\left(I+UCVA^{-1}\right)\\&=\left(A+UCV\right)^{-1}+\left( A+UCV\höger)^{-1}UCVA^{-1}\\&=\vänster(A+UCV\höger)^{-1}+A^{-1}U\vänster(C^{- 1}+VA^{-1}U\höger)^{-1}VA^{-1}.\end{aligned}}$

Härledning via blockvis eliminering

Att härleda Woodbury-matrisidentiteten görs enkelt genom att lösa följande blockmatrisinversionsproblem ${\begin{bmatrix}A&U\\V&-C^{-1}\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}I \\0\end{bmatrix}}.$ Expanderande kan vi se att ovanstående minskar till ${\begin{cases}AX+UY=I\\VX-C^{-1}Y=0\end{cases}}$ vilket är ekvivalent med $(A+UCV)X=I$ . Om vi ​​eliminerar den första ekvationen finner vi att ${\displaystyle X=A^{-1}(I-UY)} ,$ som kan ersättas med den andra för att $VA^{-1}(I-UY)=C^{-1}Y$ . Om vi ​​expanderar och arrangerar om har vi $VA^{-1}=\left(C^{-1}+VA^{-1}U \right)Y$ , eller $\left(C^{-1}+VA^{-1}U\right)^ {-1}VA^{-1}=Y$ . Slutligen ersätter vi till vår $AX+UY=I$ , och vi har ${ \displaystyle AX+U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=I}$ . Således, $(A+UCV)^{-1}=X=A^{-1}-A^{-1}U\vänster(C^{-1}+VA^{-1}U\höger) ^{-1}VA^{-1}.$ Vi har härlett Woodbury-matrisidentiteten.

Härledning från LDU-nedbrytning

Vi börjar med matrisen ${\begin{bmatrix}A&U\\V&C\end{bmatrix}}$ Genom att eliminera posten under A (med tanke på att A är inverterbar) får vi ${\begin{bmatrix}I&0\\-VA^{-1}&I\end{ bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}A&U\\0&C-VA^{-1}U\end{bmatrix}}$ ger eliminering av posten ovanför C ${\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{ bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\V&C-VA^{-1}U\end{bmatrix}}$ När vi nu kombinerar ovanstående två får vi ${\begin{bmatrix}I&0\\-VA^ {-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix} }={\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}$ Att flytta till höger ger ${\begin{bmatrix}A&U\\V&C\end{bmatrix }}={\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}{ \begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}$ vilket är LDU-sönderdelningen av blockmatrisen till en övre triangulär, diagonal och nedre triangulär matris. Nu invertera båda sidor ger ${\ displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix }}^{-1}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}^{-1}{\begin{bmatrix}I&0\\VA^{-1 }&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}{\begin{bmatrix} A^{-1}&0\\0&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}{\begin{bmatrix}I&0\\-VA^{- 1}&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U\left(C-VA^{-1}U\right )^{-1}VA^{-1}&-A^{-1}U\vänster(C-VA^{-1}U\höger)^{-1}\\-\vänster(C-VA ^{-1}U\right)^{-1}VA^{-1}&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}\qquad \ mathrm {(1)} \end{aligned}}}$ Vi kunde lika gärna ha gjort det åt andra hållet (förutsatt att C är inverterbart) dvs ${\begin{bmatrix}A&U\\V&C\end{bmatrix }}={\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\ börja{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}$ Nu återigen invertera båda sidor, ${\ displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix }}^{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}^{-1}{\begin{bmatrix}I&UC^{-1}\\ 0&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&0\\-C^{-1}V&I\end{bmatrix}}{\begin{bmatrix}\left (A-UC^{-1}V\höger)^{-1}&0\\0&C^{-1}\end{bmatrix}}{\begin{bmatrix}I&-UC^{-1}\\0&I \end{bmatrix}}\\[8pt]&={\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&-\left(A-UC^{- 1}V\höger)^{-1}UC^{-1}\\-C^{-1}V\left(A-UC^{-1}V\höger)^{-1}&C^{ -1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm {(2 )} \end{aligned}}}$ Genom att jämföra element (1, 1) i RHS för (1) och (2) ovan får man Woodbury-formeln $\left(A-UC^{-1}V\right)^{-1}=A^{-1}+A^{-1}U\left(C-VA^{-1}U \right)^{-1}VA^{-1}.$

Ansökningar

Denna identitet är användbar i vissa numeriska beräkningar där A ⁻¹ redan har beräknats och det är önskvärt att beräkna ( A + UCV ) ⁻¹ . Med inversen av A tillgänglig är det bara nödvändigt att hitta inversen av C ⁻¹ + VA ⁻¹ U för att få resultatet med hjälp av den högra sidan av identiteten. Om C har en mycket mindre dimension än A är detta mer effektivt än att invertera A + UCV direkt. Ett vanligt fall är att hitta inversen av en lågrankad uppdatering A + UCV av A (där U bara har ett fåtal kolumner och V bara några få rader), eller att hitta en approximation av inversen av matrisen A + B där matrisen B kan approximeras av en matris med låg rangordning UCV , till exempel genom att använda singularvärdet dekomposition .

Detta tillämpas, t.ex. i Kalman-filtret och rekursiva minsta kvadratmetoder , för att ersätta den parametriska lösningen , som kräver inversion av en matris med tillståndsvektorstorlek, med en villkorsekvationsbaserad lösning. När det gäller Kalman-filtret har denna matris dimensionerna för observationsvektorn, dvs. så liten som 1 om bara en ny observation behandlas åt gången. Detta påskyndar de ofta realtidsberäkningarna av filtret avsevärt.

I fallet när C är identitetsmatrisen I är matrisen $I+VA^{-1}U$ känd i numerisk linjär algebra numeriska partiella differentialekvationer som kapacitansmatrisen .

Se även

• Sherman-Morrison formel
• Schur komplement
• Matrisdeterminantlemma , formel för en rang- k uppdatering till en determinant
• Inverterbar matris
• Moore–Penrose pseudoinverse#Uppdatering av pseudoinversen

Anteckningar

•   Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sektion 2.7.3. Woodbury Formula" , Numeriska recept: The Art of Scientific Computing (3:e upplagan), New York: Cambridge University Press, ISBN 978-0-521-88068-8

externa länkar

• Vissa matrisidentiteter
• Weisstein, Eric W. "Woodbury formula" . MathWorld .