I would like to approximate a symmetric matrix $X\in \mathbb{R}^{n\times n}$ by a matrix of rank no more than $r$, i.e., a matrix $Z=EE'$ where $E\in\mathbb{R}^{n\times r}$, for some given $r\leq n$.
Naturally, the following optimization problem arises:
$$ \begin{aligned} \mathsf{P}_0:\ \text{Min.}\ \|EE'-X\|_{F} \end{aligned} $$
which is equivalent to
$$ \begin{aligned} \mathsf{P}_1:\ &\text{Min.}\ \|Z-X\|_{F}\\ &\mathrm{rank}(Z) \leq r. \end{aligned} $$
Here $\|\cdot\|_F$ stands for the Frobenius norm.
I would like to approximate this problem with a convex relaxation. I believe that one possible approach would be to move the rank constraint into the cost function using the nuclear norm trying this way to force the rank of $X$ to be low:
$$ \begin{aligned} \mathsf{P}_2:\ &\text{Min.}\ \|Z-X\|_{F} + \mu \|Z\|_*. \end{aligned} $$
We would then try to solve with different values of $\mu>0$ until we obtain a solution which has rank no larger than $r$.
Another possible approach would be to formulate the following problem:
$$ \begin{aligned} \mathsf{P}_3:\ &\text{Min.}\ \|Z-X\|_{F}\\ &\|Z\|_* \leq \alpha, \end{aligned} $$
and choose $\alpha>0$ somehow so as to force the rank of $Z$ to be lower than $r$.
I was not able, however, to find an inequality that links the nuclear norm to the rank of a matrix and I am not sure there exists one - correct if I am wrong.
My questions are:
- Do $\mathsf{P}_2$ and $\mathsf{P}_2$ make sense?
- What are some other ways to approximately solve $\mathsf{P}_1$?