Derivative wrt to Kronecker Product Given a function:
$\|\mathbf{y} - (\mathbf{I}\otimes\mathbf{K}) \mathbf{x}\|^2_2$
where $\mathbf{I}$ is an identity matrix, and $\mathbf{K} \in \mathbb{R}^{D \times D}$, how does one find the derivative with respect to $\mathbf{K}$?
 A: First, use the Kronecker-vec operation
$${\rm vec}(AMB^T) = (B\otimes A) {\rm vec}(M)$$
to "de-vectorize" the arguments, then find the differential and gradient
$$\eqalign{
 f &= \|(I\otimes K)x-(I\otimes I)y\|^2_F \cr
   &= \|KX-Y\|^2_F \cr
   &= (KX-Y):(KX-Y) \cr\cr
df &= 2\,(KX-Y):dK\,X \cr
   &= 2\,(KX-Y)X^T:dK \cr\cr
\frac{\partial f}{\partial K} &= 2\,(KX-Y)X^T \cr\cr
}$$
where a colon has been used to denote the Frobenius Inner Product, 
$x={\rm vec}(X)$ and $y={\rm vec}(Y)$.
A: Note that
$$
\DeclareMathOperator{\tr}{tr}
\|y - (I\otimes(K+H)) x\|^2 - \|y - (I\otimes K) x\|^2 =\\
(y - (I\otimes(K+H)) x)^T(y - (I\otimes(K+H)) x) - \|y - (I\otimes K) x\|^2=\\
2[y - (I \otimes K)x]^T(I \otimes H)x + o(\|H\|) = \\
2\tr[[(y - (I \otimes K))xx^T]^T(I \otimes H)] + o(\|H\|)
$$
So, the Frechet derivative is given by
$$
[Df(K)](H) = 2\tr[[(y - (I \otimes K))xx^T]^T(I \otimes H)]
$$
How one should write this derivative as a matrix depends on one's choice of notation, but it should be possible to get the desired form from here.
A: Here is greg's answer in vector form ( again assume lower-case=vec(upper-case) ):
Properties of Kronecker's product:
$$
\begin{aligned}
KXI = (I \otimes K) x = IKX = (X^T \otimes I) k \\
(A \otimes B)^T = (A ^T \otimes B^T)
\end {aligned}
$$
Some conventions (defining $r=y- (I\otimes K)x=y- (X^T\otimes I)k$):
$$
\begin{aligned}
&\frac{\partial f}{\partial k} = \frac{\partial f}{\partial r}\frac{\partial r}{\partial k} \\
%
&\nabla_K f = \text{mat}\left( \left( \frac{\partial f}{\partial k} \right)^T \right) \\
%
\end{aligned}
$$ 
Now let's start computing. Derivative of $f$ w.r.t to $r$:
$$
\frac{\partial f}{\partial r}=\frac{\partial r^T r}{\partial r} = 2r^T 
$$
Derivative of $r$ w.r.t to $k$:
$$
\frac{\partial r}{\partial k}=\frac{\partial}{\partial k}\left( y-(X^T\otimes I)k \right) = -(X^T\otimes I) 
$$
Chain rule to find derivative of $f$ w.r.t to $k$:
$$
\frac{\partial f}{\partial k}=\frac{\partial f}{\partial r}\frac{\partial r}{\partial k} = -2(y- (X^T\otimes I)k)^T(X^T\otimes I) 
$$
Transpose the row Jacobian matrix:
$$
\begin{aligned}
\left( \frac{\partial f}{\partial k} \right)^T=
 &-\left( 2(y- (X^T\otimes I)k)^T(X^T\otimes I) \right)^T \\
= &-2(X\otimes I)(y- (X^T\otimes I)k) \\
= &-2\text{vec}( I \text{mat}(y- (X^T\otimes I)k) X^T) \\
= &-2\text{vec}((Y-KX)X^T)\\
\end{aligned}
$$
Finally put it into matrix form:
$$
\nabla_K f = \text{mat}\left( \left( \frac{\partial f}{\partial k} \right)^T \right) 
= -2((Y-KX)X^T) = 2(KX-Y)X^T
$$
