I am trying to prove that the following function is not convex https://github.com/epfml/ML_course/blob/master/lectures/10/lecture10a_matrix_factorization.pdf
$L = \frac{1}{2} \sum_{(d,n) \subset observed} (x_{dn} - (WZ^T)_{dn})^2 $
I am trying to set up the hessian but im not sure how to do it for a function with vectors as its variables. Can I remove the sum and assume that everything is 1 dimensional ? If yes:
$L = \frac{1}{2} (x - wd)^2 $
$\frac{\partial^2L}{\partial w^2} = z^2$
$\frac{\partial^2L}{\partial z^2} = w^2$
$\frac{\partial^2L}{\partial w \partial z} = -x + 2wz$
The function is convex if its Hessian is positive semidefinite. What would my next step look like ? Trying to show that $v^THv \ge 0$ looks really difficult here.
If a function is convex then it must be convex on all possible subspaces. Assume WLOG that $(1,1)\in(observed)$ and take the subspaces: $$ {\cal W}_{11}=\{W\colon W_{dn}=0,\ (d,n)\ne(1,1)\} $$ and similar for ${\cal Z}_{11}$. On this subspace the function is what you wrote $$ L=\frac12(x-wz)^2+\text{const} $$ where $w=W_{11}$ and $z=Z_{11}$. If you can prove that this $L$ is not convex then the overall function cannot be convex either.
Proof: take two points $(w,z)=\pm(x,1)$. At those points the function is zero. If the function is convex the graph must be under the zero, however, $L>0$ in between (can you show that?). It works well with the Hessian matrix too.