# Gradient of sum of products of matrix traces

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$.

-
How can the derivative of a real number be a sum of vectors? – xavierm02 Apr 16 '13 at 21:36
@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
$\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

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}}
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
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