I'd like to find the gradient of $\frac{1}{2} ||X A^T||_F^2$ with respect to $X_{ij}$.

Going by the chain rule in the Matrix Cookbook (eqn 126), it's something like

$\partial \left[\frac{1}{2} ||X A||_F^2 \right]/\partial X_{ij}= Tr[(XA^T)^T (J^{jk} A^T)]$, where J has same dimensions as X and has zeros everywhere except for entry (j,k).

I'm not so sure about the $J^{jk} A^T$ bit (cookbook eqn 66 applies here?).

Thanks.

-

Recall that if $A,B \in \mathbb{R}^{m \times n}$ then $$\langle A, B \rangle = \text{Tr}(A^T B)$$ and \begin{align*} \|A\|_F^2 &= \langle A,A \rangle \\ &= \text{Tr}(A^T A) \\ &= \text{Tr}(A A^T). \end{align*}

Let $f:\mathbb{R}^{m \times n} \to \mathbb{R}$ such that \begin{align*} f(X) &= \frac12 \| X A^T \|_F^2 \\ &= \frac12 \text{Tr}(X A^T A X^T). \end{align*} Let $J$ be the $m \times n$ matrix whose entries are all $0$ except $J_{ij}$ which is equal to $1$. Let $\Delta X = \epsilon J$, where $\epsilon > 0$ is tiny.

Then

\begin{align*} f(X + \Delta X) &= \frac12 \text{Tr}((X + \Delta X)A^T A (X + \Delta X)^T) \\ &= \frac12 \text{Tr}(X A^T A X^T) + \frac12 \text{Tr}(\Delta X A^T A X^T) + \frac12 \text{Tr}(X A^T A \Delta X^T) \\ & \qquad + \frac12 \text{Tr}(\Delta X A^T A \Delta X^T) \\ &\approx \frac12 \text{Tr}(X A^T A X^T) + \frac12 \text{Tr}(\Delta X A^T A X^T) + \frac12 \text{Tr}(X A^T A \Delta X^T) \\ &= \frac12 \text{Tr}(X A^T A X^T) + \text{Tr}(X A^T A \Delta X^T) \\ &= f(X) + \left\langle X A^T A,\Delta X \right\rangle \\ &= f(X) + \epsilon \left \langle X A^T A,J \right\rangle. \end{align*}

Comparing this result with the equation $$f(X + \epsilon J) \approx f(X) + \epsilon \frac{\partial f(X)}{\partial X_{ij}}$$ we see that $$\frac{\partial f(X)}{\partial X_{ij}} = \left \langle X A^T A,J \right\rangle.$$

-
thanks, I think there's a mistake in the second line of f(X + delta X), where the first term should be 1/2 Tr(X A^T A X^T) to match your definition of the Frobenius norm in terms of trace earlier. –  purple51 Nov 11 '12 at 23:08
Thanks. I think I fixed it, but let me know if you see any other errors. –  littleO Nov 12 '12 at 6:35
Why do you say that all entries of J are zero and then say that all entries (J_ij) are 1? Or did you mean to say that the diagonal entries i.e. J_ii are 1? –  Stephen Tierney Oct 17 '13 at 23:29
@StephenTierney $J$ has only one nonzero entry -- namely, $J_{ij}$. I'm viewing $i$ and $j$ as given, fixed indices, and we want to compute $\frac{\partial f(X)}{\partial X_{ij}}$. –  littleO Oct 18 '13 at 1:59