# Least Squares with Singular $AA^T$

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!

• Indeed, if $A$ is singular, then you cannot calculate the inverse of $A^TA$. In the case of a singular $A$, one needs to replace the term $(A^T A)^{-1}A$ by the Moore-Penrose-Pseudoinverse $A^+$ of $A$. – Roland Apr 16 '16 at 15:09
• Use that fact that $\ker A^T A = \ker A = \operatorname{sp} \{ (1,-2,1)^T \}$. – copper.hat Apr 16 '16 at 15:47
• You are looking for all $x$ that solve $A^TA x = A^Tb$. If you find any solution $x_0$ then $x_0+n$ is also a solution for any $n \in \ker A^TA = \ker A$. A solution to $A^TA x = A^Tb$ must exist and you can find a solution any way you wish, such as row reduction. So, you need to characterise $\ker A$. I have given one element above, you can show that $A$ has rank 2 (look at the range, for example). – copper.hat Apr 16 '16 at 15:57
• If $x_1,x_1$ are two solutions you must have $A^T A (x_1-x_0) = 0$ and so $x_1-x_0 \in \ker A^TA$. You can show $\ker A^TA = \ker A$. This is why we care about $\ker A$. – copper.hat Apr 16 '16 at 16:30
• No worries, glad to help! – copper.hat Apr 16 '16 at 16:31

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 overdetermined 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, $x=A^+b$ is an exact solution with minimal $x$, and for any vector w, $A^+b+(I-A^+A)w$ is an exact solution that may not have minimal $\|x\|$.

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