Vrftsjtryk

I have a question about differentiating an expression which has multiple kronecker products.

I have the following objective function I would like to differentiate with respect to $mathbf{Q}$:
begin{equation*}
lVertmathbf{y}-mathbf{A}(mathbf{Q}otimesmathbf{Q}otimesmathbf{Q}otimesmathbf{Q})mathbf{x}rVert^2_2
end{equation*}
where $mathbf{y}inmathbb{R}^m$, $mathbf{A}inmathbb{R}^{mtimes K^4}$, $mathbf{Q}inmathbb{R}^{Ktimes K}$ and $mathbf{x}inmathbb{R}^{K^4}$. I am confused with how the chain rule works with respect to matrix differentiation. This is how I proceeded:

Let $ f=lVertmathbf{y}-mathbf{A}(mathbf{Q}otimesmathbf{Q}otimesmathbf{Q}otimesmathbf{Q})mathbf{x}rVert^2_2$
and $mathbf{B}=mathbf{Q}otimesmathbf{Q}otimesmathbf{Q}otimesmathbf{Q}$. Therefore $frac{df}{dmathbf{Q}}=frac{df}{dmathbf{B}}frac{dmathbf{B}}{dmathbf{Q}}$

When I calculate $frac{df}{dmathbf{B}}=mathbf{A}^T(mathbf{y}-mathbf{ABx})mathbf{x}^T$ I gain a $mathbb{R}^{K^4times K^4}$ matrix not a $mathbb{R}^{Ktimes K}$ matrix that I am hoping for.
Therefore I am using the chain rule wrong because of the change in dimensions i.e scalar to matrix.

Thank you for your help in advance.

Short answer: the derivative of $Qotimes Qotimes Qotimes Q$ with respect to $Q$ is a mess, at first sight...

Let's start simple. Let $Q$ be a $Ktimes K$ matrix with entries $Q_{ij}$ and let $E^{ab}$ be the $Ktimes K$ matrix with all $0$ entries, except the entry $(a,b)$ which is $1$; in other words, $(E^{ab})_{ij} = delta_a^idelta_b^j$.

Then I claim that
$$
frac{partial(Qotimes Q)}{partial Q_{ij}} = E^{ij}otimes Q+Qotimes E^{ij} .
$$
I leave it to you to see why, because trying to write out the involved matrices will probably crash the entire Stack Exchange network...

Jokes aside, this is really immediate to see: just write $Qtimes Q$ as in the first formula of the definition and think which elements are affected by $Q_{ij}$. There is the entire $(i,j)$th block, so you get $E^{ij}otimes Q$, but there is also the $(i,j)$th entry in each block, which gives you $Qotimes E^{ij}$.

Now, if $A$ and $B$ are matrices which are functions of $Q$, by the same reasoning you get
$$
frac{partial(Aotimes B)}{partial Q_{ij}} = frac{partial A}{partial Q_{ij}}otimes B + Aotimes frac{partial B}{partial Q_{ij}} .
$$

So you can iterate for instance
$$
begin{split}
frac{partial (Qotimes Qotimes Q)}{partial Q_{ij}}
&= frac{partial(Qotimes Q)}{partial Q_{ij}}otimes Q
+ (Qotimes Q)otimes frac{partial Q}{partial Q_{ij}} \
&= (E^{ij}otimes Q+Qotimes E^{ij})otimes Q + (Qotimes Q)otimes E^{ij} \
&= E^{ij}otimes Qotimes Q + Qotimes E^{ij}otimes Q + Qotimes Qotimes E^{ij}.
end{split}
$$

Now you can prove by induction that
$$
frac{partial bigl(bigotimes_{n=1}^N Qbigr)}{partial Q_{ij}}
= sum_{n=1}^N left(bigotimes_{h=1}^{n-1} Qright) otimes E^{ij} otimes left(bigotimes_{h=n+1}^{N} Qright).
$$

Written more concisely,
$$
frac{partial Q^{otimes N}}{partial Q_{ij}}
= sum_{n=1}^N Q^{otimes (n-1)}otimes E^{ij} otimes Q^{otimes (N-n)} .
$$