Why all the math?

6/5/2009 5:57 PM EDT

An e-mail to Richard Nass from a reader:

Hi guys,

Re: Jack Crenshaw's "Why all the math?" in Embedded System Design, June 2009...

The article was excellent, but there is another simplification that Jack didn't mention, and that is applicable to Jack's simplest least squares "implementation anywhere on the planet."

Just as you can arrange for the Xs to range from 0 to n-1, assuming n is odd (which is true in Jack's example) you can also arrange for the Xs to range from -floor(n/2) to floor(n/2). This has the happy result that the sum of the Xs is zero.

Referring to equations (16) in the article, these then simplify to:

a = sum(Yi) / n

b = sum(Xi * Yi) / sum(Xi * Xi)

The same techniques Jack used to produce an on-line real-time version of the algorithm apply.

There is a closed form solution for sum(Xi * Xi):

m = floor(n/2)
sum(Xi * Xi) = m * (m + 1) * n / 3

In the case of n = 5, the sum(Xi * Xi) = 10.

Using u1 and u1+ as Jack defined them in equations (27-29), we can define:

u1- = u1 - Y(k-4)

u1+ = u1- + Y(k+1)

u3 = -2Y(k-4) + -1Y(k-3) + 0Y(k-2) + 1Y(k-1) + 2Y(k-0)

u3+ = -2Y(k-3) + -1Y(k-2) + 0Y(k-1) + 1Y(k-0) + 2Y(k+1)

u3+ = u3 + 2Y(k-4) - u1- + 2Y(k+1)

Note that both 2s in the equation above correspond to m = floor(n/2).

Now,

a = u1+ / 5

b = u3+ / 10

Regards,

--Doug Currie
Consulting Engineer
Sunrise Labs, Inc.

6/5/2009 6:14 PM EDT

The following comment is from Jack Crenshaw to Doug Currie:



Excellent stuff, Doug!

I'll probably work with your equations to get them in the right form. Thanks for the idea. It's one I definltely hadn't thought of.

--Jack

6/6/2009 10:31 PM EDT

I'm not particularly good in math but I love your column, Jack. Keep up the great work.

6/8/2009 3:08 PM EDT

This is the kind of "embedded" programming I do as well, so thanks for the articles.
In your section "Why Least Squares?" you didn't make the interesting connection between least squares and probability. If the noise in the measurements is Gaussian then the pdf of the measurement is proportional to exp(-e^2/sigma^2) and the pdf of the set of independent measurements looks like exp(-M/sigma^2), where this is the M of eq. 11. Hence the model found by the least squares approach has the greatest probability of producing the measured data. (I know I'm not being entirely rigorous here).
A simple but profound observation is that the least squares solution for zero-order polynomial (i.e. constant) is the mean of the data. We use the mean intuitively to reduce noise; we can justify it as both the least square solution and the most likely solution given Gaussian measurement noise.
One final observation, the median minimizes the sum of the absolute errors; it is the median that is often used when we don't trust that the errors are truly Gaussian.

6/11/2009 1:21 AM EDT

Hello Jack,

Good to see a detailed article, specially on the subject I am working on currently and trying to get this in firmware hoping for better estimates. Gives me goose bumps.

Regards,
~
Jagmeet
~

6/29/2009 8:18 AM EDT

Jack,
I can give you one reason 'Why all the math?'.. I think because fluency with math is pivotal to our fundemantal grip of any physical process.
Frankly I'm tired with shrink wrapped and abstracted solutions to everything! Abtraction = Assumption very often.
Unless you wrote the 'concrete' underlying the abstraction yourself, you will be assuming the writer of the asbtraction knew what they were doing.. and then hope the documentation is well written and correct, while written with sufficient context to help you in your implementation.

Understanding and experience have power attached to them. Once you have these, you can freely abstract away...or buy code that does what you want: In any case you can then make a properly, informed decision.

Summary of reasons to get with math..
a) Just because Mathlab does somefunc(), for example, does not mean I understand it.
b) Or that I understand it well enough to use it in my own code.
c) Understanding is a vital key to creativity.
d) Creativity is why we are here and why we expect to get paid.

Also imagining that "stuff has been 'done before', so why should I bother?" is just so short sighted. It's like reading a book about playing the flute and not picking one up. Nothing beats the 'actual experience' -- you get to know the 'concrete' underneath..that's real value...

I like what you do Jack and I like your honest, experienced, friendly and knowledgeable style. And you can't be expected to cover all ground in a few articles. Your mentioning something like matrix atrithmetic, then showing me examples of how to implement it has made me aware of something that I never imagined I could use in my programs so (relatively) easily and would otherwise have had no idea, would be of such far reaching value. Period.

I used your integer based square root algortithm on the 8051 and sped things up considerably because I factored the precision appropriately-- because you made me aware of the ramifications of algorithms. And there always so much more to know on ANY subject. What you have done in your columns is to demystify math and then trigger more learning by putting it in the context of a real CPU and compiler. GOOD!!

I'm grateful..This is where the road meets the rubber..

You have more than done your job for mine!!
Kind regards,
Steve

7/8/2009 9:54 PM EDT

I'm glad you brought up the "Mathlab has a function" thing, because I had another point to make. Sometimes you really can buy tools that do what I tend to write about. Case in point: A few years ago I wrote about "The Rosetta Stone," which was all about z-transforms and filters and things. I showed how to derive the coefficients for filters of various kinds.

Thing is, nowadays you can buy tools specifically to generate filter coefficients. Whereas I wrote about 2nd or 3rd order filters, you can buy tools that will generate, say, 50th order filters. Some will actually burn the E3PROMs for you. Ditto for logic minimization. Just give the program a truth table, and it's generate the file to burn the chip.

For those folks who do this stuff every day, I highly recommend getting the most powerful tools you can, and let the computer do all the work. But, as in the case of the least-squares fit (LSQ), it's always bothered me if there's something going on in the black box that I don't understand.

I don't believe in re-inventing the wheel. Once I understand how LSQ works, I have no problem at all asking an app to generate me a 6th or 8th order polynomial fit, or a nonlinear fit like Micromath does so well.

I guess it's like building a fire. I don't have to be the one to do it every time, but I like to know I could if I had to.

Jack

8/24/2010 5:51 AM EDT

This is one of the best descriptions of implementing an algorithm, furthermore, the spirit in which it is written is fantastic. Wish I had this man as my math prof !