# Matrix calculus : Find the gradient/derivative?

I know that the derivative of $Tr(Z^TAZ)$ w.r.t $Z$ is $2AZ$. Now I'd like to compute the derivative of $Tr\left[Z^T\left( \operatorname{diag}(ZZ^T\mathbf{1}) - ZZ^T\right)Z\right]$ instead, w.r.t $Z$ correctly. I'd like to see, how this would be done, given my basic matrix calc skills . All the entries are real and both $A$ and $\operatorname{diag}[(ZZ^T\mathbf{1}) - ZZ^T]$ are symmetric and $Z$ is a tall, rectangular matrix (more rows than columns), while $diag(.)$ denotes a diagonal matrix, whose diagonal elements are specified by the placeholder $'.'$ and I think that $\left(\operatorname{diag}(ZZ^T\mathbf{1}) - ZZ^T\right)$ is p.s.d, as it seems like it is in the form of a Laplacian matrix.

-
$\partial(\operatorname{tr}(Z^T A Z))/\partial X= (A+A^T)X$. Is $A$ symmetric? –  Jacob Apr 9 '13 at 23:35
Yes! It is symmetric. I'd mention that above. Can you go ahead with the derivative now..under the symmetric condition in the second problem where the $A$ part is a function of $Z$? –  halms Apr 9 '13 at 23:37
The derivative of the trace of $Z^T AZ$ can't possibly be $2AZ$. Trace is a real-valued operator whereas $2AZ$ is matrix-valued. –  Christopher A. Wong Apr 9 '13 at 23:55
It surely can be a matrix. All the matrix trace derivatives in this link from berkeley have results that are matrices: cs.berkeley.edu/~jduchi/projects/matrix_prop.pdf and @Jacob also, concurs with this. –  halms Apr 10 '13 at 0:00
@ChristopherA.Wong I don't think it is really less consistent in this case. The identification $M_n(\mathbb{R})^*\simeq M_n(\mathbb{R})$ via trace representation is as natural, via the inner product $\mbox{Tr}(X^*Y)$. Just like $\mathbb{R}^{n*}$ is identified with $\mathbb{R}^n$ via the Euclidean inner product. But you're right, it should be mentioned as it is less frequent. –  1015 Apr 10 '13 at 3:54

Let's do this. I like to use a variational approach in a case like this, since it's just sums and products. Well, there's the pesky diag term too, but we'll get to that last.

First, let's separate the additive terms: $$\mathop{\textrm{Tr}}(Z^T\mathop{\textrm{diag}}(ZZ^T\mathbf{1})Z-Z^TZZ^TZ)$$ Now we substitute $\delta Z$ for each value of $Z$ present, creating a separate additive term each time. This is equivalent to substituting $Z\rightarrow Z+\delta Z$, subtracting any constant ($Z$ only) terms, and eliminating any higher-order terms in $\delta Z$. (This is not true in general, but when we have sums and products like this, it's fine.) The result is \begin{aligned} \mathop{\textrm{Tr}}( &Z^T\mathop{\textrm{diag}}(\delta ZZ^T\mathbf{1})Z +Z^T\mathop{\textrm{diag}}(Z\delta Z^T\mathbf{1})Z \\ &+\delta Z^T\mathop{\textrm{diag}}(ZZ^T\mathbf{1})Z +Z^T\mathop{\textrm{diag}}(ZZ^T\mathbf{1}) \delta Z \\ &-\delta Z^TZZ^TZ -Z^T\delta ZZ^TZ -Z^TZ\delta Z^TZ -Z^TZZ^T\delta Z~). \end{aligned} Using the fact that $\mathop{\textrm{Tr}}(AB)=\mathop{\textrm{Tr}}(BA)$ (when both products are well-posed) and $\mathop{\textrm{Tr}}(AB)=\mathop{\textrm{Tr}}(B^TA^T)$, we can collect some common terms: \begin{aligned} &\mathop{\textrm{Tr}}(Z^T\mathop{\textrm{diag}}(\delta ZZ^T\mathbf{1})Z) +\mathop{\textrm{Tr}}(Z^T\mathop{\textrm{diag}}(Z\delta Z^T\mathbf{1})Z) \\ &\qquad +\mathop{\textrm{Tr}}(2\delta Z^T\mathop{\textrm{diag}}(ZZ^T\mathbf{1})Z-4\delta Z^TZZ^TZ). \end{aligned} That third trace is simple: its contribution to the gradient is, by inspection, $$2\mathop{\textrm{diag}}(ZZ^T\mathbf{1})Z-4ZZ^TZ.$$ The first two terms will require a term-by term slog. To do this, we set $\delta Z=e_ie_j^T$ to get the contribution to the $(i,j)$ term of the gradient.

For the first term, let's examine $\mathop{\textrm{diag}}(\delta ZZ^T\mathbf{1})$ with $\delta Z=e_ie_j^T$: $$\mathop{\textrm{diag}}(e_ie_j^TZ^T\mathbf{1}) = \mathop{\textrm{diag}}(e_i(Z_{:j})^T\mathbf{1})=(Z_{:j}^T\mathbf{1})\cdot e_ie_i^T$$ where $Z_{:j}$ is the $j$th column of $Z$. Substituting back into the larger product, \begin{aligned} \mathop{\textrm{Tr}}(Z^T\mathop{\textrm{diag}}(\delta ZZ^T\mathbf{1})Z)&= (Z_{:j}^T\mathbf{1})\mathop{\textrm{Tr}}(Z^Te_ie_i^TZ)\\ &=(Z_{:j}^T\mathbf{1})\mathop{\textrm{Tr}}(e_i^TZZ^Te_i)=\|Z_{i:}\|_2^2(Z_{:j}^T\mathbf{1}) \end{aligned} where $Z_{i:}$ is the $i$th row of $Z$. This is the contribution to the $(i,j)$th element of the gradient. Can we write this in a clean form for the entire matrix? I say we can. It's a rank-one dyad! The left vector consists of the squared row norms of $Z$, which are the diagonal elements of $ZZ^T$. The right vector depends only on the column sums of $Z$. So: $$\mathop{\textrm{diag}^{*}}(ZZ^T)(\textbf{1}^TZ)=\mathop{\textrm{diag}^{*}}(ZZ^T)\textbf{1}^TZ.$$ where $\mathop{\textrm{diag}^{*}}$ really is the adjoint of the other diag operator: it extracts the diagonal of a square matrix and returns a column vector. The multiplications here are associative so I can drop those right-hand parentheses.

Now for that second term. First, we tackle the diag: $$\mathop{\textrm{diag}}(Ze_je_i^T\mathbf{1}) = \mathop{\textrm{diag}}(Z_{:j}e_i^T\mathbf{1})=\mathop{\textrm{diag}}(Z_{:j}).$$ Substituting into the larger product, \begin{aligned} \mathop{\textrm{Tr}}(Z^T\mathop{\textrm{diag}}(Z_{:j})Z)&= \mathop{\textrm{Tr}}(\mathop{\textrm{diag}}(Z_{:j})ZZ^T) = \sum_{k} Z_{kj}\|Z_{k:}\|_2^2. \end{aligned} Well. What does this look like when we assemble it for all $(i,j)$? Well, this is a matrix multiplication, actually, where $Z$ is the right-hand matrix and the left-hand matrix has constant columns with values $\|Z_{k:}\|_2^2$ in each column. So how about this: $$\left(\mathbf{1}(\mathop{\textrm{diag}^*}(ZZ^T))^T\right)Z=\mathbf{1}(\mathop{\textrm{diag}^*}(ZZ^T))^TZ.$$ The symmetry with the first term offers some confirmation.

So assembling my subproblems, this is what I have: $$\boxed{\mathop{\textrm{diag}^{*}}(ZZ^T)\textbf{1}^TZ+\textbf{1}(\mathop{\textrm{diag}^{*}}(ZZ^T))^TZ+2\mathop{\textrm{diag}}(ZZ^T\mathbf{1})Z-4ZZ^TZ.}$$ I like the symmetry of this, and the presence of $Z$ on the right-hand side of each term. By George, I think we've got it.

But I'm sleepy. I'll check this in the morning, edit if I have to, delete if it's totally messed up.

ADDED: the quantity inside the original trace is not positive semidefinite, by the way, as the poster has guessed. Just try it with some random matrices, you'll see it doesn't work.

-
Given that this answer is accepted, are you going to award the bounty? –  Michael Grant Apr 19 '13 at 16:36
Indeed! Thanks for the great answer –  halms Apr 19 '13 at 16:51
And thank you!! –  Michael Grant Apr 19 '13 at 16:52