MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let there be a possibly overdetermined system AX = B, where B are some measured data, with a low noise level. To cancel out the measurement noise, and to allow for more unknowns, a large B is acquired, by making a lot of measurements, every time changing measurement conditions, represented by A, only by a very small step. Thus, subsequent rows in A are almost identical. But, rows that are far apart, are substantially different.

Thus, within such a system exist equations that are very similar to each other, so their solution hyperplanes are very close to each other.

Add a minimal noise, or even arithmetic round--off errors, and intersections of such similar hyperplanes can be practically random. Even worse, possibly with very large absolute values.

But various least squares solvers I tried take these random intersections into account, and return unusable values of X.

But, if the equations in the system are divided into a number of subsets of mutually dissimilar equations within each set, each subset solved individually by one of the same solvers, and then the solutions averaged into a single one, it turns out the averaged result can be usable.

The question is, are there solvers that already take into account the extreme similarity of certain pairs of equations within a system + some small noise.

Imagine a two--unknowns system with four equations, the four lines represented by the equations produce something like the # sign. The solver would average the four ~90 deg crossings in the center into the solution, but it would completely ignore the two near-infinity crossings of parallel lines.

Note that the measurements in B do not contain any outliers, the noise is very low, it's just the almost-linearly-dependent equations.

share|cite|improve this question
Instead of dividing into subsets of mutually dissimilar equations, why not divide the problem into subsets of very similar equations and average A and B components over each subset? If the rows of A form a fairly regular random walk in some high-dimensional space (as it seems they may), then this may not be effective, but otherwise it might. – Steve Huntsman May 27 '10 at 15:19
Steve, the question is, if the data lost because of the averaging is important, if two subsequent rows are almost linearly dependent anyway. I hoped there is a solver that handles the described problems internally. If not, I'll try dividing into subsets or averaging and will use generics solvers. Perhaps I'll use scalar product of pairs of rows, to check if they should be put to different subsets/averaged. Thanks for help, Artur – arataj May 28 '10 at 11:34

Your Answer


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

Browse other questions tagged or ask your own question.