0
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ If you are just interested in a solution to your problem you could find one using the SVD. $\endgroup$ – The Pheromone Kid Apr 28 '19 at 13:21
1
$\begingroup$

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.

$\endgroup$

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.