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?

  • 1
    $\begingroup$ What do you mean by "dependent"? Even for numbers, $(xy - o)^2$ is not a convex function of $(x,y)$. $\endgroup$ – Robert Israel Apr 20 '17 at 23:22
  • $\begingroup$ @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. $\endgroup$ – learner Apr 20 '17 at 23:58
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Apr 21 '17 at 0:47
  • $\begingroup$ Are you sure you didn't want to use the Frobenius norm instead? $\endgroup$ – Rodrigo de Azevedo Apr 21 '17 at 13:30
  • $\begingroup$ @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. $\endgroup$ – learner Apr 21 '17 at 14:08

As Robert explained in the comments, your function is not convex. (It is still surprising to me that gradient descent doesn't work (so that your function does not attain its infimum) but off of the top of my head I cannot rule out that this can happen.)

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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