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!

  • $\begingroup$ 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$. $\endgroup$ – Roland Apr 16 '16 at 15:09
  • $\begingroup$ Use that fact that $\ker A^T A = \ker A = \operatorname{sp} \{ (1,-2,1)^T \} $. $\endgroup$ – copper.hat Apr 16 '16 at 15:47
  • 1
    $\begingroup$ 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). $\endgroup$ – copper.hat Apr 16 '16 at 15:57
  • 1
    $\begingroup$ 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$. $\endgroup$ – copper.hat Apr 16 '16 at 16:30
  • 1
    $\begingroup$ No worries, glad to help! $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.