1
$\begingroup$

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?

  • 1
    "Consistency" means that the system has a solution. What you are asking is not how to check for consistency, but rather how to check if a particular $x$ *is* a solution. What's wrong with plugging it in? It's pretty straightforward, and pretty quick.2010-12-15
  • 1
    Why do you not like the approach that you mentioned in your last sentence?2010-12-15
  • 0
    @Arturo, I afraid that it can be numerically unstable; I would like to implement this on a computer, so I would prefer a solution that fully works here.2010-12-15
  • 0
    @J.M., see the updated question2010-12-15
  • 0
    Ngu, you can swap rows (pivoting)... but you will have to remember the permutations you did.2010-12-15
  • 0
    @J.M., that's just a solution to the above special case. What about general solution?2010-12-15
  • 1
    You can still swap rows. Gaussian elimination routines generally swap rows for stability purposes anyway. Look up "partial pivoting".2010-12-15

3 Answers 3

4

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

  • 1
    mpiktas, that's for least squares. For instance: if you QR decompose the 3-by-2 example of Ngu (call the original matrix $\mathbf A$), and let $\mathbf b=(2\quad 3\quad 4)^T$ and $\mathbf x=\left(0\quad \frac1{10}\right)^T$ , your equation doesn't work, even if the $\mathbf x$ I gave minimizes $\|\mathbf A\mathbf x-\mathbf b\|_{\infty}$2010-12-15
  • 0
    @mpiktas, how to compute the $x$ in this case?2010-12-15
  • 0
    Yes, you are right. You cannot even multiply $Q$ by $b$, since the dimensions do not match. The answer I think still lies in decomposition of $A$, but it should be rephrased better.2010-12-15
  • 0
    @Ngu Soon Hui, sorry my answer is incorrect. I will see if I can fix it.2010-12-15
  • 1
    OK, I fixed the answer. Actually there is a slight typo in the question, $b$ should be $n\times 1$ vector, not $k\times 1$.2010-12-15
  • 0
    @mpiktas, even with your fix, I still fail to see how to compute $x$.2010-12-15
  • 0
    @Ngu Soon Hui, you do not have to if you only want to check whether $x$ is the solution.2010-12-15
  • 0
    @mpiktas, that's the problem: without $x$, how to check whether the equation $Rx=Q^Tb$ is fulfilled?2010-12-15
  • 1
    @Ngu Soon Hui. When we get to the matrix $R_1$ and vector $b_1$ we get the square linear system. Since determinant of $R_1$ is non zero, the solution always exists. If $Q^Tb$ is not of the form I mentioned, then the solution of the original system does not exist.2010-12-15
  • 0
    @mpiktas, I think your above formulation is still wrong. Take this equation: $Rx=Q^Tb$. Note that the LHS the dimension is $n \times 1$, but the RHS the dimension is $k \times 1$. There is a dimension mismatch here.2010-12-16
  • 0
    Matrix $A$ dimension is $n\times k$, matrix $Q$ dimension is $n\times n$, matrix $R$ dimension is $n\times k$. Vector $x$ dimension is $k\times 1$, vector $b$ dimension is $n\times 1$, so $Rx$ dimension is $n\times 1$, and $Q^Tb$ dimension is $n\times 1$. Everything is ok.2010-12-16
0

I am not sure why I cannot comment, but anyway, you can always do an RREF and then you should be fine.

  • 0
    let's say if there is no matlab involved?2010-12-15
  • 0
    Manually doing an RREF is not that difficult. How else do you invert a matrix? (assuming you do not know LR decomp)2010-12-15
  • 0
    ah, I get your point. But how does RREF helps to find the $x$?2010-12-15
  • 0
    perform a GJ elimination to solve for x2010-12-15
0

Consider the related least squares question: find x minimizing $||Ax-b||_2$. In the unlikely scenario that the overdetermined system has a solution, then we in fact have $||Ax-b||_2=0$.

The x solving the least squares problem can be found via the Moore-Penrose pseudoinverse:

$$x=(A^tA)^{-1}A^tb$$

So, one algorithm would be as follows:

1) Solve $(A^tA)x=A^tb$ via your favorite linear solver.

2) Check if $Ax-b=0$.

  • 0
    1. If $\mathbf A$ is rank deficient, the normal equations method fails. 2. I've mentioned the Lauchli example in here and other places on why the normal equations isn't always a good idea. The QR and singular value decomposition are safer alternatives.2010-12-16
  • 0
    If you use a krylov solver like conjugate gradient and the initial guess is not in the null space of A, then it should work even with rank-deficient A (I think), though the point on stability is a good one.2010-12-16
  • 0
    Krylov methods are appropriate only for large sparse systems. For small dense problems, QR and SVD remain standard.2010-12-16