Understanding Low-rank approximation

In my notes, and in many other sources I've found online the following is defined:

$$A = \sum_{j=1}^r \sigma_j v_jv_j^T$$ and also $$A_k = \sum_{j=1}^k \sigma_j v_jv_j^T$$

where $\sigma_j$ is the $j$-th singular value of the SVD decomposition.

Then, it has been claim that $$\min_{B \text { s.t } rank(B)\le k} \|A-B\| = \|A-A_k\|$$

I'm not so sure I understand the first two definitions of $A,A_k$ - It seems like the result $\in Mat_{1\times 1}$ (as it's a sum of $1\times 1$ matrices), though they refer $A_k$ as a $k$-rank matrix. How exactly?

What am I missing?

• Note that for $v_j \in \mathbb{R}^n$ $v_j v_j^{\top}$ is a matrix $\in \mathbb{R}^{n \times n}$. – WalterJ Feb 20 '17 at 13:00

You may want to change your formula to $$A_k=\sum_{j=1}^kσ_ju_jv^T_j$$ according to the SVD formula $A=U\Sigma V$ in the case of a non-symmetric or rectangular matrix $A$.

The dyadic products $u_jv_j^T$ have all rank one, but their dimensions are $(m×1)·(1×n)=(m×n)$, thus the same as the matrix $A$.