0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$

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.