Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a matrix $X$, we can compute its matrix exponential $e^X$. Now one entry of $X$ (say $x_{i,j}$) is changed to $b$, the updated matrix is denoted by $X'$. My problem is how to compute $e^{X'}$ from $e^X$ in a fast way?

PS: I know that if our goal is to calculate the matrix inversion (not matrix exponential), we can use Sherman–Morrison formula to compute ${X'}^{-1}$ from $X^{-1}$ easily, but currently I have not found a way to deal with the matrix exponential. Hope you can give me a hand. Thanks!

share|improve this question
    
I can't seem to find appropriate results for $\exp(\mathbf A+\mathbf u\mathbf v^\top)$. Note, however, that in practice $\exp(\cdot)$ is usually approximated by a truncation of its Taylor series or its Padé approximant, and thus a generalization of the Sherman-Morrison-Woodbury formula, due to Bernstein and Van Loan and discussed here (or see this) might be useful. –  J. M. May 10 '12 at 11:10
    
It seems too complicated for rank-one update of $exp(\cdot)$. Is there any other simple way? –  John Smith May 10 '12 at 14:33
    
$(A + uv^T)^n$ can simplify quite a bit, using the fact $v^T A^k u$ is a scalar (in fact, a linear recursive sequence). It's not immediately obvious if it will simplify enough that you can manipulate the Taylor series conveniently.... –  Hurkyl Aug 13 '12 at 16:35
add comment

2 Answers 2

up vote 2 down vote accepted

To expand on my comment, observe that

$$ vw^* A^n vw^* = \left( w^* A^n v \right) vw^* $$

so in any product of $A$'s and $vw^*$'s with more than one copy of $vw^*$, we can convert the middle part to a scalar and extract it.

Applying this and grouping like terms gives the formula

$$\begin{align} (A + vw^*)^n = A^n + \sum_{i=0}^{n-1} A^i v w^* A^{n-1-i} + \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} A^i v w^* A^j \left( w^* (A + vw^*)^{n-2-i-j} v \right) \end{align}$$

Summing this to get $\exp(A + vw^*)$, the second term yields

$$ \sum_{n=1}^{+\infty} \frac{1}{n!} \sum_{i=0}^{n-1} A^i v w^* A^{n-1-i} = \sum_{i=0}^{+\infty} A^i v w^* \sum_{n=i+1}^{+\infty} \frac{1}{n!}A^{n-1-i} $$

I'm not particularly inclined to deal with truncated exponentials of $A$. :( The third term also involves truncated exponentials of $A + vw^*$.

The path forward with this idea is not clear. I only see two ideas, and both promise to be irritating:

  • Try to come up with a simplified formula for all truncated exponentials, hoping the complicated terms cancel or otherwise collect together or have a nice recursion
  • Use combinatorics to further simplify $w^* (A + vw^*)^{n-2-i-j} v$ and hope something nice falls out.
share|improve this answer
add comment

What you are looking for is the Baker–Campbell–Hausdorff formula. You are trying to compute $$e^{X+B}$$ where $B=X'-X$ has only one non-vanishing entry. If you are lucky then $X$ and $B$ commute and you can apply the standard formula $$e^{X+B}=e^X\cdot e^B,$$ where $e^B$ is easy to compute. In gnereal you will get higher terms which involve (iterated) commutators. It is then up to the form of $X$ and $B$ whether you can find suitable bounds and appoximate the series with a finite sum.

share|improve this answer
    
The likelihood of $X$ and $B$ being commutative is small. You see that Sherman–Morrison formula for matrix inversion is elegant. Is there some simple way to update $exp(\cdot)$ ? –  John Smith May 10 '12 at 17:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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