Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question
    
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... –  mtiano 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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.