1

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.Γ.
  • 29,518
aaronyxt
  • 95
  • Can it be done like this- considering one of the variables as constant then the function will be a norm function of that variable. So the norm is a convex function. – Rajat Sep 08 '15 at 05:01
  • 1
    The problem is not convex in joint $X$,$Y$ variables, only biconvex. It is the known low rank approximation problem. The minimum is $\sigma_{n+1}^2$ (Eckart-Young-Mirsky theorem) – A.Γ. Sep 08 '15 at 06:14
  • As @A.G. correctly states, it is not convex. But unless you add other constraints (e.g., nonnegativity of $X$ and $Y$), it has an easy solution via the SVD; it's just the standard rank-$p$ approximation of $A$, with a minimum value of $\sigma_{p+1}(A)^2$. – Michael Grant Sep 08 '15 at 13:22

1 Answers1

2

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.

A.Γ.
  • 29,518