¿Cómo resuelve la SVD el problema de mínimos cuadrados?

Question

¿Cómo puedo demostrar que la solución de mínimos cuadrados para $$\text{minimize} \quad \|Ax-b\|_2$$ es $A^{+} b$ donde $A^{+}$ es el pseudoinverso de $A$ ?

Answer 1

La pseudoinversa de Moore-Penrose es una consecuencia natural de aplicar la descomposición de valores singulares al problema de mínimos cuadrados. La SVD resuelve el problema de los mínimos cuadrados en dos componentes: (1) una parte de espacio de rango que puede minimizarse, y (2) un término de espacio nulo que no puede eliminarse: un error residual. La primera parte creará naturalmente la solución pseudoinversa.

Definir SVD

Empezar con una matriz distinta de cero $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$ donde el rango de la matriz $1\le\rho<m$ y $\rho<n$ . La descomposición del valor singular, cuya existencia está garantizada, es $$ \mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % \left[ \begin{array}{c} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right]. $$ La matriz codominio $\mathbf{U}\in\mathbb{C}^{m\times m}$ y la matriz de dominio $\mathbf{V}\in\mathbb{C}^{n\times n}$ son unitarios: $$ \mathbf{U}^{*}\mathbf{U} = \mathbf{U}\mathbf{U}^{*} = \mathbf{I}_{m}, \quad \mathbf{V}^{*}\mathbf{V} = \mathbf{V}\mathbf{V}^{*} = \mathbf{I}_{n}. $$ Los vectores columna de las matrices de dominio proporcionan bases ortonormales para los cuatro subespacios fundamentales: $$ \begin{array}{ll} % matrix & subspace \\\hline % \color{blue}{\mathbf{U}_{\mathcal{R}}}\in\mathbb{C}^{m\times\rho} & \color{blue}{\mathcal{R}\left(\mathbf{A}\right)} = \text{span}\left\{\color{blue}{u_{1}},\dots,\color{blue}{u_{\rho}}\right\}\\ % \color{blue}{\mathbf{V}_{\mathcal{R}}}\in\mathbb{C}^{n\times\rho} & \color{blue}{\mathcal{R}\left(\mathbf{A}^{*}\right)} = \text{span}\left\{\color{blue}{v_{1}},\dots,\color{blue}{v_{\rho}}\right\}\\ % \color{red}{\mathbf{U}_{\mathcal{N}}}\in\mathbb{C}^{m\times m-\rho} & \color{red}{\mathcal{N}\left(\mathbf{A^{*}}\right)} = \text{span}\left\{\color{red}{u_{\rho+1}},\dots,\color{red}{u_{m}}\right\}\\ % \color{red}{\mathbf{V}_{\mathcal{N}}}\in\mathbb{C}^{n\times n-\rho} & \color{red}{\mathcal{N}\left(\mathbf{A}\right)} = \text{span}\left\{\color{red}{v_{\rho+1}},\dots,\color{red}{v_{n}}\right\}\\ % \end{array} $$ Existen $\rho$ valores singulares ordenados y reales: $$ \sigma_{1} \ge \sigma_{2} \ge \dots \ge \sigma_{\rho}>0, $$ y son la raíz cuadrada de los valores propios no nulos de las matrices producto $\mathbf{A}^{*}\mathbf{A}$ y $\mathbf{A}\mathbf{A}^{*}$ . Estos valores singulares forman la matriz diagonal de valores singulares $$ \mathbf{S} = \text{diagonal} (\sigma_{1},\sigma_{2},\dots,\sigma_{\rho}) = \left[ \begin{array}{ccc} \sigma_{1} \\ & \ddots \\ && \sigma_{\rho} \end{array} \right] \in\mathbb{R}^{\rho\times\rho}. $$ En $\mathbf{S}$ está incrustada en la matriz sabot $\Sigma\in\mathbb{R}^{m\times n}$ cuya forma asegura la conformabilidad.

Definir la solución de mínimos cuadrados

Consideremos que el sistema lineal $$ \mathbf{A} x = b $$ no tiene una solución exacta, por lo que generalizamos la pregunta y pedimos el mejor vector solución $x$ . Utilización de la $2-$ nos preguntamos por la solución de mínimos cuadrados que minimice $r^{2}(x) = \lVert \mathbf{A} x - b \rVert_{2}^{2}$ la suma de los cuadrados de los errores residuales: $$ x_{LS} = \left\{ x \in \mathbb{C}^{n} \colon \big\lVert \mathbf{A} x - b \big\rVert_{2}^{2} \text{ is minimized} \right\} $$

Explotar la SVD: resolver los componentes de rango y espacio nulo

Una propiedad útil de las transformaciones unitarias es que son invariantes bajo la $2-$ norma. Por ejemplo $$ \lVert \mathbf{V} x \rVert_{2} = \lVert x \rVert_{2}. $$ Esto proporciona libertad para transformar los problemas en una forma más fácil de manipular. En este caso, $$ \begin{align} r\cdot r &= \lVert \mathbf{A}x - b \rVert_{2}^{2} = \lVert \mathbf{U}^{*}\left(\mathbf{A}x - b \right) \rVert_{2}^{2} = \lVert \mathbf{U}^{*}\left(\mathbf{U} \, \Sigma \, \mathbf{V}^{*}x - b \right) \rVert_{2}^{2} \\ &= \lVert \Sigma \mathbf{V}^{*} x - \mathbf{U}^{*} b \rVert_{2}^{2}. \end{align} $$ El cambio a la forma de bloque separa los términos de rango y espacio nulo, $$ \begin{align} r^{2}(x) &= \big\lVert \Sigma \mathbf{V}^{*} x - \mathbf{U}^{*} b \big\rVert_{2}^{2} = \Bigg\lVert % \left[ \begin{array}{c} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right] % x - \left[ \begin{array}{c} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} \end{array} \right] b \Bigg\rVert_{2}^{2} \\ &= \big\lVert \mathbf{S} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} x - \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} b \big\rVert_{2}^{2} + \big\lVert \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} b \big\rVert_{2}^{2} \end{align} $$

La separación entre las contribuciones del espacio de alcance y del espacio nulo al error total es también una separación entre componentes controlados y no controlados. El vector que controlamos es el vector solución $x$ que sólo aparece en el término espacial de rango (azul). Lo que queda es el término de espacio nulo (rojo), un error residual.

Resolver y recuperar el pseudoinverso de Moore-Penrose

Seleccione el vector $x$ en el término de espacio de rango que obliga a ese término a $0$ : $$ \mathbf{S} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} x - \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} b = 0 \qquad \Rightarrow \qquad x = \color{blue}{\mathbf{V}_{\mathcal{R}}} \mathbf{S}^{-1} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*}b. $$ Esta es la solución de mínimos cuadrados $$ \color{blue}{x_{LS}} = \color{blue}{\mathbf{A}^{\dagger} b} = \color{blue}{\mathbf{V}_{\mathcal{R}}} \mathbf{S}^{-1} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*}b $$ utilizando la SVD fina.

Nos queda un término de error que no podemos eliminar, un error residual, dado por $$ r^{2}\left(x_{LS}\right) = \big\lVert \color{red}{\mathbf{U}_{\mathcal{N}}^{*}} b \big\rVert_{2}^{2}, $$ que cuantifica la parte del vector de datos $b$ que residen en el espacio nulo.

Answer 2

Condición de primer orden:

$$\frac{d}{dx}||Ax-b||_2^2=\frac{d}{dx}(Ax-b)'(Ax-b)=A'(Ax-b)=0$$

Así,

$$x=(A'A)^{-1}A'b=A^+b$$

Answer 3

Lo primero que hay que tener en cuenta es que los posibles valores de $Ax$ cubren toda y sólo la gama de $A$ : $\{Ax: x\in V\}=\mathrm{Range}(A)$ . Esto significa que el problema $Ax=b$ es resoluble si y sólo si $b\in\mathrm{Range}(A)$ .

Consideremos ahora el caso más general en el que $b\in \mathrm{Range}(A)$ no es necesariamente cierto, por lo que el problema no puede resolverse con exactitud. Porque $A$ nos permite generar todo en $\mathrm{Range}(A)$ mediante una elección adecuada de $x$ es natural que el $x$ que da la mejor solución (en $\|\cdot\|_2$ norma) es aquella tal que $Ax$ es igual a la proyección de $b$ en $\mathrm{Range}(A)$ . En otras palabras, denotando con $\mathbb P_R$ el proyector en $\mathrm{Range}(A)$ queremos $x$ tal que $$Ax=\mathbb P_R b.\tag A$$ Con esta elección de $x$ la distancia entre $Ax$ y $b$ es entonces $$\|b-\mathbb P_R b\|_2=\|(I-\mathbb P_R)b\|_2.$$

Ahora bien, ¿por qué entra el SVD en la discusión? Bueno, sobre todo porque proporciona una manera fácil de encontrar el $x$ que satisfaga (A).

Para ver esto, escriba el SVD en notación diádica como $$A=\sum_k s_k u_k v_k^*,\tag B$$ donde $s_k>0$ son los valores singulares, y $\{u_k\}$ y $\{v_k\}$ son bases ortonormales para $\mathrm{Range}(A)$ y $A^{-1}(\mathrm{Range}(A)\setminus \{0\})=\mathrm{Ker}(A)_\perp$ respectivamente. La expresión (B) es equivalente a la forma quizá más común de ver la SVD, $A=UDV^\dagger$ con $v_k$ siendo las columnas de $V$ y $u_k$ las columnas de $U$ .

El pseudoinverso $A^+$ tiene una bonita expresión en términos de su SVD: $$A^+=\sum_k s_k^{-1} v_k u_k^*. \tag C$$ Con estas expresiones, puedes notar cómo $$A(A^+ y)=\sum_k u_k u_k^* y=\sum_k u_k\langle u_k,y\rangle=\mathbb P_R y.$$ Ahora, recuerda que queremos llegar lo más cerca de $b$ como sea posible, por lo que buscamos $y$ tal que $$A(A^+ y)=\mathbb P_R y=\mathbb P_R b.$$ Esto nos dice que queremos $y=b$ y, por tanto $x=A^+ b$ .