3
$\begingroup$

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.

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

1 Answer 1

5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .