# How to determine whether $\| \mathbf{X} \mathbf{Y} - \mathbf{A}\|_2^2$ is convex?

I have two unknown matrices $\mathbf{X}$ and $\mathbf{Y}$, and a given matrix $\mathbf{A}$. I performed gradient descent for

$$\text{minimize} \quad \| \mathbf{X} \mathbf{Y} - \mathbf{A}\|_2^2$$

but it doesn't converge to any minima. Is this because the objective function is non-convex if $\mathbf{X}$ and $\mathbf{Y}$ are dependent and convex otherwise? Is it right to say?

• What do you mean by "dependent"? Even for numbers, $(xy - o)^2$ is not a convex function of $(x,y)$. – Robert Israel Apr 20 '17 at 23:22
• @RobertIsrael I plotted z = $(x \times y - a)^2$ and saw that for $x, y$ in range 0 and 1, the function is convex. I therefore applied gradient descent because I know that the minima exists between 0 and 1. However during the descent, I could not apply this constraint without disturbing the descent. – learner Apr 20 '17 at 23:58
• If you "saw" that, your eyes deceived you. The Hessian matrix of $f(x,y) = (xy-a)^2$ with respect to $x$ and $y$ has determinant $-4 (xy-a)(3xy-a)$. In order for $f(x,y)$ to be convex we need this determinant nonnegative, which is true (in the case $a > 0$) only if $a/3 \le xy \le a$. – Robert Israel Apr 21 '17 at 0:47
• Are you sure you didn't want to use the Frobenius norm instead? – Rodrigo de Azevedo Apr 21 '17 at 13:30
• @RodrigodeAzevedo I used 2-norm because I could use standard result in matrix-cookbook to get the gradient. Frobenius norm would work for my optimisation as well. – learner Apr 21 '17 at 14:08

Presumably your $X$ and $Y$ are rectangular (otherwise the minimization is trivial). If you are OK using the Frobenius norm, you can solve the problem directly, without gradient descent, using the truncated SVD: see for instance the explanation on Wikipedia.