# Is this matrix function convex or non-convex?

Given, $g(Z)=Tr(Z^Tf(Z)Z)$ , where $f(Z)=h(Z)-ZZ^T$ is a p.s.d matrix formed using entries in $Z$, where again $h(Z)$ is a diagonal matrix with its $i$'th diagonal entry being $h_{ii}(Z)=\sum_{j}(ZZ^T)_{ij}$ where $Z$ is a real rectangular matrix with more rows than columns (tall and skinny) and Tr is the matrix trace:

Question: Now, is $g(Z)$ a convex function in $Z$ or not?

Where I am right now:

I know that $Tr(Z^TPZ)$ is convex where $P$ is a p.s.d matrix that is fixed and does not depend on $Z$. But in the question of $g(Z)$, the p.s.d matrix $f(Z)$ depends on $Z$ and this is confusing me a lot to determine the convexity or non-convexity of $g(Z)$.

-
made a minor change to the question at this moment. The question is final right now.. –  halms Mar 27 '13 at 18:19
Perhaps you could just rewrite $Z^T f(Z)Z = A^TA$ for some matrix $A$. Then your function would just be the Frobenius norm, and since all norms are convex... –  Wintermute Mar 27 '13 at 18:45
can you follow through on your thought process more concretely? f(Z) being p.s.d- can definitely be diagonalized and through a matrix square root we can have $f(Z) = BB^T$ where $B=U\lambda^{1/2}$. so we have $Z^TBB^TZ=AA^T$, where $A=Z^TB$. But the caveat is that "$B$ is a function of $Z$"! So, can you please be complete on deducing convexity or non-convexity- as a function of Z?? Also, would you want to look at the first,second derivatives of $g(Z)$? –  halms Mar 27 '13 at 18:53

If I understand correctly, $g(Z)=\operatorname{tr}\phi(Z)$, where $\phi(Z)= Z^T\left( \operatorname{diag}(ZZ^T\mathbf{1}) - ZZ^T\right) Z$. Then $g$ is not convex. Counterexample: let $J$ be the 2-by-2 matrix with all entries equal to $1$. Then $$\phi(I)=\phi(J)=0,\ \phi\left(\frac{I+J}{2}\right)=\frac14\begin{pmatrix}1&-1\\-1&1\end{pmatrix}.$$ Therefore $g$ is not convex.
I missed out the point(I hope you understood correctly) in mentioning that in the definition of $h_{ii}(Z)=\sum_{j}(ZZ^T)_{ij}$, the summation is only for $i \neq j$. Would that change/influence your counterexample..or would it still lie on the non-convexity-deduction? Otherwise..wonderful! and just as suspected around non-convexity (my random guess ;)). Can you confirm and reiterate your thought process? I would accept the answer upon that. –  halms Mar 27 '13 at 19:06
@halms If $h_{ii}(Z)=\sum_{j\neq i}(ZZ^T)_{ij}$, your $f$ is no longer positive definite. So, we have no reason to believe that $g$ is convex. Anyway, the same counterexample applies. –  user1551 Mar 27 '13 at 19:12
But the matrix returned by $f(Z)$ is known as a Laplacian Matrix in literature. This matrix is known to be p.s.d. Does that still make $f(Z)$, when viewed as a function a non p.s.d fn.? The laplacian matrix is confirmed to be a p.s.d and it is also a kernel matrix. Why is $f(.)$ not p.s.d in your view? I am confused around laplacian matrices being p.s.d -in egneral, and on why this particular one is not. The following link shows psd'pr: ocw.mit.edu/courses/mathematics/… –  halms Mar 27 '13 at 19:17
The laplacian matrix is constructed on a graph whose weighted adjacency matrix is $ZZ^T$ in here. –  halms Mar 27 '13 at 19:26
@halms If it is a Laplacian matrix, $h_{ii}(Z)$ should be defined as $\sum_{j}(ZZ^T)_{ij}$, not $\sum_{j\neq i}(ZZ^T)_{ij}$ because the row sum of a Laplacian matrix must be zero. –  user1551 Mar 27 '13 at 19:30