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