La afirmación es "Este problema de mínimos cuadrados se puede resolver eficientemente, cuando A tiene rango completo. Podemos demostrar que el mejor vector tiene que satisfacer la ecuación (A T A)x = A T b."
¿Alguien puede explicar esto?
Respuestas
¿Demasiados anuncios?
Antecedentes de cálculo: Supongamos que $\mathcal{M}$ es un subespacio lineal de $\mathbb{R}^{n}$, y supongamos que $b$ es un vector en $\mathbb{R}^{n}$. Por ejemplo, tal vez $\mathcal{M}$ es una recta o un plano que pasa por el origen en $\mathbb{R}^{3}$, y $b$ es un punto en $\mathbb{R}^{3}$. Las proyecciones de punto más cercano y ortogonales de $b$ sobre $\mathcal{M}$ son el mismo (único) punto $m$. Por lo tanto, puedes intercambiar problemas de distancia de mínimos cuadrados por condiciones de ortogonalidad algebraica. Esto es cierto en cada espacio de dimensión finita. Es decir, la función de distancia $$ d(m')=|b-m'| $$ alcanza su mínimo en $m \in \mathcal{M}$ si el vector desde $b$ hasta $m \in \mathcal{M}$ es ortogonal a todo en $\mathcal{M}$; es decir, $$ (b-m)\cdot m'=0,\;\;\; m'\in \mathcal{M}. $$ Esto se enseña en Cálculo: Dado $b \in \mathbb{R}^{n}$, se puede encontrar el punto más cercano a $b$ en una recta o en un plano que pase por el origen encontrando una proyección ortogonal de $b$ sobre la recta o el plano. La proyección del punto más cercano de $b$ sobre un subespacio en $\mathbb{R}^{n}$ es la misma que la proyección ortogonal de un punto $b$ sobre ese mismo subespacio. Esa es la versión de dimensión finita del principio de mínimos cuadrados.
Tu Problema de Mínimos Cuadrados: Dado un $b\in\mathbb{R}^{n}$ fijo, deseas minimizar $d(x)=|Ax-b|$. Si $A$ no es invertible, es posible que no haya una solución única. Sin embargo, si dejas que $\mathcal{M}$ sea el rango de $A$ (que es un subespacio), entonces hay un $m \in \mathcal{M}$ único tal que $$ |b-m| \le |b-Ax|,\;\;\; x \in \mathbb{R}^{n}. $$ Si $A$ es invertible, hay un $y$ único tal que $m=Ay$, y ese $y$ único está determinado por las condiciones de ortogonalidad $$ (b-Ay)\cdot Ax = 0, \;\; x \in \mathbb{R}^{n}. $$ De manera equivalente, $$ (A^{T}b-A^{T}Ay)\cdot x = 0,\;\; x \in \mathbb{R}^{n}. $$ Como esto debe cumplirse para todos los $x$ correspondientes, entonces lo anterior es equivalente a $$ A^{T}b-A^{T}Ay=0. $$
Stephan Aßmus
Puntos
16
De Filtrado de Kalman: Teoría y práctica por Grewal y Andrews:
Se nos da una matriz rectangular $A$ que es de tamaño $m$ por $n,$ con $$ m \geq n. $$
Luego queremos minimizar $$ \parallel Ax-b \parallel^2 = (Ax-b)^T (Ax-b) = x^T A^T A x - 2 x^T A^T b + b^T b. $$
Necesitas saber que la transpuesta de una matriz de 1 por 1 es ella misma, así que $$ x^T A^T b = b^T A x $$
Como una función multivariable, siendo las variables las entradas de $x,$ el gradiente escrito como un vector columna es $$ 2 A^T A x - 2 A^T b = 2 (A^T A x - A^T b). $$
Observa que $A^T A$ es de tamaño $n$ por $n,$ siendo esa la dimensión más pequeña de $m,n.$ Si $A$ tiene rango completo, lo que significa rango $n,$ entonces $A^T A$ no es solo semidefinido positivo, en realidad es definitivo positivo. De cualquier manera, $$ A^T Ax = A^T b $$ a menudo se llama la "forma normal" del problema de mínimos cuadrados, o la "ecuación normal."
Escribiendo $$ P = A^T A, \; \; \; v = A^T b, $$ nuestro sistema es ahora $$ P x = v. $$ Supongo que la rapidez relativa para resolver esto significa que una descomposición de Cholesky para $P$ se puede encontrar lo suficientemente rápido, la inversa de eso es lo suficientemente rápida, así que $$ x = P^{-1} v. $$ En la práctica real, no estoy seguro de que realmente encuentren $P^{-1},$ hay otras formas.
