So, as it turns out, we can get the "harder" sum in U without doing a summation at all. Just take the old value, add five times the newest y-axis data value, and subtract the new value of u₁. Piece of cake.

Now that we have expressions for both Q and U for this special case, we can write down the scalar expressions for a and b. They are:

(35)

This is the way I implemented a real-time version of the least squares fit, some years ago. Trust me, you will not find a simpler implementation anywhere on the planet.

Of course, you may choose to use a different number of data points in your implementation. But the process is the same; only the values of the summations change.

The general case
All the analysis you've seen here so far has been for the special case where we assume a linear polynomial for f(x). You might think that if we want to fit higher-order polynomials, we'll have to abandon the linear algebra used so far. But we don't. The order that matters is not the order of the polynomial, but the order used in the error penalty function. That's always going to be order 2 (hence, least squares). If we try to fit higher-order polynomials, we'll have more unknown constants to solve for, so we'll need larger matrices. But we still get to use linear algebra. For the general case, the matrices Q and U look like this:

(36)

(37)

where k is the order of the polynomial being fitted.

You can see the pattern. The elements of Q are equal down the minor diagonals, and are the sums of various powers of x_i. The elements of U have sums involving y_i times some power of x_i. All the relationships we've seen so far, including the fact that Q depends only on the x's, and can sometimes be computed in advance, still hold. The only difference is that, for polynomial orders greater than one, the matrix inversion becomes nontrivial.

Remember again, though, that if the data is measured at a fixed rate, as is often the case with embedded systems, the value of Q, and therefore its inverse, doesn't change.

More generalizations
Can we use the concept of least squares fits with functions other than polynomials? You bet we can. Whenever you can express the fitting function as a linear combination of primitive functions, you can still apply the least squares criterion. That is, if your trial function has the form:

(38)

You can apply the least squares method of Equations 11 to 16 as usual. You'll still get equations in which the derivatives are linear in the constants, so you'll still get a linear algebra solution like Equation 19. It's just that the summations will not be so easy to evaluate and will require calls to the primitive functions.

Even more generally, we aren't absolutely required to restrict the unknown constants to the role of linear coefficients. Any function f(x, a, b, ...) will do. In that case, however, the partial derivatives are liable to be messy, and it's likely that you won't be able to solve the resulting simultaneous equations for the minimum.

On the other hand, with the computing power available to us these days, and powerful numerical optimization methods, we can still hope to determine the optimal values of the unknown constants using some numerical optimization method.

And yes, now that you ask, I've implemented this kind of least squares fit in embedded real-time software, too.

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10