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.

For a matrix $X \in \Re_{n\times d}$ find the gradient of

$\sum_{i,j}[\langle X_{i.},X_{j.} \rangle\operatorname{tr}(X^TA_{ij}X)]$ w.r.t $X$, where $A_{ij}=(e_i-e_j)(e_i-e_j)^T$ using the basis vectors while $X_{i.}$ denotes the $i$'th row. Do note that, $\langle X_{i.},X_{j.} \rangle$ can be written as $\langle X_{i.},X_{j.} \rangle = \operatorname{Tr}(X^Te_ie_j^TX)$ making the original question a sum of products of trace functions.

Hint: The gradient of $\operatorname{tr}(X^TMX)$ w.r.t $X$ for any real matrix $M$ is given by $MX+M^TX$.

share|improve this question
    
How can the derivative of a real number be a sum of vectors? –  xavierm02 Apr 16 '13 at 21:36
1  
@xavierm02 I think that as in the case of derivative of scalar w.r.t. vector: $\frac{\partial f(X)}{\partial X}$ is such a matrix $Y$ that $f(X+\Delta X)-f( X) = \langle Y,\Delta X \rangle + o(\Delta X)$, where $\langle,\rangle$ is the Euclidean scalar product. Note that $\langle Y,X \rangle = \mathrm{tr} \; (Y^T X)$ –  Nimza Apr 16 '13 at 21:40
    
@xavierm02 Refer to the table with gradients and derivatives of functions involving trace (scalar), and other matrix and vector 'valued' functions with 'domains' being scalar, vector or matrix domains at: ccrma.stanford.edu/~dattorro/matrixcalc.pdf Nimza..You are right. –  halms Apr 16 '13 at 21:40
    
I don't get how the derivative of $\operatorname{tr}(X^TMX)$ (scalar) can be $MX+M^TX$ (vector)... –  xavierm02 Apr 16 '13 at 22:25
1  
$\langle X_{i.},X_{j.} \rangle = \mathop{\textrm{Tr}}(X^Te_ie_j^TX).$ Given the structure of $A_{ij}$ that seems rather important... –  Michael Grant Apr 19 '13 at 16:09

1 Answer 1

up vote 1 down vote accepted
+50

First, let's normalize the notation by rewriting the inner product. $$\langle X_{i.},X_{j.} \rangle = \mathop{\textrm{Tr}}(X^Te_ie_j^TX) = \tfrac{1}{2}\mathop{\textrm{Tr}}(X^T(e_ie_j^T+e_je_i^T)X)$$ Let $B_{ij}\triangleq e_ie_j^T+e_je_i^T$. The expression, which we will call $f(X)$, simplifies to $$ f(X)=\tfrac{1}{2}\sum_{ij} \mathop{\textrm{Tr}}(X^TB_{ij}X)\mathop{\textrm{Tr}}(X^TA_{ij}X) $$ The gradient follows from a combination of the standard product rule and the fact that $\nabla X\mathop{\textrm{Tr}}(X^TPX)=2PX$ when $P$ is a symmetric constant. (This is why we took the extra symmetrizing step above.) The gradient is $$ \nabla_Xf(X)=\sum_{ij} \mathop{\textrm{Tr}}(X^TB_{ij}X)A_{ij}X + \mathop{\textrm{Tr}}(X^TA_{ij}X)B_{ij}X = (Q + R) X, $$ where $Q$ and $R$ are defined as follows: $$ Q \triangleq \sum_{ij} \mathop{\textrm{Tr}}(X^TB_{ij}X)A_{ij}, \quad R \triangleq \sum_{ij} \mathop{\textrm{Tr}}(X^TA_{ij}X)B_{ij}. $$ Let's find some clean expressions for $Q$ and $R$. For $Q$, we have $$ \mathop{\textrm{Tr}}(X^TB_{ij}X) = \mathop{\textrm{Tr}}(X^T(e_ie_j^T+e_je_i^T)X) = 2e_i^TXX^Te_j = 2Z_{ij} $$ where $Z\triangleq XX^T$. Continuing: $$ Q = \sum_{ij} 2Z_{ij}A_{ij} = \sum_{ij} 2Z_{ij}(e_i-e_j)(e_i-e_j)^T = \sum_{ij} 2Z_{ij} ( e_ie_i^T + e_je_j^T - e_ie_j^T - e_je_i^T ) $$ For each $(i,j)$, this expression adds $Z_{ij}$ to elements $Q_{ii}$ and $Q_{jj}$, and subtracts $Z_{ij}$ from $Q_{ij}$ and $Q_{ji}$. (When $i=j$, these steps cancel.) The total is then multiplied by two. This will do that: $$ Q = 2(\mathop{\textrm{diag}}(Z\textbf{1})+\mathop{\textrm{diag}}((\textbf{1}^TZ)^T)-Z-Z^T)=4\mathop{\textrm{diag}}(Z\textbf{1})-4Z $$ The $\mathop{\textrm{diag}}$ operator constructs a diagonal matrix from a column vector. You can verify this result by substituting $Z\rightarrow Z_{ij}e_ie_j^T$ into the first form for $Q$ above and simplifying; the result should equal the $(i,j)$ summand.

Now consider the second term in the summation: $$\begin{aligned} \mathop{\textrm{Tr}}(X^TA_{ij}X) &= \mathop{\textrm{Tr}}(X^T(e_i-e_j)(e_i-e_j)^TX) \\& = (e_i-e_j)^TXX^T(e_i-e_j) = Z_{ii}+Z_{jj}-Z_{ij}-Z_{ji}\end{aligned}$$ $$ R=\sum_{ij} \mathop{\textrm{Tr}}(X^TA_{ij}X)B_{ij} = \sum_{ij} (Z_{ii}+Z_{jj}-Z_{ij}-Z_{ji})(e_ie_j^T+e_ie_j^T) $$ This summation copies each quantity $Z_{ii}+Z_{jj}-Z_{ij}-Z_{ji}$ to the $(i,j)$ and $(j,i)$ positions. Thus $R$ is $$R=2(\mathop{\textrm{diag}^*}(Z)\textbf{1}^T+\textbf{1}\mathop{\textrm{diag}^*}(Z)^T-Z-Z^T)=2\mathop{\textrm{diag}^*}(Z)\textbf{1}^T+2\textbf{1}\mathop{\textrm{diag}^*}(Z)^T-4Z.$$ The $\mathop{\textrm{diag}^*}$ operator extracts the diagonal elements of a matrix into a column vector.

The final result, therefore, is $$ \boxed{ \begin{aligned} \nabla_X f(X) &= (4\cdot\mathop{\textrm{diag}}(XX^T\textbf{1}) +2\cdot\mathop{\textrm{diag}^*}(XX^T)\textbf{1}^T \\ &\quad +2\cdot\textbf{1}\mathop{\textrm{diag}^*}(XX^T)^T -8\cdot XX^T)X. \end{aligned}} $$

share|improve this answer
    
Given $X$ is of dimension $n \times 2$ we get that $XX^T\mathbb{1}$ is $n \times 1$ dimensions. What does $diag(XX^T\mathbb{1})$ mean as we are looking for a diagonal of a column vector? –  halms Apr 20 '13 at 21:56
    
Two different operators here. $\mathop{\textrm{diag}}$ creates a diagonal matrix from a vector. Its adjoint $\mathop{\textrm{diag}^*}$ extracts the diagonal from a matrix, returning a vector –  Michael Grant Apr 20 '13 at 22:06
    
Got it. So, you meant diag takes as input a vector! Thanks for the answer with the clear explanation of the manipulations. –  halms Apr 20 '13 at 22:07
    
Right. It is confusing because MATLAB uses the same command for both directions. So in formulae I try to be consistent and use the adjoint notation to differentiate between the two operations. –  Michael Grant Apr 20 '13 at 22:08
    
also a quick question, is there some software that would allow a symbolic entry of the gradient equation in this answer, so that I can solve the system for $X$ easily? or do you see this as more complicated! I hope if done on paper, the system dosn't look like a Sylvester equation, or some complicated format ;) –  halms Apr 20 '13 at 22:09

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.