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 -

vfuncs on google code – with discrete filter

Just a note that Ive uploaded the initial version of vfuncs to google code. Ive released under a BSD license so you can use it in your commercial and noncommercial code easily.

Download from here [I'll import to SVN sometime soon]. See my previous post for a description of vfuncs.

This version contains an example of a digital filter. This can be used to smooth the series data, or apply other signal processing operations. If your familiar with applying a blur filter in photoshop or gimp, using a gaussian filter kernel, this is exactly the same idea (except in one dimension).  Gaussian filter is basically just a moving average of the data.

Think of the algorithm as applying a sliding window across the data – the sliding window contains the filter weights, and at each position you apply the weighted average [dot product] of the filter weights against each data point in the window.

If the filter contains a single element of weight 1.0, then the result is just the input (the filter is just the Dirac delta function in that case). If the filter contains [0.25 0.50 0.25] its going to mix each element with its neigbours and take a weighted average, thus smoothing the data.

Cornucopia of Math

Eclectic recent math-goodness :

Two nice video talks by Terry Tao on Random Matrices and Additive Combinatorics here

A programmers intro to the practical aspects of Flow Graphs at topcoder algorithm tutorials

PCM

Last but not least the superb ‘Princeton Companion to Mathematics‘.

In a nutshell, PCM is a readable survey-guide to modern math by the experts.  Some links -

• The intro page autoplays a podcast interview with Tim Gowers, the editor
• Contents list with some downloadable sample chaptes
  
• Terry Taos many PCM contributions are discussed/previewed at his blog
• ‘Mathematics and Money’ chapter apparently has an intro to Quantitative Finance by Mark Joshi
• ‘Numerical Analysis’ sample chapter mentions John Butcher, a great ex prof from Auckland Uni.

Should be in print Nov 2008.  Hopefully more articles from Tim Gowers’ and Terry Tao’s blogs will make it out in book form, with the momentum this will generate…

Math Journals – to be or not to be?

Found a great entry on Terry Taos blog : a guide to strengthening math inequalities, with examples and tricks, entitled “Amplification, Arbitrage and the Tensor Power trick”.

At the end of that article the comments digress towards the relevance of Math Journals, and this is taken up in a linked blog entry – “more on Journals“

I repeat here the comment I made on that blog, namely -