# Why does the non-negative matrix factorization problem non-convex?

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?

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$$
• 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! – Michael Grant Nov 12 '14 at 21:53