Why is the non-negative matrix factorization problem non-convex?

Solution 1:

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