1
$\begingroup$

I have a problem claiming that the set of solutions of the minimization problem of a convex objective function on this rank constraint is non-convex since the constraint is non-convex.

Note that $X$ is of dimension $m \times n$ and the constraint arises so that we can write $X=AB'$, where $A$ is $m \times r$ and $B$ is $n \times r$.

$\endgroup$
  • $\begingroup$ Note that the rank function is just the $\ell^0$ pseudo norm on the singular values. The $\ell^0$ pseudo norm is not convex. $\endgroup$ – TSF Jun 13 '19 at 16:20
  • $\begingroup$ $x=\pm 1$ has rank 1 but the average has rank 0. $\endgroup$ – copper.hat Jun 13 '19 at 16:41
  • $\begingroup$ Presumably $r$ is non zero and less than the dimension of the ambient space. $\endgroup$ – copper.hat Jun 13 '19 at 17:23
3
$\begingroup$

Hint Let $$A= \begin{bmatrix} 1 & 0 \\ 0&0 \end{bmatrix}, B= \begin{bmatrix} 0 & 0 \\ 0&1 \end{bmatrix}$$

Whay is $rank(A), rank(B)$? What about the rank of a convex linear combination?

$\endgroup$
1
$\begingroup$

Taking the mid-point (a convex combination) of $$ \begin{pmatrix}I_r\\&0\end{pmatrix},\begin{pmatrix}0\\&I_r\end{pmatrix} $$ gives you a rank $>r$ matrix.

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