So, lets assume that we have two matrices given to us:

$A \in \mathbb{\Re}^{M \times K}$: just some dense, real, arbitrary valued matrix.

$L \in \Re^{K \times K}$: A positive diagonal matrix

Now, lets say we have the following situation:

$\left( A^T A + L \right)^{-1}$

Is it possible to rephrase this statement in such a way as to make use of the knowledge of $\left( A^T A \right)^{-1}$ so as to avoid this addition inside the inverse?

I'm sorry if this is a little vague :P Just running into an analytical hiccup and trying to figure out how to break this statement apart.

Edit: Would it be possible to analyze this expression using an eigen decomposition? That is, if we say

$A^T A = Q \Lambda Q^{-1}$

Then, if $L$ is diagonal:

$\left( A^T A + L \right) = Q \left( \Lambda + L \right) Q^{-1}$

Which would make

$\left( A^T A + L \right)^{-1} = Q \left( \Lambda + L \right)^{-1} Q^{-1}$

Which might be usable somehow because $\left( \Lambda + L \right)$ is a diagonal matrix and allowing you to calculate the inverse directly by taking $1$ over the diagonal entries, right? Or is this completely off?

Edit 2: @Rcollyer So, I changed around my formulation entirely by only looking at rank 1 updates of $A^T A$ and was able to use the Sherman-Morrison (a form of the Woodbury) formula to break it apart and get at what I wanted :P

  • $\begingroup$ 1. An expression is not a statement. 2. What is a dense matrix? 3. $A^T A$ is not invertible, in general. $\endgroup$ – Rasmus Jun 2 '11 at 1:01
  • $\begingroup$ I take dense to mean, not sparse - that is, most of the entries are non-zero. $\endgroup$ – Gerry Myerson Jun 2 '11 at 1:18
  • $\begingroup$ Gerry: Correct, I just mean that it isn't sparse in any sense. $\endgroup$ – Eric Jun 2 '11 at 1:25

The only method I am aware of is the Sherman–Morrison formula for performing a rank-1 update of an inverse, or its generalization, the Woodbury matrix identity for performing rank-k updates. In both cases, their advantage lies in the fact that $L$ does not have full rank. If $L$ has full rank, these methods won't provide you with enough speed up to make them worth it over just performing an LU decomposition on $A^{\mathrm{T}}A + L$ directly.

I ran into a similar problem where I potentially had several hundred to several thousand matrices to invert where the portion of the matrix sum that was changing had full rank, and LU decomposition was the best I was able to come up with.

Edit: Hunting through my stack of papers, I came across a good review of these techniques.

Edit (2nd question): Your second approach doesn't work, in general. The error is in the second equation, it should be

$$ \begin{align} A^\mathrm{T}A + L &= Q \Lambda Q^{-1} + L \\ &= Q \Lambda Q^{-1} + Q Q^{-1} L Q Q^{-1} \\ &= Q( \Lambda + Q^{-1} L Q )Q^{-1} \end{align} $$

In general, $Q^{-1} L Q$ is not diagonal, unless $L$ commutes with $Q$ which usually only occurs when it is proportional to $I$.

Edit (idyl speculation): Upon reviewing the second question, I though of a way that may allow you to use that method. As stated previously, the only way for the second method to work is for $L$ to commute with $Q$. Since $L$ is diagonal, we can rewrite $L$ as $\alpha I + N$, where $\alpha$ is the most common diagonal element of $L$. Then, the rank of $N$ will be less than the rank of $A^\mathrm{T}A$. Thus, we can calculate $(A^\mathrm{T}A + L)^{-1}$ in two steps: calculate

$$B^{-1} = Q(\Lambda + \alpha I)^{-1}Q^{-1}$$

and then perform a $\text{rank}(N)$ update of $B^{-1}$ using the Woodbury matrix identity. If all the diagonal elements of $L$ are equally common, $\text{rank}(N) = \text{rank}(A^\mathrm{T}A) - 1$. So, this method is likely only worth it if you have many different $L$ matrices, and the cost of diagonalizing $A^\mathrm{T}A$ can be amortized. Obviously, the larger $A^\mathrm{T}A$ is, the smaller the difference between $\text{rank}(N)$ and $\text{rank}(A^\mathrm{T}A)$ for you to see a net benefit, but it will require some thought as to whether it is worth it, overall.

  • $\begingroup$ Thanks for the answer, it seems like its all kind of up the creek when you're looking at a full rank update. $\endgroup$ – Eric Jun 2 '11 at 22:23
  • $\begingroup$ I'm batting zero, here, hah! Thanks again for the answer :) $\endgroup$ – Eric Jun 3 '11 at 1:19
  • $\begingroup$ @Eric, I went through the same set of trials with my research, so batting zero is average! I'd recommend the books by G. W. Stewart (1, 2). Eventually, there will be 5 volumes, but the first two alone will improve how you think about matrix problems. $\endgroup$ – rcollyer Jun 3 '11 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.