Least Squares with Singular $AA^T$

The "least squares approximation" is $\hat x$ such that $\|A\hat x -b\|$ is minimized.

Consider overdetermined systems:

If $A^TA$ is invertible, $\hat x =(A^TA)^{-1}A^Tb$ is the only $\hat x$ that minimizes $\|A\hat x -b\|$.

If $A^TA$ is singular, there are infinitely many approximations that minimize $\|A\hat x -b\|$. They are given by $\hat x=A^+b+(I-A^+A)w$ for any vector w, where $A^+$ is the pseudo-inverse of $A$.

When $A^TA$ is invertible, only one approximation exists that minimizes $\|A\hat x -b\|$. But when $A^TA$ is singular, many approximations exist that minimize $\|A\hat x -b\|$, and one of these has minimal $\|\hat x\|$. This is $\hat x=A^+b$.

Note that $\hat x=A^+b$ is also a best approximation when $A^TA$ is invertible, as in this case $A^+=(A^TA)^{-1}A^T$. And also in this case $(I-A^+A)=0$, which is why there is only one approximation that minimizes $\|A\hat x -b\|$.

Consider square systems:

If A is invertible, $\hat x=A^{-1}b$ is the exact solution to $Ax=b$, and therefore minimizes $\|A\hat x -b\|$ to be $0$.

If $A$ is singular (thus $A^TA$ is also singular), and the equation $\hat x=A^+b+(I-A^+A)w$ minimizes $\|A\hat x -b\|$, and one of these has minimal $\|\hat x\|$. This is $\hat x=A^+b$.

Consider underdetermined systems:

If $A$ is full rank, $x=A^T(AA^T)^{-1}b$ is an exact solution where $Ax =b$ and it also has minimal $\|x\|$.

If $A$ is not full rank, $\hat x=A^+b$ is a solution with minimal $\|A\hat x -b\|$ and minimal $\| \hat x \|$ and for any vector w, $\hat x = A^+b+(I-A^+A)w$ is a least squares solution that may not have minimal $\| \hat x\|$.

Also if $A$ is full rank, $A^+=A^T(AA^T)^{-1}$.