# Why is the constraint $\mbox{rank} (X) \leq r$ non-convex?

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

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

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?
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.