Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In general, how do you solve a system with more equations than unknowns? I know that if I select the equations to match them with the number of unknowns, there may be zero or many solutions depending on our selection. Where can I go from there? And how does a "pseudo inverse" come in the picture? Thank you. -Cody

EDIT: I know overdetermined system usually have no solution, but in my case (triangulation matting, i.e filtering out the weatherman from the blue screen), I was told there is a solution and I need to find it using pseudo inverse.

share|improve this question
    
Do you know how to solve via using an augmented matrix? Follow the same procedure and in the end, if you have $k$ variables, rows $k+1$ through $n$ should reduce to a row of zeroes. If not, then there is no solution. –  Clayton Jan 19 '13 at 22:31
    
Are your equations linear? If we're restricted to real numbers, then you can solve $\sum x_i ^2 = 0$. –  Calvin Lin Jan 19 '13 at 22:34
add comment

3 Answers

up vote 1 down vote accepted

I'm assuming you're referring to linear equations.

Although the linear system of equations $Ax = b$ might not have a solution when the system is overdetermined, you can always find a least-squares solution

$$\min_x \|Ax-b\|^2.$$

If the minimum value is $0$, a minimizer $x$ is a solution to the system. Otherwise, $x$ is the "closest possible" solution, in the sense of minimizing the residual error, to a system that has no solution.

To find a minimizer $x$, you take a derivative and set it equal to 0:

$$A^TAx -A^Tb = 0.$$

The matrix $A^TA$ might be singular, but $A^Tb$ always lies in its column space so this system always has a solution. You can find one such solution by calculating $x = A^{+}b$, where $A^{+}$ is the Moore-Penrose pseudoinverse of $A$.

So to find a solution to your overdetermined system, one approach is to compute(*) the pseudoinverse $A^{+}$, then calculate $x = A^{+}b$. You can check if $Ax=b$ to see if your overdetermined system did in fact have a solution.

(*): My favorite method, in terms of robustness and efficiency, for computing the pseudoinverse is to use the QR decomposition of $A$. The details are beyond the scope of this answer, but worth looking up if you're interested.

share|improve this answer
add comment

In general, there is no solution. (I am assuming you are talking about linear equations, but this is also sort of true for polynomial equations.)

However, it might be that some of your equations are a consequence of the others, so they are not really independent equations, and there might be solutions.

In the case of linear equations, your system may be expressed as $Ax=B$, where $A$ is the coefficient matrix of your variables, and $B$ is the constants.

Now, your system has (at least one) solution if $rank(A) = rank(A|B)$ i.e. the larger block matrix $A|B$ does not have larger rank than the matrix $A.$

If $rank(A)$ equals the number of variables, (and $rank(A) = rank(A|B)$) then the system has a unique solution, and if less, you will have infinitely many solutions. if the rank is less, then you even have infinitely many solutions.

share|improve this answer
add comment

You can think of an overdetermined system as a bunch of data points (rows of $A$) that you want to fit the best line (or plane, hyperplane, etc.) to ($x$). The solution probably won't even intersect any of the points, but it will be the best solution in that it will minimize the sum of squared errors of all of the points relative to the solution. (That's one way of thinking about it.)

A pseudoinverse is any $A^+$ that satisfies $A^+AA^+=A^+$ and $AA^+A=A$ (obviously a regular inverse satisfies these properties too). If you let $x^* = A^+B$ then $x^*$ will be the best fit for the normal to a hyperplane that estimates all the rows of $A$. That is, $\|Ax^*-B\|^2$ will be minimized.

So again, the pseudoinverse probably won't give you a solution, but it will give you the next best thing.

Most math packages have some kind of pinv function that will compute the pseudoinverse of a matrix, and will usually compute the Moore-Penrose pseudoinverse.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.