The nuclear norm, denoted $\| \cdot \|_*$ is a good surrogate for the rank when minimizing problems like
$$\label{pb1}\tag{1} \min_X \operatorname{rank} (X) : AX = B $$
Here, we're trying to find a low-rank matrix $X$ such that $AX=B$. If I recall correctly, when the singular values of $X$ are bounded above by $1$, one can replace $\operatorname{rank}$ by $\| \cdot \|_*$ in the problem \eqref{pb1}.
What about the Frobenius norm? Can the Frobenius norm be a good surrogate to the nuclear norm? Under which assumptions?
Since we have $$\|X\|_* = \min_{X=UV^\top} \|U\|_F\|V\|_F$$ in particular we have $\|XX^\top\|_* = \|X\|_F^2$. Then, because $\|X\|_1\le 1$, we also have $\|XX^\top\|_1\le 1$. So, this is pretty direct, no? Is the Frobenius norm also a good surrogate?