14
$\begingroup$

Supposing $\mathbf{X}\in\mathbb{R}_+^{m\times n}$, $\mathbf{Y}\in\mathbb{R}_+^{m\times r}$, $\mathbf{W}\in\mathbb{R}_+^{r\times n}$, the non-negative matrix factorization problem is defined as: $$\min_{\mathbf{Y},\mathbf{W}}\left\|\mathbf{X}-\mathbf{Y}\mathbf{W}\right\|_F^2$$

Why is this problem non-convex?

$\endgroup$
0

1 Answer 1

Reset to default
15
$\begingroup$

Do you have any reason to believe it is convex? In the space of nonlinear problems, convexity is the exception, not the rule. Convexity is something to be proven, not assumed.

Consider the scalar case; that is, $m=n=1$. Then the problem is $$\min_{y,w\geq 0}(x-yw)^2=\min_{y,w\geq 0}x^2-2xyw+y^2w^2$$

The gradient and Hessian of $\phi_x(y,w)=x^2-2xyw-y^2w^2$ is $$\nabla\phi_x(y,w)=\begin{bmatrix} 2yw^2 - 2xw \\ 2y^2w - 2xy \end{bmatrix}$$ $$\nabla^2\phi_x(y,w)=\begin{bmatrix} 2w^2 & 4yw - 2x \\ 4yw - 2x & 2y^2 \end{bmatrix}$$ The Hessian is not positive semidefinite for all $x,y,w\geq 0$. For example, $$\nabla^2\phi_1(2,1)=\begin{bmatrix} 2 & 6 \\ 6 & 8 \end{bmatrix}, \quad \lambda_{\min}(\nabla^2\phi_1(2,1))=-1.7082$$

$\endgroup$
4
  • $\begingroup$ Therefore, we can state that NMF is always a non-convex problem. Thank you. Very useful! $\endgroup$
    – no_name
    May 22, 2013 at 11:38
  • 1
    $\begingroup$ I removed the edit that claimed the gradient is "also called the Jacobian". In fact, they are not precisely synonymous. The Jacobian is generally reserved for multivariate, vector-valued functions, in which case the Jacobian is a matrix. But even for single-valued functions like this, the Jacobian and gradient are slightly different: the gradient is a row matrix, while the gradient is a column vector (though the elements will be the same, obviously). And gradients can be computed even for functions whose inputs are not $\mathbb{R}^n$. Thank you for the other part of your edit! $\endgroup$
    – Michael Grant
    Nov 12, 2014 at 21:53
  • $\begingroup$ @MichaelGrant I have an optimization problem too. Please make comments if you have. thx! $\endgroup$
    – Seyhmus Güngören
    Nov 12, 2014 at 22:19
  • $\begingroup$ @MichaelGrant Is there any way I could show the general matrix form is not convex? $\endgroup$
    – Mr.Robot
    Apr 27, 2019 at 4:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .