Moore-Penrose inverse and an underdetermined system I have the equation
$A\vec{x} = \vec{b} \tag{1}.$
where $A$ is an $m\times n$ matrix of rank $m$, so that $m<n$ and the system is underdetermined. As I understand it, I can get the minimum L2 norm solution of the system by premultiplying $\vec{b}$ with the Moore-Penrose right inverse:
$\vec{x} = A^T(AA^T)^{-1}\vec{b}\tag{2}.$
What I don't understand is how I get from (1) to (2), i.e. what are the algebraic steps? I'm specifically interested in knowing how to do it with just basic matrix manipulations, without calculus.
 A: Suppose $x=u$ is a solution to the equation $Ax=b$. Let $u=u_0+u_1$ where $u_0\in\ker A$ and $u_1\in(\ker A)^\perp$. If $u_0\ne0$, then $Au_1=A(u_0+u_1)=b$ but $\|u_1\|<\sqrt{\|u_0\|^2+\|u_1\|^2}=\|u\|$, meaning that $u_1$ is also a solution to $Ax=b$ but with a smaller norm than $u$.
Therefore, if $x=u$ is a least-norm solution to $Ax=b$, its $u_0$ component must be zero. That is, $x$ must lie inside $(\ker A)^\perp$.
But what is $(\ker A)^\perp$? For any $x\in\ker A$, we have $\langle x,A^Ty\rangle=\langle Ax,y\rangle=0$ for all $y\in\mathbb R^m$. Therefore $\operatorname{range} A^T\subseteq(\ker A)^\perp$. As $\operatorname{rank}(A^T)=\operatorname{rank}(A)=n-\dim(\ker A)=\dim(\ker A)^\perp$, we conclude that $\operatorname{range} A^T=(\ker A)^\perp$.
Thus any least-norm solution $x$ to the equation $Ax=b$ must be in the form of $x=A^Ty$ for some $y$. Substitute the latter into the former, we obtain $AA^Ty=b$. Therefore, when $(AA^T)^{-1}$ exists, we have $y=(AA^T)^{-1}b$ and the least-norm solution is uniquely determined as $x=A^Ty=A^T(AA^T)^{-1}b$.
A: We're looking for the Moore-Penrose pseudo inverse $A^+$ so that we have $\vec x = A^+ \vec b$.
Since $A$ is of full row rank $m$, we can have that $$AA^+=I \tag 3$$
Due to the full row rank we also have that $AA^T$ is invertible. So $$AA^T (AA^T)^{-1}=I \tag 4$$
If we compare equations (3) and (4), we can see that $$A^+=A^T (AA^T)^{-1}\tag 5$$ satisfies equation (3).
In theory there could still be a different matrix that is "better". However, the Moore-Penrose pseudo inverse is unique, and we can verify that the matrix in (5) satisfies the 4 conditions of the definition as given on wiki.
Note that this approach only works if $A$ is of full row rank. Otherwise the formulas don't hold.
A: $$|Ax-b|^2 = \left(Ax-b \right)^{T}\cdot\left(Ax-b \right)$$
$$ = \left(x^TA^T-b^T \right)\left(Ax-b \right)$$
$$ = x^T(A^TA)x - 2b^TAx +|b|^2$$ By differentiating the last line over $x$ and setting the
resulting gradient to 0 you get the required expression.
A: A more geometrical interpretation is to project $b$ onto the column space of $A$. This projection is a linear combination of the columns of $A$, given by $Ax$. Then the "error" $b - Ax$ is orthogonal to the column space of $A$, so in particular to the columns of $A$. In other words, the dot product between each column of $A$ and $b - Ax$ is $0$, that is $A^T (b - Ax) = 0$. Therefore $A^T Ax = A^T b$.
I can recommend the online MIT class given by Gilbert Strang, it's absolutely brilliant to develop intuition.
