3
$\begingroup$

I know there always exists a least-square solution $\hat{x}$, regardless of the properties of the matrix $A$. However, I keep finding online that least-square can have infinitely many solutions, if $A$ is not full column rank.

Shouldn't $\hat{x}$ always be unique, as the minimization of a quadratic function (the error) always yields a global minima/maxima? Therefore, regardless of what the matrix $A$ is (even if it is a badly constructed matrix with dependent columns), least-square should find a single 'best' solution $\hat{x}$?

Is there an easy (or intuitive) proof showing why would the least-square method produce infinitely many solutions if there are dependent columns?

$\endgroup$
3
  • 1
    $\begingroup$ In the higher dimensional space where defined by A, then less than full rank implies that there exists a linear combination of the columns of A that equal zero, hence you can always add any multiple of that linear combination to the minimum value to get another solution. If you reduced the dimensionality to just the linearly independent vectors, then you would have a unique solution. $\endgroup$
    – user237392
    Jun 29, 2015 at 3:20
  • $\begingroup$ Just think an extreme case, $A = 0 \in \mathbb{R}^{m \times n}$, then clearly every vector in $\mathbb{R}^n$ is a least square solution. $\endgroup$
    – Zhanxiong
    Jun 29, 2015 at 3:38
  • 1
    $\begingroup$ The predicted values are unique, regardless of the fact that the coefficients are not. ${}\qquad{}$ $\endgroup$
    – Michael Hardy
    Jun 29, 2015 at 4:44

4 Answers 4

Reset to default
9
$\begingroup$

Your least squares solution is minimizing $\hat x^T A \hat x$ If $A$ does not have full rank, there is some vector $y$ such that $Ay=0$. Then $(\hat x+y)^TA(\hat x+y)=\hat x^T A \hat x$ so you can add any multiple of $y$ to your solution and get the same product.

$\endgroup$
3
$\begingroup$

for what it is worth, the least squares solution to $$ H \hat{x} = z $$ is considered by multiplying on the left by $H^t,$ giving $$ H^t H \hat{x} = H^t z. $$ The matrix $H^t H$ is square and symmetric, indeed positive semidefinite. It is called the Gramian of the system in applications.

If the Gramian is nonsingular, therefore invertible, there is a single answer to the original problem given by $$ \hat{x} = \left( H^t H \right)^{-1} H^t z $$

The unknown variables are said to be observable if all this happens, which is the case if and only if the columns of $H$ are linearly independent.

From Kalman Filtering: Theory and Practice by Grewal and Andrews

$\endgroup$
1
$\begingroup$

Suppose that $\exists y \in Ker(A) / y \neq 0$. Now, let $\hat{x}$ be a least squares solution. That is: $\hat{x}$ is such that $||A\hat{x} - b||_2 = min_{x \in V} ||Ax - b||_2$. Notice that $A(\hat{x} + y) = A\hat{x} + Ay = A \hat{x}$, hence $||A\hat{x} - b||_2 = ||A(\hat{x} + y) - b||_2$.

This means that you have just created another solution that also has the minimum possible norm, provided that $Ker(A) \neq \{0\}$, which only happens if A is not full rank.

$\endgroup$
0
$\begingroup$

Nice property is to add constraint of the least norm of all solutions.
Then, if $ A $ is full rank there is one solution (Hence unique) while in the case $ A $ isn't full rank still there is one unique solution.

The great thing is that the Pseudo Inverse of $ A $ always yields both the Least Squares and Least Norm solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .