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 was reading the following derivation of the Kalman filter gain http://www.robots.ox.ac.uk/~ian/Teaching/Estimation/LectureNotes2.pdf on pg 5-6.

From the following

$$L=\min_{K_{k+1}} trace(P_{k+1|k+1})$$

With

$$ P_{k+1|k+1} = \boldsymbol{ (I-K_{k+1} H_{k+1}) P_{k+1|k} (I-K_{k+1} H_{k+1})^{T} + K_{k+1}R_{k+1}K_{k+1}^T }$$

K,H, and P are all nxn matrices.

It uses the following trace differentiation identity:

$${\frac{\partial}{\partial \boldsymbol{A}}} (trace(\boldsymbol{ABA^T})) = 2\boldsymbol{AB}$$

But from there, there is a bit of a skip to the result of the differentiation

$${\frac{\partial L}{\partial \boldsymbol{ K_{k+1}}}} = -2(\boldsymbol{I-K_{k+1}H_{k+1})P_{k+1|k}H_{k+1}^T+2K_{k+1}R_{k+1} } = 0$$

What I am wondering about is the origin of the $H_{k+1}^T$ term in the above equation.

It appears to me that chain rule is applied here. But most online sources on matrix chain rule or trace identities does not show a direct example that the chain rule can be applied to the derivative of a trace.

ie. This is what I think happens in the intermediate step:

$$\boldsymbol{A=I-K_{k+1} H_{k+1}; B=P_{k+1|k}}$$

$${\frac{\partial}{\partial \boldsymbol{K_{k+1}}}} (trace(\boldsymbol{ABA^T})) = 2\boldsymbol{AB} * {\frac{\partial (trace (\boldsymbol{A}))}{\partial \boldsymbol{ K_{k+1}}}}$$

Question: Is the above chain rule application valid? If so, I would appreciate a pointer to a proof.

And then using

$$ {\frac{\partial trace(\boldsymbol{K_{k+1}H_{k+1}} )} {\boldsymbol{\partial K_{k+1}}}} = \boldsymbol{H_{k+1}^T} $$

To arrive at

$$ = -2(\boldsymbol{I-K_{k+1} H_{k+1}) * P_{k+1|k} * H_{k+1}^T}$$

If the intermediate steps is actually different, please let me know and link to any proofs of the identities used as I am self-learning linear algebra. Thanks.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Firstly $\nabla_A(ABA^T)=A(B+B^T)=2AB$ only if $B$ is symmetric.

Here $L=trace((I-KH)Q(I-KH)^T+KRK^T)$ where $Q,R$ are symmetric matrices. The derivative is $DL_K:Z\rightarrow trace(-ZHQ(I-KH)^T+(I-KH)Q(-ZH)^T+ZRK^T+KRZ^T)=trace(-2ZHQ(I-KH)^T+2ZRK^T)=trace((-2HQ(I-KH)^T+2RK^T)Z)$.

I wrote that follows in at least 10 posts but nobody reads my post (tears). Yet, no students know how to calculate a gradient. Incredible !

A gradient is associated to a scalar product; we take, here, $(U,V)=trace(U^TV)$. The associated gradient is defined by, for every $Z$, $(\nabla_K(L),Z)=DL_K(Z)$. Thus $\nabla_K(L)=-2(I-KH)QH^T+2KR$.

EDIT (answers to frank): 1),2) $DL_K$ is a linear application and $Z$ is the variable. For instance, if $f:K\rightarrow KAK$, then $Df_K:Z\rightarrow ZAK+KAZ$, the derivative of a product ! ($(uv)'=u'v+uv'$). If $f:K\rightarrow -KHQ$, then $Df_K:Z\rightarrow -ZHQ$. $(ua)'=u'a$.

3) Here $Df_X:(h,k,l)\rightarrow [3z,4y^3,3x][h,k,l]^T$. We use the scalar product over vectors $(u,v)=trace(u^Tv)=u^Tv$. Then $\nabla_Xf=[3z,4y^3,3x]^T$. More generally, to define a gradient with the help of a scalar product has a geometric meaning. You do not need a basis.

4) The derivative uses trace and the gradient not. It is linked to the chosen scalar product.

5) Consider the application $f:K\in\mathcal{M}_n(\mathbb{R})\rightarrow KAK\in\mathcal{M}_n(\mathbb{R})$, then the derivative is the linear application $Df_K:Z\in\mathcal{M}_n(\mathbb{R})\rightarrow ZAK+KAZ\in\mathcal{M}_n(\mathbb{R})$. In the same way, if $g(K)=K^3$, then $Dg_K(Z)=ZK^2+KZK+K^2Z$. If you choose coordinates, then the matrix of the derivative is its Jacobian. For 3), $f:\mathbb{R^3}\rightarrow \mathbb{R}$ and let $X=[x,y,z]^T$. $Df_X$ is a linear application $(h,k,l)\in\mathbb{R^3}\rightarrow \mathbb{R}$ and , consequently, its matrix (the Jacobian) is $1\times 3$, that is a row. The gradient is the transpose of the previous matrix, that is a vector.

share|improve this answer
    
Thanks, a few follow-ups –  frank Oct 16 '13 at 4:08
    
1) What is variable Z in the first part $DL_K:Z$? $DL_K$ is already taking the derivative of L with respect to K. And is the : Z the Frobenius inner product notation? Why is that notation necessary? 2) Since trace is linear, d tr(X) = tr(dX). When you are taking the derivative of the trace, how does the -KH)Q term become -ZHQ? Seems like the product rule, for the first term, you held (I-KH)^T constant. But K, H, Q are nxn, and d(-KHQ)/dK would be the derivative of a matrix by a matrix, which should be undefined? –  frank Oct 16 '13 at 4:21
    
3) I know how to calculate a gradient like so from math.umn.edu/~mathe233/math2263/resources/… If f(x,y,z) = 3xz + y^4 Df(x,y,z) = [3z 4y^3 3x] $\nabla_f(x,y,z) = (3z, 4y^3, 3x)$ Using the expression above, Our K is like the x,y,z. the f function is like the L. So the expression of taking the gradient of L with respect to K I understand, but the additional taking the Frobenius product with Z I don’t understand. –  frank Oct 16 '13 at 4:26
    
4) I read (U,V) is a notation for Frobenius inner product. $DL_K:Z$ is also a Frobenius inner product notation, so $DL_K:Z$ from your reply is the same as ($DL_K$, Z) = trace(U^TV). And we have V=Z, we get $DL_K$ which is what we wanted to solve. Why do we need the extra expression for ($\nabla_K(L),Z) = $DL_K$(Z)? Gradient and matrix derivative are largely same, no? pg 4 of math.umn.edu/~mathe233/math2263/resources/… –  frank Oct 16 '13 at 4:28
    
5) Thanks for the update. I think I get the idea of the steps, so I will accept the answer. In 1) the switch to Z still looks funny, "if $f:K\rightarrow KAK$, then $Df_K:Z\rightarrow ZAK+KAZ$ ". The K in $Df_K$ should already specify the derivative is with respect to K, is there a difference between saying $Df_K:Z$ and $Df_K:K$? What is Z equal to? I tried to search for "linear application" to see if I can find more examples, but that combination in web search turn out too many random things. In 3), I did not have h,k,l, but you had $Df_x : (h,k,l), is that same as Df_x : (x,y,z)? –  frank Oct 17 '13 at 7:31

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.