Math problem #1 - piecewise approximating functions

I'm the kind of person that can get very interested in things that others might not notice. For me, his seems to occur from time to time with math problems. I'll be thinking about an engineering problem, and I will get caught up with some mathematical aspect of it. Usually, it's some problem which is easy to state but not obvious to solve. (Then again, I'm not a mathematician)

Over the years, I've gathered up a list of these problems. And now, I'd like to share some of them on this blog. I hope some of you, at least, will find them as interesting as I do.

---

Today's problem is fairly simple to state - and I thought about it for the first time many years ago. Suppose I have a continuous function y=f(x), defined on an interval from x0 to xn. I know _everything_ there is to know about the function. Now, for some reason, I need to approximate the function using a "piecewise-linear" function. This is just a set of straight lines connected together at "break" points. (You can also think of this as an approximation based on splines.)

For say, a fixed number of break points, what is the "best" way to approximate the function? (BTW - this is something that is practically done all the time, in embedded computer programs, using "table lookups" to approximate functions)

Some clues:

For a given set of breakpoints located at each x_i, you can start by picking the breakpoints at (x_i, f(x_i)). In other words, points on the curve f(x), and connecting the points with straight lines. However, you will quickly notice that the approximation is biased, based on the concavity of the curve.

A better way for a given set of points at x_i, is to solve the linear least-squares problem to find the optimal y values, which minimize the error between the approximate curve and the actual one.

But the key question seems to be - how do I locate my points in x? I see no easy way to do this, without non-linear iteration. It seems strange that it is trivial to locate the points in Y given X values, but hard to locate the X values. I can imagine some heuristic rules like "I should use more breakpoints where the function is 'curvier'". But it's not at all clear what this means :) Maybe I need to think about the meaning of "best" a bit more.

So, to summarize, we have a situation where we have a function which we know everything about, and a simple space of approximating functions, but we seem unable to match the two together, without resorting to nonlinear iteration.

If this one is too easy for you, feel free to handle extensions to this problem with higher order piecewise splines, and/or multidimensional functions. :) I can imagine practical applications for a good algorithm in this area.

Yikes - more than 2 years without blogging!

Not the kind of anniversary I wanted to celebrate. Anyways, I'm in the middle of a move to a new house, and work is heating up. So, hopefully around October, things will settle down...and I will try to post something more regularly.

The Road to Reality

I have been interesting in Physics as a hobby for a very long time. Back in the mid-90's, I was reading about Quantum Mechanics and Relativity on a fairly regular basis. I had to really dig to find books that were deeper than a purely "popular" treatment, but not so deep that an engineer could actually make sense of them. Some math, not all math.

Having been trained as an engineer is "almost enough" to handle "some" of the math, but I ended up with an awfully long road ahead. I eventually got a bit discouraged, but never quite gave up. (Emulation came along and I got a bit distracted for a number of years.)

In 2004 Roger Penrose wrote a giant book on Math and Physics, call "The Road to Reality: A Complete Guide to the Universe". It is a highly mathematical, modern treatment, but it builds on itself such that, theoretically, someone with some math background can actually understand it all. (At least, they'll be able to self-direct to other resources as needed.) There are 16 chapters of Math (the first 1/3 or so), followed by as many on Physics. For comparison, my formal math training ended at chapter 7. I now find myself in chapter 15, nearly finished with the math section. It is definitely not for everyone, but it's exactly what I needed.

Finally, I have found that discussing the details of the book can help a lot with the understanding. I recently created a Yahoo Group called RTRFANS, for just this purpose. With this book, and with internet resources that weren't available in the mid-90's, I've now got a shot at understanding truly modern physics.

Some porting work

I really need to post more often!

For a while now, I've been wanting to experiment with new methods of high-speed circuit simulation. The idea would be to prototype some discrete-audio stuff, possibly for MAME, using something like Python.

After looking into the requirements, I realized that I needed to handle polynomials with a single variable, and ratios of these polynomials. Also, I needed to be able to handle real or complex variables. I looked around on the web, and I found that SciPy is finally coming along nicely on Windows. However, I wasn't entirely happy with the root finder they use.

Along the way, I also found the ratfun package, which looked perfect, but was unsupported on Windows. I dug in and in a couple weekends, got it building under Windows. I think I'll be using it for the experiments, whenever I get back to it.

The Joy of LaTeX

Ok, I'm a geek. Over the past 10 years or so, I've worked on a handful of math and engineering problems that I thought were interesting. Yes, most of them were "spare-time" activities, although a few were inspired by work stuff. I recently made a list of all of them, and I suddenly had the urge to publish them. Maybe some other people will find these things interesting as well.

At any rate, I wanted a way to publish them with all the math equations, as well as generate PDF's and HTML. I had heard about LaTeX for a long time, but now I had a fine excuse to give it a try.

I first tried the TeXLive distribution, but I never could get it to work on Windows. (Maybe this has been fixed since then) Then I tried MikTeX. It was a fairly straightforward installation. After working out a few examples, I was hooked. My first draft of a test article turned out pretty well:

http://www.avoidspikes.com/textest/gamma.html

I use pdflatex to generate pdfs and htlatex (part of tex4ht) to create html + pngs.

At any rate, it's nice to see that free software can be used to do professional typesetting. I'm planning to use this stuff to document my math problems, as well as some theory behind discrete sound filtering in MAME.

Actual MAME-related work!

For those who haven't heard, the speech chip used in Berzerk has been reverse-engineered by "Lord Nightmare"! This is something I've been waiting for for about 7-8 years! I'm sure that the emulation will end up in MAME and PinMAME sooner or later.

Because of this, I spent some time over Christmas looking at the analog filters on the Berzerk speech board. (These are applied to the sound after it comes out of the chip.) I finished the analysis, and it should be pretty straightforward to add them into MAME after the chip emulation is done.

For what it's worth, I've been trying out Maxima with wxMaxima to do the symbolic math for circuit analysis. I know, I could have used SPICE or something - but doing the math from scratch makes it easier to understand what is going on.

After I worked out about half of the math for these filters by hand, I ended up with about 6 pages of algebra. At this point, I figured I should use this as an excuse for learning Maxima. Sure enough, I found an error on page 5. Darned minus signs! :)

The second half of the analysis took about 5 minutes, since the code from the first half was already done, and I could re-use it!

For those who care - the filter is a third-order lowpass - a first order lowpass, followed by a second order with a resonant peak around 2400 Hz.

Firefly and Serenity

Well, I did it. I managed to watch all the Firefly episodes before checking out the movie, with two hours to spare :)

I've got to say, with every episode I watched, I enjoyed the series more. The writing and character development is really well done, and it's pretty darned funny to boot. I can't believe they canceled it just as it was taking off. It was kind of the opposite of what Star Trek and Star Wars have been of late. Less tech, and much more fun. And this is from a guy who has a penchant for hard science fiction.

At any rate, I also enjoyed the film. I went with three others who hadn't seen Firefly, and they seemed to like it as well. I think it's quite a tough job to introduce this world and so many characters to an audience who may never have seen the series. Still the movie seems to do all this and more, with entertainment value that is missing in many other sci-fi films of late.

However, I actually think this whole concept works better as a TV series, rather than a series of movies. So, now I join the ranks who are hoping someone will bring back the TV show in some incarnation.

More non-emulation news :)

I have still been up to my neck in "real work". I hope it will slowdown in the next month or so. When I do get a few minutes - I am trying to read, and maybe catch up on TV a little.

I'm carving out enough time to finish Neal Stephenson's "Baroque Cycle." I find these books to be amazing. Exciting, intellectually challenging, but very rewarding. I feel like I've actually visited the late 17th and early 18th century. And Neal's themes about science, technology, commerce, etc. are quite intriguing.

As I side note, I TiVo'd the whole "Firefly" series, which I'd like to watch before I go see "Serenity". I haven't heard anything but good things about the movie.