Is it worse an over or an under determined system of linear equations?

[fisico30]

Hello Forum,

a system of linear equations can be determined (if there are as many unknowns as equations), overdetermined or underdetermined.

In general, is it easier to solve an overdetermined or an underdetermined system?

Am I correct in thinking that both have an infinite number of possibile solutions or no solution at all? In the case they have infinite solutions, are the available linear algebra tools more in favor of underdetermined or overdetermined systems?

Thanks
fisico30

 

[HallsofIvy]

An "over determined system" has NO solution: there is NO x such that Ax= b.
An "under determied system" has an infinite number of solutions: there exist an infinite number of x such that Ax= b.

For an over determined system, there are Linear Algebra techniques that would get x that "comes close" to satisfying Ax= b. Most notably the "least squares solutions".

For an under determined system, there exist Linear Algebra techniques to write a formula for all solutions. As to which is "better", that is a value judgement. Judge it any way you want. Personally, I would prefer a whole lot of correct solutions to some that are "pretty close".

 

[Vaedoris]

An "over determined system" has NO solution: there is NO x such that Ax= b.

I beg to differ: If b is in the column space of A then there is a solution x, otherwise there is no solution.

 

[fisico30]

Hello Vaedoris,
thanks for the reply.

I am familiar with columns space and row space: they are the spaces (or subspaces) of vectors formed by the linear combination of the column vectors and row vectors.

In an equation like Ax=y (say a determined system) how do the solutions x relate what we find inside the column space and/or the row space?

I am not able to get a sense of what the row and column space truly are and how they can be useful in the resolution of Ax=y.

Also, in the case of an overdetermined system, there is no exact solution (aside from the special case you mentioned). Can we not get rid of those extra, useless equations and make the system determined?

Thanks
fisico30

 

[Vaedoris]

You could find the reduced row echelon form of the matrix (of an overdetermined system) to determine which rows are dependent. Then, take them out, but you must also erase the corresponding components of the vector b.

Edit: However, this does not guarantee that the reduced matrix is square as erasing rows creates an under-determined system for the case where matrix rank is less than number of columns. On the bright side though, erasing dependent rows does not change the row space.

Personally, I would solve for the solution x by finding the left inverse (using some computer program) if the matrix has full column rank.

 

[schaefera]

I'm sorry, but I think you are mistaken.

An over-determined system has more equations than unknowns. This doesn't mean it is inconsistent. Imagine a whole lot of lines (more than 2) that all happen to intersect at a certain point. This is a solution to the over-determined problem.

An under-determined system has fewer equations than unknowns. It may have no solutions (parallel planes, for instance). Of course, if it has solutions then it has an infinite number. But it is possible that there be no solutions.

 

[Vaedoris]

I don't think you are talking about the same thing.

Besides, your example of intersection of lines is just one case of overdetermined system (where rank = number of columns - if you write the problem in matrix form). What I explained above is the other case:

For overdetermined system, mathematically, you can construct an $m\times n$ matrix that has more rows than columns (m>n) and yet you can have rank that is less than the number of columns (r<n).

Clearly for this case, erasing the dependent rows gets you a new matrix that is under-determined because there are only r independent rows but r is less than n (r<n<m).

Also, the existence of solution depends on whether the vector b (in the equation Ax=b) is in the column space of A as directly implied by the equation itself. So, there are vectors of an overdetermined system that are not in the column space (e.g. all vectors in left nullspace except the zero vector) and therefore for those vectors they have no solutions. Of course, the same applies to under-determined systems.

 

[schaefera]

Nevertheless, my example proves false the statement that overdetermined systems have no solutions.

 

[Vaedoris]

Well, that's what HallsofIvy claimed (probably just some unintentional mistake).

Not me.P.S.: You could create unlimited number of counter-examples to that claim by just inspecting Ax=b. "Intersection of straight lines" though may not be obvious to some people.

 

[HallsofIvy]

I don't think you are talking about the same thing.

Besides, your example of intersection of lines is just one case of overdetermined system (where rank = number of columns - if you write the problem in matrix form). What I explained above is the other case:

For overdetermined system, mathematically, you can construct an $m\times n$ matrix that has more rows than columns (m>n) and yet you can have rank that is less than the number of columns (r<n).

That is NOT what I would call an "over determined sytstem". Given that definition, you could take any system of equations, add some equations that are equivalent to those you already have, and declare it "over determined". To me, and "over determined system" must have more equations than unknowns that cannot be reduced.

Clearly for this case, erasing the dependent rows gets you a new matrix that is under-determined because there are only r independent rows but r is less than n (r<n<m).

Also, the existence of solution depends on whether the vector b (in the equation Ax=b) is in the column space of A as directly implied by the equation itself. So, there are vectors of an overdetermined system that are not in the column space (e.g. all vectors in left nullspace except the zero vector) and therefore for those vectors they have no solutions. Of course, the same applies to under-determined systems.

 

[Vaedoris]

Many textbooks define an overdetermined system as simply a system that has more equations than unknowns. I have yet seen one definition that restricts it to being "irreducible" or that it must have full column rank!

For example: You can have a matrix that has more rows than columns with its rank less than the number of columns but the matrix equation is still an overdetermined system because it has more equations than unknowns.

 

[fisico30]

So, how about schaefera example?
Is multiple lines intersecting at a single point an example of an overdetermined system having a solution?

Clearly, a consistent system, with as many equations as unknowns, can always be made overdetermined by adding dependent equations (scaled versions of the already existing equations, sums of the existing equations, etc...).

I guess I would like to understand why a "true" overdetermine system cannot have a solution in many cases. I feel that it is more about having some extra equations that are in contrast with the other ones: the extra equations have different solution from the other ones which have a common solution...

thanks
fisico30

 

[jasonRF]

Hello Forum,

a system of linear equations can be determined (if there are as many unknowns as equations), overdetermined or underdetermined.

In general, is it easier to solve an overdetermined or an underdetermined system?

Am I correct in thinking that both have an infinite number of possibile solutions or no solution at all? In the case they have infinite solutions, are the available linear algebra tools more in favor of underdetermined or overdetermined systems?

Thanks
fisico30

I hate to say this, but the answer to such a general question is, "it depends." Perhaps you can give more detail on what the context is?

Many other folks have posted replies with the emphasis on finding exact solution to a set of exact equations, so I will give another perspective in case you are interested. In many practical applications we are modeling a phenomenon based upon some set of (imperfect) measurements. If our model is linear in a set of unknown parameters, then we end up with a system of linear equations that in general is inconsistent, due to the imperfect measurements.

The most common approach to dealing with the inconsistent equations is to use least-squares. If we have at least as many independent measurements as we do unknowns (that is, the rank of the matrix is equal to the number of columns) then the least-squares solution is unique. This case is often referred to as the "full-rank" case. If the rank of the matrix is less than the number of columns then there are an infinite number of least-squares solutions. This case is often referred to as the "rank-deficient" case. One then has to pick the solution that you are most interested in: sometimes you may want the least-squares solution with the fewest nonzero elements, other times you may want the least-squares solution that has the smallest norm, other times you may not even care which solution, etc. In all cases, there are good linear algebra tools that can be used. But most would agree that overdetermined is far better than underdetermined for solving least-squares, and more equations yields better estimates.

jason

 

[fisico30]

Hi Jason,
Thanks for the reply. I can live with "it depends".
Are you familiar with compressive sampling? It sounds like you are.
IF so, can I shoot some questions?
thanks
fisico30

 

[jasonRF]

Hi Jason,
Thanks for the reply. I can live with "it depends".
Are you familiar with compressive sampling? It sounds like you are.
IF so, can I shoot some questions?
thanks
fisico30

sorry - I don't know anything about compressive sampling. It is one of many things I would eventually like to learn, though!

jason

 

[fisico30]

Hello jasonRF,

another simple question: in the situation Ax=y, the column space and the row space from A can be different. The rows and columns span different sets of vectors...

How do the column space and the row space relate to each other and how are they helpful in finding the solutions x?
Can we derive one from the other?

thanks
fisico30