I want to solve a least squares problem, $$ \min_x ||y - A x ||^2 $$ with $A \in \mathbb{R}^{m\times n}$. Suppose I were to find two distinct solutions $x_1,x_2$, which solve the problem, so that $$ ||y - A x_1 ||^2 = || y - A x_2 ||^2 $$ Does this imply that $A$ has a non-trivial null space?
Certainly, if $x_2 = x_1 + z$ and $z \in Ker(A)$, then the above condition would hold. But is it possible to have a non-singular $A$ which can have two distinct least squares solutions as above?
On
If $$\text{the columns of $A$ are linearly independent},$$ then $A^\top A$ is invertible and the solution is uniquely given by $$(A^\top A)^{-1} A^\top y.$$
The above condition is equivalent to $$\text{$A$ has a trivial nullspace}.$$
(Note that the above conditions include the case where $A$ is non-singular, but are more general since they handle cases where $A$ is not square.)
There is a unique vector in the span of $A$ (the columnspace of $A$) that is closest to $y$, namely the orthogonal projection of $y$ onto the columnspace. Since $Ax_1$ and $Ax_2$ are both “closest” to $y$, then $Ax_1$ and $Ax_2$ are both the orthogonal projection of $y$ onto the columnspace, and therefore $Ax_1=Ax_2$; in particular, $x_1-x_2$ lies in the nullspace of $A$.
An interesting question in this situation is to find the vector $\mathbf{x}_0$ among all vectors for which $\lVert A\mathbf{x}-\mathbf{y}\rVert^2$ is minimal that has least norm. This can be done in two steps using the problem of “minimal solutions”, or in a single step by using the pseudoinverse of $A$.