Adding Circles – Javascript animation of Fourier Series

I get a few hits for the Animated Sine demo in Javascript – maybe this is a good way to introduce young people to math?

Here is a minor update I did a while ago that shows what happens when a second circle spins around the point on the outside of the first circle…

[click the pic or here to view the animation ]

This might be a nice lead into Fourier Series…

jsxGraph Epicyclic calligraphy – spirograph on steroids

Some amazing javascript libraries are coming out now, which enable interactive math directly in the browser.

One of the most impressive is jsxGraph, from Bayreuth University, which is purpose built upon SVG for plotting mathematical functions.  See their wiki for superb demos.

On the jsxGraph blog, there is a video showing a construction being manipulated by touch on the iPhone – very cool.

Experimenting with their circles-on-circles web app, by sliding the parameters around I uncovered this delightful piece, which reminded me of those ornate calligraphy end-notes you see in olde books.

Its a lot of fun to experiment.  For the curious, the parameters of this specimen are : c1:0.51 f1:7 c2:0.32 f2:17

SVG coolness

I think SVG is the right way to go, and a more natural approach than using canvas [as I did for my interactive sine generator last week].

There’s no technical reason now why something as featured as GeoGebra or KGeo could not be implemented directly in the browser.. it just has to be done!

Geogebra is really nice, but I do prefer the simplicity of not having to download the java applet and approve it for access.  Each extra step supposedly halves the audience, and I want math to be interactive and accessible.

An easy Putnam problem : areas in a stretched circle

I’ve been thoroughly enjoying Paul Zeitz’s book “The Art and Craft of Problem Solving“.

One of the early problems in the book is from 1994 Putnam math competition, but surprisingly easy once you see that it can be scaled into a much simpler question.

The problem :

Find the positive value of m such that the area enclosed by the ellipse x^2/9 + y^2=1, the x-axis, and the line y=2x/3 is equal to the area in the first quadrant enclosed by the ellipse x^2/9 + y^2=1, the y-axis, and the line y=mx.

Heres a drawing of the areas mentioned using GeoGebra, with each area in separate quadrants for comparison, with an approximate area.  The Qn asks what is the slope of the line through point F [or -ve slope of line through Q here].

Problem as stated, with areas colored

Well its a bit hard to pick the point Q [ the slope -m ] so that these colored regions have the same area…

… but then you realize that the whole problem becomes easy if you simply scale the ellipse back to the unit circle.

To do this, x is scaled back by 3x, so areas become 1/3 of what they were [y remains the same].  So the problem now looks like this :

“]

scaled back to the unit circle : areas are x 1/3, slopes x 3

So the line that gives the same area is y=x/2.  When this is scaled back to the original ellipse, the slope gets divided by 3;  so the line we want is y=x/6.

Quite surprised to see this in a Putnam, but it does show a really common motif in math, namely :

Transform to a simpler domain, solve it there, then transform the solution back.

The astute reader will have noticed that I cheated : the areas of the colored regions in the top picture are of course ~1.65 or 3 x area of regions in the second diagram.

The areas marked were calculated by rough approximation with a polygon and the GeoGebra area function. [  The ellipse itself was drawn to fit using foci - I wasn't sure how to edit the formula in GeoGebra to make it exact. ]

More fun with a two-circle sine generator

I’ve added a secondary ‘slave’ circle, which I think introduces the idea of Fourier series in a natural way.

The animation starts as before with a sine curve,  then you can add in the second circle by clicking ‘toggle’.

Click this picture to see the Javascript web animation :

Animated sine wave in Javascript HTML5

I wanted to explain the math-magic of the circle generating the sine wave with a simple animation of a point rotating on the edge and the height matching the sine wave.

I had a look around but most of the math animations are Java applets which I find a bit top heavy, and this should be doable in Javascript.

This is what I came up with, [click to view animation] -

I tried several approaches to get this working, not perfectly happy with any of them, although I did get a basic demo up and running as you see above.

First approach was using SVG, but for some reason I had problems getting svg to appear at all in an html5 page… go figure, this should be simple.   In the process I was impressed by SVGEdit which is an early stage, usable if not polished, in browser SVG editor. cool.. I just couldnt get any of my pages to show svg.  Ill have another go when the frustration has been forgotten, its possibly some syntax glitch I missed.

I then tried RaphaelJS library which did work reasonably well.  Its a nice api.  Some things like animating along a path you get out of the box, which is nice.  After some basic success I did find myself scratching my head on how to rotate a path – and I’m not sure how to apply a rotate transformation to an item generally [which is a cool feature of SVG ].

Partial demo of sine wave animation implemented in Raphael here.  Animates quickly in Safari on mac, Chrome on mac, slightly choppy on Firefox on mac, and quite slow but functional on Safari iPod/webkit.

Wanting a bit more control over exact placement, I decided to try pure HTML5 Canvas rendering.  This worked well, was simpler to understand exact x,y pixel placement.  I haven’t solved a side issue which is that for some reason if I have the preferred HTML5 “<DOCTYPE html>” tag it ignores exact placement of div elements.. finding this side effect drove me nuts!   Im wondering if this is in the spec, it seems it would break a lot of code.

Anyway, layout of the animation was easy in HTML5 canvas.  See sine animation demo here.

It does seem to be busy drawing, and Id like to eliminate back flicker [which you'd normally do by drawing to back buffer, or having dirty regions].  Performs ok on desktop safari, firefox and chrome [which seems fastest of all the browsers].  Comes up on iPhone but animates slowly as you’d expect.

A faster approach might be to render the background into a separate layer and draw the dots and lines per frame, as its probably touching only 1 in 1000 of the total pixels.

Anyway, seems to be a promising way to get Math animations up and running, which fine tuning will improve.  See page source for Javascript, BSD licence, feel free to reuse.

Matching Buyers & Sellers – solving NxN problem with chaos

Been reading a bit about gaussian processes and machine learning…

For a slightly related problem of matching Buyers with Sellers or matching a large number of people on a dating site, the brute force method would make NxN comparisons.  You have N points [seller/buyer or date-seeker etc] with d attributes such as age, sex,  weight, height, income location, interests, preferences… or price, quantity, product, location, expiry etc – these define the dimensions of the space in which N belongs.

If your data was 1 dimensional, each item having only one attribute such as price or age, youd simply sort on that and do the match in a greedy fashion, complexity roughly O(NlogN).

In many problems d=5 or so [in biotech micro-assay arrays where there are thousands of gene probes, d could be as large as 60k] which means that the volume of the space grows incredibly large – if you partition the space in K parts over each dimension thats K^d subvolumes to match to each other which gets huge very quickly.

There are normally continuity assumptions – if you take samples, you can get some predictive value from them.  A sample tells us something about nearby points, and this is really the basis of machine learning.  Another aspect of this is a theorem from compressed sensing and random matricies, that Terry Tao and others have proven, which says something along the lines that in high dimensions, random samples will actually be very effective in exploring the higher dimensional space.  This could explain why evolution is so universally effective in finding ultra optimised solutions, and overcoming local maxima.

Back to the case of finding best matches of N points in a d dimensional domain.  Lets assume we have some probably nonlinear function f = fitness(P1, P2) given any two points.  One approach would be to take a smaller random sample from the N points, small enough that we can do brute force comparing each sample against each other.  Then we sort on f and pick the best ones.  This gives us a lot of information about the space… because for any P1, P2 that match well, there will be surrounding points that also match well, in all likelihood.

So using this geometric way of looking at the problem of finding best matches, I implemented a simple prototype in Python which does the following -

• Take S sample pairs P1, P2 and eveluate f12 = fitness(P1,P2)
• Sort on f12, and take the best matches
• Make a small volume V1 around P1, V2 around P2
• Take the best matches from all points Pa in Va and Pb in V2
• Brute force any remaining points
• Post-process by swapping P1 of one pair with P2 of another pair

The results were not as good as I hoped but there are lots of improvements to make.  I measured the total number of times the fitness() function is called, as the complexity, and found that for N<~200 brute force is more effective.  Brute force on 1000 takes a long time to compute.   This sampling pairs method gets results in roughly NlogN it seems, runs on samples 5 to 10k in size, seems roughly NlogN.  This initial implementation when compared against brute force gave around 80% of the maximum possible global fitness score, when compared to brute force.

So its promising and Ill play with it and see if it can be improved in practical ways.  One of the nice things about it is the fitness function can be very nonlinear, so that the hotspots of high fitness volumes are not something that you can hard code a routine for… but random sampling finds these very well, and requires no special handling.

I used a naive approach to post processing – improving the match by swapping randomly chosen pair elements, and keeping the swap if it results in a better match.  This is basically a simple form of genetic optimisation or simulated annealing, so its pretty inefficient as a first implementation.

Interesting

computing kth moments – performance comparisons

My previous blog articles describe approaches to calculating kth moments in a single pass – see compute kth central moments in one pass and variance of a sequence in one pass.

I decided to make a rough performance comparison between my approach and boost accumulators api.  A reasonable test is to procedurally generate 10^7 random numbers in range [0.0..1.0] as the input data.  We compare 3 algorithms -

• No moments accumulated – baseline, just generates the input
• Accumulate all 12th order moments using Boost Accumulators
• Accumulate all 12th order moments using my vfuncs cpp code

We run on Linux using time command to get rough timings, raw results are -

• Baseline   -   1.16s
• Boost Acc – 23.16s
• Vfunc Acc -  2.44s

If we subtract the baseline we get a rough comparison of Boost ~ 22s and Vfuncs cpp ~1.3s when the cost of generating the input is factored out.

So the vfuncs impl is roughly an order of magnitude faster then the current v1.37.0 boost accumulate stats implementation (both are single pass).

I don’t think the boost algorithm is logically different, its probably more a case of template code complexity having an impact – the 10s compile times might indicate this also.  Executable size also reflects this, differing by an order of magnitude.

(Note : Using gcc 4.2.4.  I haven’t tried this on other compilers, build settings etc – they could have a profound effect.  Let me know if you see different results on eg. Intel or VC compilers)

Download

Download code and project – kth_moments.tgz – from vfuncs google code downloads page.  [BSD license feel free to use]

compressed sensing links

Some links while I have them at hand…

Compressed sensing basically gives a better practical way of recovering a signal from its samples than the Shannon Sampling theorem suggests – given some structure on the data.

Recent methods using L1 norm, as a compromise between L2 and L0, mean this is much more computationally feasible. New work by Tao, Candes etc gives some proofs on why this sparse sampling works so well.

Useful compressed sensing links -

• Introduction to Compressive Sampling – IEEE magazine article – PDF- Candes
• Terence Taos blog articles on CS
• L1 magic
• Compressed Sensing videos
• Talks at U Minnesota

compute kth central moments in one pass

Continuing on the same topic as my previous post, its nice to be able to gather all the kth order moments in a single pass.

Last time I mentioned the boost/accumulators example, but you will have noticed two issues if you use that.  Firstly, moment<k> tag will give you the kth simple moment relative to zero, whereas we often want the kth central moment of a sequence relative to the mean.  Secondly, although boosts accumulator is well written it does seem to take a while to compile [~ 12 seconds for code using moment<12>].

After some playing around Ive got a faster simpler approach, where the inner loop accumulates kth powers of the element.  After you’ve run the sequence through, you can then easily extract variance, and all the kth central moments.  So in adding the more general case of kth moments, Ive made the particular variance case simpler.  That often seems to happen in programming and math!

algebra

First a bit of math and then the code.  We want to express the kth central moment in terms of the k basic moments.

First, lets define the basic moment as -

We rearrange the binomial expansion -

So we have the kth central moment given as a weighted sum of the kth simple moments -

which shows that all we need to accumulate as we walk across the sequence is the kth simple powers .

Notice the variance is now handled as a special case where k=2.  Likewise k=0 corresponds to n, the element count and k=1 is the sum of elements.

c++ impl

Heres a basic impl of the above expression -

variance of a sequence in one pass

Rearranging

I was chatting with some other quant developers the other day, as you do, and the issue came up of calculating variances.  Its a pretty common operation, and the naive approach does two passes, one to calculate the mean, , and one to gather the squares of differences from that. … but someone asked if it could be done in one pass, and of course it can, quite easily.

Recall, the population variance of a sequence is defined as -

We can expand this and see how the variance after n terms differs from the variance after m=n+1 terms, vis -

and we have in terms of vis -

In other words , so theres very little we need to store to accumulate the variance as we traverse the sequence.

C++ Implementation

Expressing this in C++ code we’d have a functor that maintains state and gets handed each element of the sequence, in simplest form -