Partial derivative of a matrix of euclidean distances I'm trying to compute the gradient of a cost function wrt. to some matrices. During the computations, I reached an expression for which I wasn't sure about its derivative.
Here's my problem : 
Let $X = (x_1,x_2,\cdots,x_n) \in \mathbb(R)_+^{M\times N}$, $F = (f_1, f_2,\cdots,f_k)\in \mathbb(R)_+^{M\times K}$ is the matrix of cluster centroids, $G = (g_1, g_2,\cdots,g_k)\in \mathbb(R)_+^{K\times N}$ indicates the matrix clustering indicators, and $D \in \mathbb(R)_+^{K\times N}$ is the matrix of the euclidean distances between each data point $X$ and the set of centroids $F$, more precisely $d_{kn} = \Vert x_n - k \Vert$.
What is the derivative of $Tr(G\circ D.(G\circ D)^T)$ wrt. $F$ ? $st. Tr$ is the trace, and $\circ$ is the Hadamard Product.
The solution I found, using the matrix cookbook formulas, is : $\frac{\partial}{\partial F} Tr(G\circ D.(G\circ D)^T) = 2(G\cdot F\circ G - G\cdot X\circ G)$
But I'm not sure about it. In case my solution is wrong, can you please provide a step by step explanation?  Thanks
 A: In the answer from Greg, you can simplify things since
$\mathbf{G} \circ \mathbf{G}=\mathbf{G}$.
The gradient vanishes when
\begin{equation}
\mathbf{F}
=
\frac{\mathbf{X} \mathbf{G}^T}{\mathbf{J}_X \mathbf{G}^T}
\end{equation}
(elementwise division).
which will be the natural way to compute a centroid given the appartenance of each example to a cluster contained in the binary matrix $\mathbf{G}$.
A: $
\def\bbR#1{{\mathbb R}^{#1}}
\def\B{B^{-1/2}}
\def\o{{\tt1}}\def\p{\partial}
\def\LR#1{\left(#1\right)}
\def\BR#1{\Bigl(#1\Bigr)}
\def\trace#1{\operatorname{Tr}\LR{#1}}
\def\Diag#1{\operatorname{Diag}\LR{#1}}
\def\qiq{\quad\implies\quad}
\def\grad#1#2{\frac{\p #1}{\p #2}}
\def\c#1{\color{red}{#1}}
\def\CBR#1{\BR{\c{#1}}}
\def\fracLR#1#2{\LR{\frac{#1}{#2}}}
$There is a very useful way to write the squared distance matrix and its differential
$$\eqalign{
D_{kn}^2 &= \|f_k-x_n\|^2 \\
D\circ D &= \LR{F\circ F}^TJ_X + J_F^T\LR{X\circ X} - 2F^TX \\
2D\circ dD &= \c{\LR{2F\circ dF}^TJ_X - 2\,dF^TX} \\
}$$
where $(J_X,J_F)$ are all-ones matrices with the same dimensions as $(X,F)$
respectively.
The Frobenius product is a convenient algebraic notation
for the trace
$$\eqalign{
A:B &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} \;=\; \trace{A^TB} \\
A:A &= \|A\|^2_F \\
}$$
Use the above to write the cost, then calculate its differential and gradient
$$\eqalign{
\phi &= \|G\circ D\|_F^2 \\
 &= (G\circ D):(G\circ D) \\
d\phi &= 2(G\circ D):d(G\circ D) \\
 &= 2(G\circ D):(G\circ dD) \\
 &= (G\circ G):(2D\circ dD) \\
 &= (G\circ G):\CBR{\LR{2F\circ dF}^TJ_X - 2\,dF^TX} \\
 &= 2(G\circ G)^T:\BR{J_X^T\LR{F\circ dF} - X^TdF} \\
 &= 2{J_X(G\circ G)^T}:\LR{F\circ dF} - 2X(G\circ G)^T:dF \\
 &= 2\BR{F\circ\LR{J_X(G\circ G)^T} - X(G\circ G)^T}:dF \\
\grad{\phi}{F}
 &= 2\BR{F\circ\LR{J_X(G\circ G)^T} - X(G\circ G)^T} \\
}$$
By defining $\,M=2(G\circ G)^T\,$ and recalling that $J$ is the identity for Hadamard multiplication, one can write the gradient in a more symmetric form
$$\eqalign{
\grad{\phi}{F} &= F\circ{J_XM} \;-\; J_F\circ{XM}
\qquad\qquad\qquad\qquad \quad
\\\\
}$$

The properties of the underlying trace function allow the terms in a
Frobenius product to be rearranged in many different but equivalent ways, e.g.
$$\eqalign{
A:B &= B:A \\
A:B &= A^T:B^T \\
C:\LR{AB} &= \LR{CB^T}:A \\&= \LR{A^TC}:B \\
}$$
Furthermore, the Hadamard product commute with the Frobenius product, i.e.
$$\eqalign{
(A\circ B):C
  \;=\; A:(B\circ C)
  \;=\; \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij}C_{ij} \\\\
}$$
Update
If the $F$ matrix must be constrained to have normalized columns, then everything derived above remains valid, but now $F$ must be constructed to satisfy the constraints using an unconstrained matrix $U$, which will act as the new independent variable
$$\eqalign{
&B = \Diag{U^TU} = I\circ\LR{U^TU} \qiq dB = 2I\circ\LR{U^TdU} \\
&F = U\B \qiq dF = dU\,\B - \tfrac 12UB^{-3/2}\,dB \\
&\Diag{F^TF} = \Diag{\B U^TU\B} = \B\Diag{U^TU}\B = I \\
&f_k = \fracLR{u_k}{\|u_k\|},
  \qquad f_k^Tf_k = \fracLR{u_k^Tu_k}{\|u_k\|^2} = {\tt1} \\
}$$
Summarize the previous result as
$$H=\grad{\phi}{F} \qiq d\phi=H:\c{dF}$$
substitute for $dF$ and perform a change of variables to $dU$
$$\eqalign{
d\phi &= H:\LR{dU\,\B - \tfrac 12FB^{-1}\,dB} \\
 &= H\B:dU \;-\; \tfrac 12B^{-1}F^TH:dB \\
 &= H\B:dU \;-\; \tfrac 12B^{-1}F^TH:\LR{2I\circ\LR{U^TdU}} \\
 &= H\B:dU \;-\; I\circ\LR{B^{-1}F^TH}:\LR{U^TdU} \\
 &= \BR{H\B \;-\; UB^{-1}\Diag{F^TH}}:dU \\
 &= \BR{H\B \;-\; F\B\Diag{F^TH}}:\c{dU} \\
\grad{\phi}{U}
 &= H\B \;-\; F\B\Diag{F^TH} \\
}$$
