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.

I have the following vector function $f(\mathbf{x})=\operatorname{Tr}[(\mathbf{A}+\operatorname{diag}(\mathbf{x}))^{-1}]$ where $\operatorname{diag}(\mathbf{x})$ is the diagonal matrix with values from $n\times 1$ vector $\mathbf{x}$ on the diagonal, and $\mathbf{A}$ is an $n\times n$ matrix (assume that $\mathbf{A}+\operatorname{diag}(\mathbf{x})$ is invertible). I know that one can express the trace as the sum of quadratic forms involving orthonormal basis vectors $\mathbf{e}_i$, thus we can also write $f(\mathbf{x})=\sum_{i=1}^n\mathbf{e}_i^T(\mathbf{A}+\operatorname{diag}(\mathbf{x}))^{-1}\mathbf{e}_i$.

I am interested in $\frac{\partial f}{\partial x_i}$. Is there a way to express it in terms of $\mathbf{A}$, $\mathbf{x}$ and $\mathbf{e}_i$?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

Here is what you can try: Using the definition of partial derivative, consider $f(x+t e_i)-f(x)$ for some $t \in \mathbb{R}$. We have $$ f(x+t e_i) = \text{Tr}((A + \text{diag}(x) + t e_i e_i^T)^{-1}).$$ You can now apply matrix inversion lemma: http://en.wikipedia.org/wiki/Woodbury_matrix_identity You should be able to isolate $f(x)$ in the expansion and it should not be hard to get the desired partial derivative from the leftover.

EDIT: Let me elaborate some more. Let $\Gamma = A + \text{diag}(x)$. Apply Woodbury identity with $A = \Gamma$, $U = t e_i$, $C = 1$ (the scalar 1) and $V = e_i^T$. You get $$ f(x + te_i) = \text{Tr} \Big( \Gamma^{-1} - t \frac{\Gamma^{-1} e_i e_i^T \Gamma^{-1}}{1 + t e_i^T \Gamma^{-1} e_i} \Big). $$ Now, apply the trace to obtain (using invariance of trace under cyclic permutation), $$ f(x + te_i) = f(x) + \frac{-t \,e_i^T \Gamma^{-2} e_i}{1+ t \,e_i^T \Gamma^{-1} e_i}. $$ Hence, $$ \frac{1}{t} [ f(x + te_i) - f(x) ] \to - e_i^T \Gamma^{-2} e_i $$ as $t \to 0$, which is the desired partial derivative (if I haven't made any mistake.)

EDIT2: Let me also add this for a general problem. You can avoid Woodbury identity and instead use von Neumann expansion of $(I-B)^{-1} = I + B +B^2 + \dots$ for $\|B\| < 1$. So, in this problem for $t$ small enough, we have (using $(CD)^{-1}= D^{-1} C^{-1}$) \begin{align*} f(x + te_i) &= \text{Tr} [( I + t \Gamma^{-1} e_i e_i^T)^{-1} \Gamma^{-1} ]\\ &=\text{Tr} \big[ \big\{ I - t \Gamma^{-1} e_i e_i^T + o(t)\big\} \Gamma^{-1} \big] \\ &= \text{Tr} \big[ \Gamma^{-1} - t \Gamma^{-1} e_i e_i^T \Gamma^{-1} + o(t)\big] \\ &= f(x) - t (e_i^T \Gamma^{-2} e_i) + o(t) \end{align*} which is the desired result. This approach seems more general and more straightforward. It also produces the entire Taylor expansion of the function. (The previous one using Woodbury can also give you this, as you end up with a function of one variable $t$ as the leftover which can be expanded using usual Taylor series.)

share|improve this answer
    
Helo! is not necessary to clarify first that U is an open set ? (where $U=\{x / A + diag(x) \quad \text{is invertible } \} $) –  user33218 Jun 8 '12 at 3:51
    
Couple of comments: in the line after "EDIT" you state "Let $\Gamma = A + \operatorname{x}$" and then you state "with $A=\Gamma$". Not sure what's going on here... EDIT: Ahh, now I get it, you're replacing the symbols in the Woodbury on the wikipedia page! –  M.B.M. Jun 8 '12 at 4:31
1  
Nice. I will (+1) when I can vote again. –  user26872 Jun 8 '12 at 5:18
    
@M.B.M, yes you are right, I meant using the identity with $A$ replaced with $\Gamma$. This is unfortunate as everyone usually uses $A$ to denote something ... . –  passerby51 Jun 8 '12 at 10:26
1  
@Mohamed: If I am not wrong, $B$ being inevitable implies $B+\Delta$ for small enough perturbation $\Delta$, as can be seen from von Neumann series mentioned above. (Also, it might have been better to add your question as a comment to the original post, as you are not answering the question.) –  passerby51 Jun 8 '12 at 10:59
show 2 more comments

$\def\e{{\bf e}} \def\D{\mathrm{diag}(\x)} \def\x{{\bf x}} \def\A{{\bf A}} \def\M{{\bf M}} \def\Mi{{\bf M}^{-1}} \def\P{{\bf P}_i} \def\id{\mathbb{I}} \def\tr{\mathrm{Tr}\,}$ Let $\M = \A + \D$. Note that $d(\M\Mi) = d \id = {\bf 0}$. Thus, $d\Mi = -\Mi d \M \Mi$, and so $$\begin{eqnarray*} d \tr \Mi &=& d \sum \e_i^T \Mi \e_i \\ &=& \sum \e_i^T d \Mi \e_i \\ &=& -\sum \e_i^T \Mi d \M \Mi \e_i. \end{eqnarray*}$$ If $\A$ is a function of $\x$, this is about as far as we'll go, $$\begin{eqnarray*} \frac{\partial}{\partial x_i} \tr \Mi &=& -\sum_j \e_j^T \Mi \frac{\partial \M}{\partial x_i} \Mi \e_j \\ &=& -\tr \left((\Mi)^2 \frac{\partial \M}{\partial x_i}\right). \end{eqnarray*}$$

If $\A$ is not a function of $\x$ we have that $\P = \frac{\partial \M}{\partial x_i}$ is a projection operator. (All components of $\P$ are zero except the $ii$th component, which is $1$.) In that case we find $$\begin{eqnarray*} \frac{\partial}{\partial x_i} \tr \Mi &=& -\sum_j \e_j^T \Mi \P \Mi \e_j \\ &=& -\tr \left((\Mi)^2 \P\right) \\ &=& -(\Mi)^2_{ii} \\ &=& -\sum_j \Mi_{ij}\Mi_{ji}. \end{eqnarray*}$$

In terms of $\A$, $\x$, and $\e_i$, $$\begin{eqnarray*} \frac{\partial}{\partial x_i} f(\x) &=& -\sum_j \e_j^T (\A + \D)^{-1} \frac{\partial \D}{\partial x_i} (\A + \D)^{-1} \e_j \\ &=& -\sum_j \e_j^T (\A + \D)^{-1} \P (\A + \D)^{-1} \e_j. \end{eqnarray*}$$ As noted by @passerby51 we could find an expression for $(\A + \D)^{-1}$ in terms of $\A^{-1}$ and $\D^{-1}$, but we will stop here.

Addendum: We made no assumptions about the basis $\e_i$. If $\e_i$ is the natural basis the above implies $$\begin{eqnarray*} \frac{\partial}{\partial x_i} f(\x) &=& -\e_i^T (\A + \D)^{-2} \e_i, \end{eqnarray*}$$ which agrees with @passerby51's result. (Note that in this case $\P = \e_i \e_i^T$.)

By the Woodbury formula, $$\begin{eqnarray*} (\A+\D)^{-1} &=& \A^{-1} - \A^{-1}(\A^{-1} + \D^{-1})^{-1} \A^{-1}. \end{eqnarray*}$$ This may or may not be useful depending on the form of $\A$.

share|improve this answer
2  
I guess your answer is the same as mine after rearranging, that is, $-\text{Tr} (\Gamma^{-1} P_i \Gamma^{-1}) = -\text{Tr}(\Gamma^{-1} e_i e_i^T \Gamma^{-1}) = -e_i^T \Gamma^{-2} e_i$, with $\Gamma$ being the $A + \text{diag}(x)$. –  passerby51 Jun 8 '12 at 4:22
    
Hmm.... I'm trying to digest all this. Actually, finding the expression in terms of $\mathbf{A}^{-1}$ would be fine as well (in my particular problem it has a very nice form). –  M.B.M. Jun 8 '12 at 4:24
    
@passerby51: Yes, I believe we agree. :-) –  user26872 Jun 8 '12 at 4:49
1  
@M.B.M.: I show above how to write the relevant inverse in terms of ${\bf A}^{-1}$ and $\mathrm{diag}({\bf x})^{-1}$ and connect the result with passerby51's. –  user26872 Jun 8 '12 at 5:14
    
Goodness! Thank you to both of you. Its really hard to accept either answer, because both are very good... –  M.B.M. Jun 8 '12 at 5:25
show 3 more comments

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.