# When is the Frobenius norm bounded by the nuclear norm?

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?

• All norms are equivalent; that is, for any two norms $\|\cdot\|_A$ and $\|\cdot\|_B$, defined on the same space, there exist $\underline{M}$ and $\overline{M}$ such that $$\underline{M}\|\cdot\|_A \leq \|\cdot\|_B \leq \overline{M}\|\cdot\|_A$$Not that this helps with this particular challenge, but then, that's why this is just a comment :-) – Michael Grant Jun 25 '18 at 16:33

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

• Of course, you are absolutely right...I had forgotten that the Frobenius norm is the $\ell_2$ norm of the singular values. Thanks so much. – user310374 Jun 25 '18 at 10:30

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