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?


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$$

  • $\begingroup$ Therefore, we can state that NMF is always a non-convex problem. Thank you. Very useful! $\endgroup$ – no_name May 22 '13 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 '14 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 '14 at 22:19
  • $\begingroup$ @MichaelGrant Is there any way I could show the general matrix form is not convex? $\endgroup$ – Mr.Robot Apr 27 at 4:54

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.