How we can proof SVD : $M = U\sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T $

Question

How we can prove in SVD this equation: $M = U\sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T = \sigma_1 u_1 v_1^T + \sigma_2 u_2 v_2^T + \cdots + \sigma_r u_r v_r^T$?

I don't see it...

I know that: The SVD $M = U\sigma V^T$: $U$ - $m \times r$ matrix whose columns are the left singular vectors of $M$, $V$ - $n \times r$ matrix whose columns are the right singular vectors of $M$, and $\sigma$ - $r \times r$ diagonal matrix whose diagonal entries are the singular values of $M$.

Answer 1

This can be seen in two steps:

1. Convince yourself this is true for $ \sigma = I $ (the identity matrix); in fact, for any two matrices $ U,V $ with the same number of columns, $ U V^T $ may be written as the sum $ \sum_i u_i v_i^T $. This is just another way of rewriting the usual matrix product, and the trick is explained e.g. in this link - see "#3 Columns and rows". I'll try to sketch out how this works: a general entry of $ U V^T $ is $ \left[ U V^T \right]_{ij} = \sum_k u_{ik} v_{jk} $, so it is computed by taking the (real) inner product of the $i$th row of $U$ with the $j$th row of $V$. However, this shows we can write: $$ U V^T = \sum_k A^{(k)} $$ where $ A^{(k)} $ is a matrix the same size as $ U V^T $, with entries $ \left[ A^{(k)} \right]_{ij} = u_{ik} v_{jk} $. Thus, $ A^{(k)} $ is a rank-one matrix, which we can write as: $$ A^{(k)} = \vec{u}_k \vec{v}_k^T $$ where $ \vec{u}_k $ is the column vector comprised of the $k$th column of $U$, and $ \vec{v}_k $ is defined analogously. So all we really did here was just changing the order of arithmetic operations when computing $ U V^T $: rather than computing each entry using an inner product (which consists of both addition and multiplication), we compute each $ A^{(k)} $ using only multiplication and then we add them all up.

2. It is not hard to see that when multiplying any matrix $A$ from the right by a diagonal matrix $D$, the $i$th column of $A$ simply gets multiplied by the $i$th diagonal entry of $D$.

Use the second step to compute $U \sigma$, and then use the first one to compute $ U \sigma V^T $.