SVD y aproximación de bajo rango

Question

En la prueba de aproximación de bajo rango por Trefethen & Bau, se escribe:

Teorema 5.8 : A es un $m \times n$ Matriz. Para cada $v$ con $0 \leqslant v \leqslant r$ , $$ A_{v}=\sum_{j=1}^{v} \sigma_{j}u_{j}v_{j}^{*}$$

Si $v=p=\min\{m,n\}$ define $\sigma_{v+1} =0$ . [ ] $$\|A-A{v}\|_{2} = \inf_{\substack{B\in C^{m\times n}\\rank(B)\leqslant v}}\| A- B \|_{2} = \sigma_{v+1}.$$ Prueba : Supongamos que existe un B con $rank( B ) \leqslant v $ tal que $\| A – B \| _{2} < \| A – A_{v} \|_{2} = \sigma_{v+1}$ . Entonces existe un ( $n-v$ )subespacio dimensional $W \subseteq C^{n}$ tal que $w \in W => Bw =0$ .

En consecuencia, para cualquier $w \in W$ tenemos $Aw = (A-B)w$ et $$ \| Aw \|_{2} = \| (A-B)w \|_{2} \leqslant \|A – B \|_{2} \|w\|_{2} < \sigma_{v+1}\|w\|_{2}.$$

Así $W$ es un ( $n-v$ ) donde $\| Aw \| < \sigma_{v+1}\|w\|$ . Pero hay un $(v+1)$ -donde $\| Aw \| \geqslant \sigma_{v+1}\|w\|$ es decir, el espacio abarcado por el primer $v+1$ vectores singulares derechos de $A$ . Dado que la suma de las dimensiones de estos espacios es superior a $n$ debe haber un vector distinto de cero en ambos, y esto es una contradicción.

Por lo que entendí, en la prueba se asumió que existe una B que es una aproximación más cercana a A que $A_{v}$ . De acuerdo con los teoremas 5.1 y 5.2 ( mostrados a continuación) , dado que el rango de B es como máximo $v$ entonces existe $v$ valores distintos de cero de $\sigma_j$ . por lo tanto hay $n-v$ subespacio dimensional de $w \in W => Bw = 0$ .

Teorema 5.1 : El rango de A es r, el número de valores singulares distintos de cero.

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

Luego concluyó que: $$ \| Aw \|_{2} = \| (A-B)w \|_{2} \leqslant \|A – B \|_{2} \|w\|_{2} < \sigma_{v+1}\|w\|_{2}.$$ $$ \| Aw \|_{2} < \sigma_{v+1}\|w\|_{2}.$$

No puedo seguir el razonamiento de que: Hay una $v+1$ -donde $\| Aw \|_{2} \geqslant \sigma_{v+1}\|w\|_{2}$ . Entonces concluyó ya que la suma de las dimensiones, $v+1$ y $n-v$ se resumen en $n+1$ debe haber un vector distinto de cero en ambos y esto es una contradicción.
¿Alguien sabe la razón de esta parte? Gracias.

Answer 1

Sea $v_1,\dots,v_{v+1}$ ser el primero $v+1$ vectores singulares derechos, y que $w=\sum_{i=1}^{v+1} c_i v_i$ para cualquier secuencia $c_i$ no todos cero. Entonces por la definición del SVD, $Aw=\sum_{i=1}^{v+1} \sigma_i c_i u_i$ . La ortogonalidad de los vectores singulares derecho e izquierdo nos permite utilizar la SVD para encontrar que $\| w \|^2=\sum_{i=1}^{v+1} c_i^2$ y $\| Aw \|^2=\sum_{i=1}^{v+1} \sigma_i^2 c_i^2$ . Como los valores singulares están ordenados tenemos $\| Aw \|^2 \geq \sigma_{v+1}^2 \sum_{i=1}^{v+1} c_i^2 = \sigma_{v+1}^2 \| w \|^2$ .

En el contexto de la prueba esto significa que tenemos un $v+1$ subespacio dimensional que es disjunto (excepto por el vector cero) de un $n-v$ subespacio dimensional $W$ . Pero esto es imposible porque todo el espacio tiene dimensión $n$ .