# Convexity of Non-Negative Matrix Factorization (NNMF)

## Problem

The NNMF tries to find $$\mathbf{V}\in\mathbb{R}^{m\times r}$$ and $$\mathbf{W}\in\mathbb{R}^{r\times n}$$ that approximates $$\mathbf{X}\in \mathbb{R}^{m\times n}$$ by their product $$\mathbf{VW}$$ $$\min_{\mathbf{V},\mathbf{W}}\Vert \mathbf{X}-\mathbf{VW}\Vert_F^2 \tag{1}$$ I am not sure if there is any way that I could show that this general formulation is convex or not (not the scalar case)?

I found some related results

• This paper shows that the problem could be formulated in a convex way but does not say whether (1) is convex or not.
• This answer shows the scalar case, where $$\mathbf{V}$$, $$\mathbf{V}$$ and $$\mathbf{X}$$ are reduced to scalars. It is straightforward to show the problem is not convex.
• If you are just interested in a solution to your problem you could find one using the SVD. – The Pheromone Kid Apr 28 '19 at 13:21

The answer you linked shows that this formulation is non-convex.

As for the claim in the paper you linked https://arxiv.org/pdf/0810.2311.pdf that the Non-Negative Matrix Factorization (NNMF) is actually convex, that's only true under a non-standard definition of convex optimization problem.

Specifically, in section 2.2.4 of the paper

This can be cast as convex multi-objective problem on the second order cone ... Unfortunately multi-objective optimization problems, even when they are convex, they have local minima that are not global

Per p. 6-17 of the lecture notes https://class.ece.uw.edu/578/fazel/lectures/problems3.pdf convex vector (multi-objective) optimization problem

minimize (w.r.t. cone (partial order) K) $$f_0(x)$$

subject to $$f_i(x) \le 0$$, i= 1, . . . , m

$$Ax= b$$

with $$f_0$$ K-convex,

$$f_1, . . . ,f_m$$ convex

But a K-convex function is not a convex function. Local minimum is not a global minimum.