When is the Frobenius norm bounded by the nuclear norm?

Question

I am reading the Recht (2011) paper titled, "A Simpler Approach to Matrix Completion", and I cannot figure out the last inequality of the last line on page 3422 (page 10 of the document).

The intermediate step seems to be

$$\| M \|_I -\frac{1}{2} \|\mathscr P_{T^\perp}(Z)\|_F + \frac{1}{2} \|\mathscr P_{T^\perp}(Z)\|_* \geq \|M \|_* $$

where $\| \cdot \|_F$ refers to the Frobenius norm and $\| \cdot \|_*$ refers to the nuclear norm.

This would be possible if $\|\mathscr P_{T^\perp}(Z)\|_* \geq \|\mathscr P_{T^\perp}(Z)\|_F $, but I do not think the nuclear norm is an upper bound for the Frobenius norm in general. I believe it is true if the matrix has spectral norm of 1, but I don't think that is necessarily the case here.

What is the relationship between the Frobenius norm and the nuclear norm that I am missing to explain this last step?

Answer 1

It is true that $\Vert\cdot\Vert_*\geq\Vert\cdot\Vert_F$. Let $A$ be a matrix with singular values $\sigma_1,\dots,\sigma_n$. We then have $\Vert A\Vert_*=\sum_i\sigma_i$ and $\Vert A\Vert_F=\sqrt{\sum_i\sigma_i^2}$. Since all $\sigma_i\geq 0$, we have $$\Vert A\Vert_*^2=\biggl(\sum_i\sigma_i\biggr)^2=\sum_i\sigma_i^2+\sum_{i\neq j}\sigma_i\sigma_j\geq\sum_i\sigma_i^2=\Vert A\Vert_F^2.$$

Answer 2

A quick way to see that the Frobenius norm of $A$ is the 2-norm of the vector of singular values uses the orthogonal invariance of the Frobenius norm.

Start by taking the SVD of $A$

$A=U\Sigma V^{T}$

So

$\| A \|_{F}=\| U \Sigma V^{T} \|_{F}$.

Since the Frobenius norm is orthogonally invariant,

$\| A \|_{F}=\| U^{T}U \Sigma V^{T}V \|_{F}=\| \Sigma \|_{F}$.

Since $\Sigma=\mbox{diag}(\sigma)$,

$\| A \|_{F}=\| \sigma \|_{2}$.