Recursive use of the Woodbury identity to prove the Neumann series expansion.

While I was playing around with some matrices I had the need to expand the matrix inverse of (I-T) . While doing so I came across two different tools, one known as the Woodbury identity and the other known as the Neumann series expansion. While messing with the aforementioned results I found out that there is an pretty cute and trivial way to prove the Neumann series expansion using the Woodbury inequality in a recursive way.

Theorem (Woodbury inequality)

Let’s consider A\in\mathbb{R}^{n\times n}, U,V^{T}\in\mathbb{R}^{n\times k} and C\in\mathbb{R}^{k\times k} then we could write:



We could easily prove this result just showing that the direct product of (A+UCV)(A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}) yield the identity matrix.

I’ll now introduce what is called the Neumann series expansion, with this term we identify the following result: (I-T)^{-1}=\sum_{k=0}^{\infty}T^k. Is possible to prove that the series mentioned above converges, and therefore the above identity make sense, if operator norm of T is less or equal to 1. To prove what we mentioned above we usually use the following argument:

We first define S_n=\sum_{k=0}^{n}T^k and then we could easily prove that:

\displaystyle \lim_{n\to \infty}(I-T)S_n=\lim_{n\to\infty}\bigg(\sum_{k=0}^n T^k - \sum_{k=0}^n T^{k+1} \bigg)=lim_{n\to\infty}(I-T^{n+1})=I

Cutey Proof For Neumann Series Expansion

Let’s decompose T using the Arnoldi iterations T=QHQ^T, once we write \Lambda=-H, then we could easily write:

(I-T)^{-1}=(I+Q\Lambda Q^T)^{-1}=I-IQ(\Lambda^{-1}+Q^TQ)^{-1}Q^TI=I-Q(\Lambda^{-1}+I)^{-1}Q^T

We then expand using the Woodbury identity again:

(\Lambda^{-1}+I)^{-1}=(\Lambda^{-1}+QIQ^T)=\Lambda - \Lambda Q^T(I+Q\Lambda Q^T)^{-1}Q\Lambda

substituting this in the above equation we obtain:

(I-T)^{-1}=I-Q(\Lambda^{-1}+I)^{-1}Q^T=I-Q\Lambda Q^T - Q\Lambda Q^T (I+Q\Lambda Q^T)^{-1}Q\Lambda Q^T

therefore we have, I+T+T(I+T)^{-1}T, once we apply recursively the Woodbury identity to expand (I+T)^{-1} we obtain: (I+T)^{-1}=\sum_{k=0}^\infty T^k.

This seemed a nice thing for my first post, therefore this is all from me today !

Leave a Reply

Your email address will not be published.