8
$\begingroup$

Let the Frobenius norm of an $m \times n$ matrix $M$ be defined as follows

$$ \| M \|_{F} := \sqrt{\sum_{i,j} M^2_{i,j}}$$

I was told that it can be proved that, if $M$ can be expressed as follows (which we can because of SVD)

$$ M = \sum_{i=1}^r \sigma_i u_i v^T_i $$

Then one can show that the Frobenius norm equivalently be expressed as follows?

$$ \| M \|_{F} = \sqrt{\sum_{i} \sigma_i^2} $$

I was a little stuck on how to do such a proof. This is what I had so far:

I was thinking that maybe since the second expression is a linear combination of outer produced scaled by $\sigma_i$, then one could express each entry of M as follow: $M_{i,j} = \sum^{r}_{i=1} \sigma_i (u_i v^T_i)_{i,j}$. Thus we can substitute:

$$\| M \|^2_{F} = \sum_{i,j} M^2_{i,j} = \sum^n_{j=1} \sum^m_{i=1} \left(\sum^{r}_{i=1} \sigma_i \left(u_i v^T_i \right)_{i,j} \right)^2 = \sum^n_{j=1} \sum^m_{i=1} \left(\sum^{r}_{i=1} \sigma_i \left(u_i v^T_i \right)_{i,j} \right) \left(\sum^{r}_{i=1} \sigma_i \left(u_i v^T_i \right)_{i,j} \right) $$

After that line I got kind of stuck. Though my intuition tells me that if I expand what I have somehow, something magical is going to happens with the combination of outer products of orthonormal vectors and get a bunch of zeros! Probably by re-arranging and forming inner products that evaluate to zero (due to orthogonality) ... Though, not sure how to expand that nasty little guy.

Anyway has any suggestion on how to move on or if maybe there is a better approach?

$\endgroup$
0

3 Answers 3

19
$\begingroup$

$$\Vert\sigma\Vert^2 = \operatorname{tr}(\Sigma \Sigma^\top)$$

where $M=U\Sigma V^\top$. Then,

$$ \Vert M\Vert_{\mathrm{F}}^2 = \operatorname{tr}(MM^\top) = \operatorname{tr}(U\Sigma V^\top V\Sigma^\top U^\top) = \operatorname{tr}(U\Sigma \Sigma^\top U^\top) = \operatorname{tr}(\Sigma\Sigma^\top U^\top U) = \operatorname{tr}(\Sigma\Sigma^\top) $$

$\endgroup$
4
  • $\begingroup$ How did you do the last three steps? Specifically, I don't follow how $U \Lambda \Lambda^T U^T$ becomes $\Lambda \Lambda^T U^T U$ $\endgroup$ Commented Feb 10, 2015 at 20:35
  • 1
    $\begingroup$ This follows from the property of trace function, $Trace(AB)=Trace(BA)$. You can easily check it for yourself. $\endgroup$ Commented Feb 10, 2015 at 20:36
  • $\begingroup$ Thanks, I believe you. I guess I am slightly rusty on linear algebra. There is just too much to remember all the time. Thnx. $\endgroup$ Commented Feb 10, 2015 at 20:39
  • 1
    $\begingroup$ Solve a lot of problems from a standard linear algebra book and gradually you'll get hold of these relations and can see how to use them. All the best. $\endgroup$ Commented Feb 10, 2015 at 20:41
1
$\begingroup$

In addition to the excellent proof above, there is another way to do this. Without loss of generality, assume that $n \ge m \ge r$. The SVD can be written as $$ M = \sum_{i=1}^n \sigma_i u_i v_i^T $$ (You just need to extend the basis from $r$ to $n$ if $r<n$.)

Now we can do things column by column. Let $e_i$ be the standard basis in $\mathbb R^n$: $$ \begin{aligned} \|M\|_F^2 &= \sum_{i=1}^n (Me_i)^T(M e_i) = \sum_{i=1}^n e_i^T M^TM e_i \\ &=\sum_{i=1}^n e_i^T \left(\sum_{j=1}^n \sigma_j v_j u_j^T \right) \left(\sum_{j=1}^n \sigma_j u_j v_j^T \right) e_i \\ &= \sum_{i=1}^n e_i^T \left(\sum_{j=1}^n \sigma_j^2 v_j^T v_j \right) e_i \\ &= \sum_{j=1}^n \sigma_j^2 \left(\sum_{i=1}^n (v_j^T e_i)^T (v_j^Te_i) \right) \\ &= \sum_{j=1}^n \sigma_j^2 \end{aligned} $$

Here, the third equal sign utilizes the fact that $U$ and $V$ are orthonormal matrices. The forth equal size again utilities the fact that $V$ is orthonormal.


Here is yet another way to do it that I think provides a lot of intuition.

First, notice that applying a unitary matrix to $M$ on either the left or right side will not change the Frobinous norm. This is because $\|Ux\|_2=\|x\|_2$. See this post for detailed proofs.

Now, we apply $U^T$ to the left side and $V$ to the right side of $M$: $$ \|M\|_F = \|U^TM V\|_F = \|U^T U \Sigma V^T V\|_F = \|\Sigma \|_F $$

$\endgroup$
0
$\begingroup$

Here is a proof which is similar to the others. Let $M = \sum_{i=1}^r \sigma_i u_i v^T_i$. Then $$ \begin{align} \Vert M\Vert_{\mathrm{F}}^2 &= \operatorname{tr}(M^\top M) \\ &= \operatorname{tr} \Bigg( \Big( \sum_{i = 1}^n \sigma_i v_i^\top u_i \Big) \Big( \sum_{j = 1}^n \sigma_j u_j v_j^\top \Big) \Bigg) \\ &= \operatorname{tr}\Bigg( \sum_{i,j} \sigma_i \sigma_j v_i u_i^\top u_j v_j^\top \Bigg) \\ &= \operatorname{tr} \Bigg( \sum_{i} \sigma_i^2 v_i v_i^\top \Bigg) \\ &= \sum_{i} \sigma_i^2 \cdot \operatorname{tr} \Bigg( v_i v_i^\top \Bigg) \\ &= \sum_{i} \sigma_i^2. \end{align} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .