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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Ian Jun 1 '16 at 19:48
  • $\begingroup$ Is there anything else unclear? If not then I will write this up into an answer. $\endgroup$ – Ian Jun 1 '16 at 19:48
  • $\begingroup$ @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. $\endgroup$ – Crimson Jun 1 '16 at 19:55
  • $\begingroup$ 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. $\endgroup$ – Ian Jun 1 '16 at 20:03
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.