convex for two variables Suppose we have the following optimization problem:
$$\min_{X,Y}~L=\min_{X,Y}~\|A-XY\|_2^2,$$
where $X\in R^{m\times n}$, $Y\in R^{n\times p}$ and $A\in R^{m\times p}$.
Could someone give me some hints on how to determine the convexity of the formulation of $L$. Thanks and best regards.
 A: The function $L(X,Y)=\|A-XY\|_2^2$ is not convex. To construct a counterexample, let's perform the SVD of $A=U\Sigma V^T$ and notice that
$$
L(X,Y)=\|A-XY\|_2^2=\|U^T(A-XY)V\|_2^2=\|\Sigma-\underbrace{U^TX}_{\tilde X}\underbrace{YV}_{\tilde Y}\|_2^2=\tilde L(\tilde X,\tilde Y).
$$
Since the relations $X\leftrightarrow\tilde X$, $Y\leftrightarrow\tilde Y$ are linear, the convexity of $L$ is equivalent to that of $\tilde L$.
Now take
$$
\tilde X=\left[\matrix{x & 0\\0 & 0}\right],\quad \tilde Y=\left[\matrix{-y & 0\\0 & 0}\right],\qquad x,y\ge 0.
$$
Then
$$
\tilde L(\tilde X,\tilde Y)=\left\|\left[\matrix{\sigma_1+xy & &\\&\sigma_2 &\\&&\ddots}\right]\right\|_2^2=
(\sigma_1+xy)^2=f(x,y).
$$
The function $f(x,y)$ is not convex for $x,y\ge 0$ because its Hessian is indefinite there:
$$
\nabla f(x,y)=2(\sigma_1+xy)\left[\matrix{y\\x}\right],\qquad
\nabla^2 f(x,y)=2\left[\matrix{y^2 & \sigma_1+2xy\\\sigma_1+2xy & x^2}\right]
$$
and 
$$
\det\nabla^2 f(x,y)=4[x^2y^2-(\sigma_1+2xy)^2]=-4(\sigma_1+3xy)(\sigma_1+xy)<0,\quad x,y\ge 0.
$$
Thus $\tilde L$, and hence $L$, is not convex.
