I have the following overdetermined linear equation system:
$$Ax=b$$
where $A$ is a matrix of $n \times k$, $x$ is of $k \times 1$,$b$ is of $n \times 1$, where $n>k$.
We all know this is an overdetermined linear equation system.
The question is how to check whether the solve for $x$, and check that the vector is consistent in this case? Consistent as in the sense that when we plug in the $x$ vector value into the above linear equation systems, then the above matrix will be satisfied.
I can separate out the $k$ linear equations and find $x$ from $x_1$ to $x_k$, and then substitute in the remaining equations to check for consistency.
I afraid that this method can be numerically unstable; I would like to implement this on a computer, so I would prefer a solution that fully works here. Let us consider one pitfall of my above solution:
$$A=\begin{bmatrix} 10 & 10 \\ 0 & 0 \\0 & 10 \end{bmatrix}$$
Note that if you separate the $1$ and $2$ rows out, and compute the solution, you may not be able to even solve it ( equation $2$ is an equation here with no unknown terms, after you times in the $0$ factor)!
Is there other method?
Best Answer
Updated according to comments.
If you are worried about the numerical stability do QR decomposition of matrix $A$. Then $A=QR$, where $Q$ is orthogonal and $R$ is triangular. Then you need to check whether $x$ satisfies the equation
$$Rx=Q^Tb$$
Now since $R$ is triangular and $n>k$ we will have that the last $n-k$ rows of $R$ are zero. Since $Ax=b$ it follows that the last $n-k$ elements of $Q^Tb$ should be zero also. If they are not, then $x$ is not a solution.
Furthermore since we have an overdetermined matrix the solution exists only if $b$ lies in the linear space spanned by columns of $A$. So the real question is, how do we reliably check whether $b$ is in linear space spanned by columns of $A$.
Update 2
Since $n>k$, the $R$ matrix will look like:
\begin{align*} R=\begin{bmatrix} R_1\\ 0 \end{bmatrix} \end{align*} where $R_1$ is $k\times k$ upper triangular matrix. If the solution exists, then
\begin{align*} Q^Tb=\begin{bmatrix} b_1\\ 0 \end{bmatrix} \end{align*} where $b_1$ is $k\times 1$ vector. The solution for our system is then $$x=R_1^{-1}b_1$$