how to solve a system with more equations than unkowns?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.