Line-fitting algorithms for exceptional cases--minimax line fitting
In many embedded systems design applications, line-fitting techniques, particularly minimax algorithms, are used instead of the more well-known regression methods to "fit" noisy data. More often than not, minimax fitting is preferred to regression when the goal is to find a fitting line with minimum tolerance, such as some automatic control applications.
My first exposure to minimax line fitting came via an engineer who asked me to help him fit some sampled sensor data. He was getting unacceptable results with regression and thought that minimax might do better. The engineer told me that he wanted something quick and simple and that small code size was required, but that high performance was not a priority because the computations would be done off-line.
This article presents my own attempts to meet these requirements. It describes both useful strategies and pitfalls to avoid in tackling similar problems.
Regression does not always give the "best" linear fit
By far the most common way to fit noisy data with a line is to use simple regression. If the noisy data consists of points (xn,yn), n=1,…,N, then the regression equations give:
Y = M•X + B
where M and B are defined in terms of the accessory values ΣX, ΣY, ΣXX, and ΣXY as follows:
ΣX = the sum of the x-values = Σnxn
ΣY = the sum of the y-values = Σnyn
ΣXX = the sum of the x2-values = Σnxn2
ΣXY = the sum of the xy-values = Σnxnyn
M = (N•ΣXY -ΣY ΣX) / (N•ΣXX -ΣX ΣX)
B = (ΣY - M•ΣX) / N.
Nonetheless, there are many cases where regression is not the best option, for instance when:
• a minimax fit is required (in other words, one that minimizes the maximum deviation between line and data);
• the noise varies systematically in such a way that it affects the linear trend;
• the linear fitting is taking place real-time and is continually adjusted as new data comes in;
• there is a possible alias in the y-value (for instance with angle data, there may be an ambiguity of ±k•π or ±2k•π);
This article will discuss minimax fit. Additional articles, which will appear later this month on Embedded.com, will deal with the other cases.
Loading comments... Write a comment