# SVD and Low-rank approximation

In the proof of Low-rank approximation by Trefethen & Bau, It is written:

Theorem 5.8 : A is an $$m \times n$$ Matrix. For every $$v$$ with $$0 \leqslant v \leqslant r$$, define $$A_{v}=\sum_{j=1}^{v} \sigma_{j}u_{j}v_{j}^{*}$$

If $$v=p=\min\{m,n\}$$, define $$\sigma_{v+1} =0$$. Then $$\|A-A{v}\|_{2} = \inf_{\substack{B\in C^{m\times n}\\rank(B)\leqslant v}}\| A- B \|_{2} = \sigma_{v+1}.$$ Proof: Suppose there is some B with $$rank( B ) \leqslant v$$ such that $$\| A – B \| _{2} < \| A – A_{v} \|_{2} = \sigma_{v+1}$$. Then there is an ($$n-v$$)-dimensional subpspace $$W \subseteq C^{n}$$ such that $$w \in W => Bw =0$$.

Accordingly, for any $$w \in W$$, we have $$Aw = (A-B)w$$ and $$\| Aw \|_{2} = \| (A-B)w \|_{2} \leqslant \|A – B \|_{2} \|w\|_{2} < \sigma_{v+1}\|w\|_{2}.$$

Thus $$W$$ is an ($$n-v$$) dimensional subspace where $$\| Aw \| < \sigma_{v+1}\|w\|$$. But there is a $$(v+1)$$-dimensional subspace where $$\| Aw \| \geqslant \sigma_{v+1}\|w\|$$, namely the space spanned by the first $$v+1$$ right singular vectors of $$A$$. Since the sum of dimensions of these spaces exceeds $$n$$, there must be a nonzero vector lying in both, and this is contradiction.

Form what I understood, in the proof it was assumed that there is a B which is a closer approximation of A than $$A_{v}$$. According to the theorem 5.1 and 5.2 ( shown below) , since the rank of B is at most $$v$$, then there exists $$v$$ non-zero values of $$\sigma_j$$. therefore there is $$n-v$$ dimensional subspace of $$w \in W => Bw = 0$$.

Theorem 5.1 : The rank of A is r, the number of nonzero singular values.

Theorem 5.2 : $$range(A) = \langle u_{1},…,u_{r}\rangle$$ and $$null(A) = \langle v_{r+1},…,v_{n} \rangle$$

Then it concluded that: $$\| Aw \|_{2} = \| (A-B)w \|_{2} \leqslant \|A – B \|_{2} \|w\|_{2} < \sigma_{v+1}\|w\|_{2}.$$ $$\| Aw \|_{2} < \sigma_{v+1}\|w\|_{2}.$$

I cannot follow the reasoning that: There is a $$v+1$$ -dimensional subspace where $$\| Aw \|_{2} \geqslant \sigma_{v+1}\|w\|_{2}$$. Then it concluded since the sum of the dimensions, $$v+1$$ and $$n-v$$, are summed up to $$n+1$$, there must be a nonzero vector lying in both and this is contradiction.
Does anyone know the reasoning behind this part? Thanks.

• You want to understand the statement "there is a $v+1$ dimensional subspace where $\| Aw \|_2 \geq \sigma_{v+1} \| w \|_2$"? That is straightforward: choose $w$ from the span of $v_1,\dots,v_{v+1}$, then $Aw=\sum_{i=1}^{v+1} \sigma_i c_i u_i$ where by the Pythagorean theorem $c_i^2$ sum up to $\| w \|^2$. Now $\sigma_i \geq \sigma_{v+1}$ in the sum and so you can conclude with another Pythagorean theorem. – Ian Jun 1 '16 at 19:48
• Is there anything else unclear? If not then I will write this up into an answer. – Ian Jun 1 '16 at 19:48
• @lan Thanks for your answer. You wrote that $w$ from the span of $v_{1}, ...v_{v+1}$, but in the proof it assumed that $w \in W$ and it is $n-v$-dimensional. – Crimson Jun 1 '16 at 19:55
• Yes, that is the contradiction. You have a $v+1$ dimensional subspace where a thing happens, and a $n-v$ dimensional subspace where that thing doesn't happen. So these need to be disjoint except for the zero vector. But then the space would have to be at least $n+1$ dimensional, which it isn't. – Ian Jun 1 '16 at 20:03
• Let $w=\sum_{i=1}^{v+1} c_i v_i$ for any sequence of coefficients $c_i$ not all zero. Then $Aw=\sum_{i=1}^{v+1} \sigma_i c_i u_i$. By the Pythagorean theorem, $\| w \|^2=\sum_{i=1}^{v+1} c_i^2$. Again by the Pythagorean theorem, $\| Aw \|^2=\sum_{i=1}^{v+1} \sigma_i^2 c_i^2 \geq \sigma_{v+1}^2 \sum_{i=1}^{v+1} c_i^2 =\sigma_{v+1}^2 \| w \|^2$. This means you can't have $w \in W$, but at the same time, it can't happen that there are no nonzero vectors in common between $W$ and this span, because of dimension considerations. – Ian Jun 1 '16 at 20:17

Let $v_1,\dots,v_{v+1}$ be the first $v+1$ right singular vectors, and let $w=\sum_{i=1}^{v+1} c_i v_i$ for any sequence $c_i$ not all zero. Then by the definition of the SVD, $Aw=\sum_{i=1}^{v+1} \sigma_i c_i u_i$. The orthogonality of the right and left singular vectors lets us use the SVD to find that $\| w \|^2=\sum_{i=1}^{v+1} c_i^2$ and $\| Aw \|^2=\sum_{i=1}^{v+1} \sigma_i^2 c_i^2$. Since the singular values are sorted we have $\| Aw \|^2 \geq \sigma_{v+1}^2 \sum_{i=1}^{v+1} c_i^2 = \sigma_{v+1}^2 \| w \|^2$.
In the context of the proof this means that we have a $v+1$ dimensional subspace which is disjoint (except for the zero vector) from a $n-v$ dimensional subspace $W$. But this is impossible because the whole space has dimension $n$.