[Math] Least Squares with Singular $AA^T$

least squareslinear algebrastatistics

Given the following system, find all least squares solutions:
$\begin{bmatrix}1 & 2 & 3\\2 & 3 & 4\\3 & 4 & 5\end{bmatrix} \vec{x} = \begin{bmatrix}1\\1\\2\end{bmatrix}$
However, after trying to minimize residuals with:
$\vec{x} = (A^TA)^{-1}A^T\begin{bmatrix}1\\1\\2\end{bmatrix}$
I found that $det(AA^T)$ is singular… I think this means that their exist infinitely many least squares solutions to the system, but I don't know how to go about describing them all. I am relatively new to linear algebra (Uni level into class at the moment) so any help/explanation would be great!

Best Answer

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}$.

Related Question