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?

  • 1
    $\begingroup$ 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 :-) $\endgroup$ – 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.$$

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – 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}$


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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.