# Overdetermined set of quadratic equations

I am having a set of equations of the form \begin{align} (x - a_1)^2 + (y - b_1)^2 + (z - c_1)^2 &= W_1\\ (x - a_2)^2 + (y - b_2)^2 + (z - c_2)^2 &= W_2\\ & \vdots \\ (x - a_m)^2 + (y - b_m)^2 + (z - c_m)^2 &= W_m. \end{align} Here $a_1,\ldots ,a_m, b_1,\ldots, b_m, c_1,\ldots, c_m$ and $W_1,\ldots, W_m$ are known constants and $m$ can be any number greater than $3$. Hence this is like overdetermined set of quadratic equations in three unknowns $x$, $y$ and $z$.

How can we solve these equations?

-
If you subtract any two equations you get a linear equation in x,y, and z. With more than three equations this is just inear algebra, solve and check to see that your answer works. With just 3 forlve for x and y and substitute to get a quadratic is z – deinst Aug 3 '11 at 12:17

If your equations are consistent, the approach of deinst will work. If not, which seems likely given your nonlinear-optimization tag, you have a three dimensional minimization problem. You can create a function of $x,y,z$ which is the sum of the squared errors of all the equations and feed it to your favorite minimizer. Calculating the gradient is pretty easy, so you might want to use one of those methods, but this feels like it might have many minima. Any numerical analysis book will have information, one of my favorites is chapter 10 of Numerical Recipes. The obsolete versions are free.

-
I think your are right, i have three unknowns x, y and z and more than three equations. Geometrically it seems that these are spheres and in general would not intersect in a point. So I have to find a point that in the overlapping region that minimizes the error in least squares sense. I hope my analysis is correct. Any ideas? – maths-help-seeker Aug 5 '11 at 15:18
You are right that these are spheres and they need not intersect in a point-in fact will not if there are errors. There may even not be any region where all the spheres overlap. But given a trial point $(x,y,z)$ you can assess the error in each equation like $e_1=(x - a_1)^2 + (y - b_1)^2 + (z - c_1)^2 - W_1$ and so on. Then the total squared error is $f(x,y,z)=\sum e_i^2.$ This is what you would feed to the function minimizer. – Ross Millikan Aug 5 '11 at 15:24
Yes, you are correct. Generally speaking, they may not have overlapping region as well. Thanks for the help. – maths-help-seeker Aug 5 '11 at 15:30

Looks to me like you have a bunch of 3-D points and you want to fit a sphere to them.

The equation of a sphere is $r^2 = (x-a)^2 + (y-b)^2 + (z-c)^2$. This seems to be nonlinear in its parameters (r, a, b, c).

However if we write it as $$r^2 = (x-a)^2 + (y-b)^2 + (z-c)^2 = x^2+y^2+z^2+2\ a\ x+2\ b\ y+2\ c\ z + a^2+b^2+c^2,$$ and let $v = a^2+b^2+c^2-r^2$, the equation becomes $$0 = x^2+y^2+z^2+2\ a\ x+2\ b\ y+2\ c\ z +v$$ which is linear in its parameters (a, b, c, v). Put this into a linear least squares solver, and then get $r$ from $a, b, c,$ and $v$.

This works for any number of dimensions. I used it about 25 years ago to fit circles to data points, and it worked quite well.

I know that this does not do a least squares fit of the sphere to points (which is nonlinear), but it works well and can generate good starting parameters for an exact nonlinear fitting process.

A suggestion I have found useful in practice: If you have many points and they are far from the origin, shift the origin so it is at the center of the points. Otherwise the computation of $r$ from $a$, $b$, $c$, and $v$ can be inaccurate.

-
Oops - my answer may not be to OP's question. However, I like my result anyway, so I will leave it in:) – marty cohen Aug 8 '11 at 22:58

If you use the quadratic functions in least square, then you will have a degree four for the sum of squared errors (i.e., the objective function) to minimize. The derivative will be cubic -- i.e., the derivative will have multiple zeroes.

Geometrically, you can intersect every 3 sphere. For those that have 3 way intersection (i.e., every two of the 3 spheres intersect), you can define a pyramid; the edges of the pyramids are curved (circular arcs). NB there is an issue here that can be illuminating, please see below.

Then given the vertices you can go multiple ways there: 1) take the center of these vertices 2) Start with convex hull of the vertices and remove the vertices on the outside, until you get a set that is no longer defines a 3 dimensional volume !!! then go one step back and take the centeroid.

Here is the problem the pyramids can be totally disjoint and far away from each other with no overlapping volume. That in itself, can tell you a lot abut your problem :-)

-

If you subtract two equations from each other, you get a linear equation in $x$, $y$, and $z$.

Now without making it too complicated:

1. You can subtract every two equations, then do a least squares.
2. Subtract a subset, which will give you a different answer.
3. You can try and do outlier rejection by taking a subset and do something like a Ransac.
-
Would you mind removing all of the stupid stuff from your answer? – Dan Rust Sep 27 '13 at 23:02