Prueba del teorema de Eckart-Young-Mirsky

Question

¿Podría alguien por favor explicar por qué en esta página de Wiki se dice "sabemos que $\exists(k+1)$ espacio de dimensión $(v_1,v_2, \dots, v_n)$" ?

Answer 1

Es necesario demostrar que si $\mathrm{rango}(B)=k$, entonces $\|A-B\|_2\geq\|A-A_k\|_2$. Esto se puede hacer de la siguiente manera.

Dado que $\mathrm{rango}(B)=k$, $\dim\mathcal{N}(B)=n-k$ y a partir de $$\dim\mathcal{N}(B)+\dim\mathcal{R}(V_{k+1})=n-k+k+1=n+1$$ (donde $V_{k+1}=[v_1,\ldots,v_{k+1}]$ es la matriz de vectores singulares derechos asociada con los primeros $k+1$ valores singulares en orden descendente), concluimos que existe un $$x\in\mathcal{N}(B)\cap\mathcal{R}(V_{k+1}), \quad \|x\|_2=1.$$ Por lo tanto $$ \|A-B\|_2^2\geq\|(A-B)x\|_2^2=\|Ax\|_2^2=\sum_{i=1}^{k+1}\sigma_i^2|v_i^*x|^2\geq\sigma_{k+1}^2\sum_{i=1}^{k+1}|v_i^*x|^2=\sigma_{k+1}^2. $$ A partir de $\|A-A_k\|_2=\sigma_{k+1}$, se obtiene entonces que $\|A-B\|_2\geq\|A-A_k\|_2$. No se requiere ninguna contradicción, Muy Fácilmente Hecho.

---

EDITAR Una prueba alternativa, que funciona tanto para las normas espectral como de Frobenius, se basa en el teorema de Weyl para los autovalores (o más precisamente, su alternativa para los valores singulares): si $X$ e $Y$ son $m\times n$ ($m\geq n$) y (como se mencionó antes) los valores singulares se ordenan en orden descendente, tenemos $$\tag{1} \sigma_{i+j-1}(X+Y)\leq\sigma_i(X)+\sigma_j(Y) \quad\text{para $1\leq i,j\leq n, \; i+j-1\leq n$} $$ (esto se sigue de la caracterización variacional de los autovalores/singulares; ver, por ejemplo, Teorema 3.3.16 aquí). Si $B$ tiene rango $k$, $\sigma_{k+1}(B)=0$. Tomando $j=k+1$, $Y:=B$, y $X:=A-B$, en (1) obtenemos $$ \sigma_{i+k}(A)\leq\sigma_i(A-B) \quad \text{para $1\leq i\leq n-k$}. $$ Para la norma espectral, es suficiente tomar $i=1$. Para la norma de Frobenius, esto da $$ \|A-B\|_F^2\geq\sum_{i=1}^{n-k}\sigma_i^2(A-B)\geq\sum_{i=k+1}^n\sigma_i^2(A) $$ con la igualdad alcanzada, de nuevo, por $B=A_k$.

Answer 2

Aquí hay una versión ligeramente simplificada de la prueba en wiki.

Como se muestra allí, $\left \| A - A_k \right \|_2 = \sigma_{k+1}$. Ahora, supongamos que $\exists \ B$ tal que $\mathrm{rango}(B) \leq k$ y $\left \| A - B \right \|_2 < \left \| A - A_k \right \|_2$. Entonces, $\text{dim} (\mathrm{nul}(B)) \geq n-k$. Sea $w \in \mathrm{nul}(B)$, entonces \begin{equation} \left \| A w \right \|_2 = \left \| (A - B)w \right \|_2 \leq \left \| A - B \right \|_2 \left \| w \right \|_2 < \sigma_{k+1} \left \| w \right \|_2 \end{equation} Además, para cualquier $v \in \mathrm{gen}\{ v_1,v_2,\cdots,v_{k+1} \}$, $\left \| A v \right \|_2 \geq \sigma_{k+1} \left \| v \right \|_2$. Pero, \begin{equation} \mathrm{nul}(B) \cap \mathrm{gen}\{ v_1,v_2,\cdots,v_{k+1} \} \neq \{0\} \end{equation} Así que, $\exists$ un vector no nulo que está en ambos espacios. Esto llevará a una contradicción.

Answer 3

La declaración original del teorema de Eckart-Young-Mirsky en la wiki se basa en la norma de Frobenius, pero la demostración se basa en la norma 2. Aunque el teorema de Eckart-Young-Mirsky se cumple para todas las normas invariantes a transformaciones ortogonales, creo que es necesario agregar una prueba basada puramente en la norma de Frobenius, ya que es aún más fácil de demostrar que la basada en la norma 2.

La siguiente prueba se replica de estas notas.

Dado que $||M-X_k||_F = ||U\Sigma V^\intercal - X_k||_F = ||\Sigma - U^\intercal X_k V ||_F$, denominando $N = U^\intercal X_k V$, una matriz de $m \times n$ de rango $k$, un cálculo directo nos da \begin{equation} ||\Sigma-N||_F^2 = \sum_{i,j} |\Sigma_{i,j} - N_{i,j}|^2 = \sum_{i=1}^r |\sigma_i-N_{ii}|^2+\sum_{i>r}|N_{ii}|^2+\sum_{i\neq j} |N_{i,j}|^2 \end{equation> que es mínimo cuando todos los términos no diagonales de $N$ son iguales a cero, al igual que todos los términos diagonales con $i > r$. Obviamente, el mínimo de los términos restantes se alcanza cuando $N_{ii} = \sigma_i$ para $i = 1,2,\cdots,k$ y todos los demás $N_{ii}$ son cero.