Solution for least squares problem

Question

I was going over the linear algebra regarding how to solve the least squares problem and had a few questions regarding the solution.

When solving the $||Ax-b||^2$ I understand the derivation of expanding it, taking the derivative with respect to x and setting it to $0$ to reach this:

$(A^TA)x = A^Tb$

Now let us assume $A$ is an $nxm$ matrix with $n>m$

I understand that if A has rank $m$ then the least squares solution will be unique as $A^TA$ will be invertible. However what if A has rank $q$ where $q<m$ , then does the least squares solution can't be unique so how does it go about solving the problem?

Will there be an infinite number of solutions and can there potentially be no solution? I was having a tough time trying to figure out these last two questions and was hoping to get some intuition on them.

Lastly, how would software go about solving the least squares problem when A has rank $q$ where $q<m$

Answer 1

I think it could be instructive to see what happens in a concrete case. Consider, for instance, $n=3, m=2$. Then if $q=m$, the image of $A$ is a plane, and solving $A^TAx=A^Tb$ finds the point on the plane which is closest to $b$, and the $x$ that is mapped to that point by $A$.

If $q=1$, then the image of $A$ is a line. Solving $A^TAx=A^Tb$ finds the point on that line which is closest to $b$, and the $x$ that are mapped to that point by $A$.

There will always be at least one solution. $A^Tb$ is in the image of $A^T$, and since $A^T$ and $A^TA$ have the same rank, they must have the same image, giving us at least one solution.