# Solution for least squares problem

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 , 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

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.
• When $q$=1 , is every set of $x_{1}$ and $x_{2}$ that satisfy the equation on the line a valid solution? I ask because you said $A^TAx = A^Tb$ finds the point on that line which is closest to $b$ so I'm not sure if you mean a unique point or any any point on that line. I'm inclined to say any two points which satisfy the equation of the line are valid solutions... just not sure yet. Aug 10, 2020 at 17:39
• @Shrey8 In the $q=1$ case, the equation has a line of solutions in the plane. This line is sent to a single point in $3$-space. And of all the points in all the (one-dimensional) image of $A$, that one point is the one which is closest to $b$. Aug 10, 2020 at 21:49
• So there is a unique point on the line which is closer to $b$ than any other point, and that unique point is the image of a line in the plane (as $A$ has rank 1), and that line in the plane is the set of solutions to the equation. Aug 10, 2020 at 22:17