Thought, “Compressed Sensing” and the maths behind Occam’s razor

“Praise be to heros neptune, the titanic sails at dawn, everybody’s shouting.. which side are you on.” BD

So I’ve been wowed once again by Wired magazine, which seems to have summed up some recent conversations with quite delicious serendipity.

This post relates to both thinking styles and to a new branch of exciting mathematics called “compressed sensing”.

Firstly let me ask you; did you ever do any advanced mathematics. If so (and I did a bit), you’ll remember the stage where you could always work through the problems from first principles. Then, BAM! it all stops working… you find that the only way to solve problems is to “somehow guess” the form of the answer, and then show that by working backwards, this answer fits the problem. (complex differentiation/integration).

This may seem geeky, so let’s come back down to earth. Some people have the skill to solve problems by thinking through situations from first principles; with the rules and the facts available. Some do it quickly and some slowly – an analytical approach – lets call it bottom up or “end state first”.  All very sensible. Others (and I confess I’m one) find this hard and take an approach which is best described as “guessing” the end state or answer, and then seeing if it fits all the facts available. If there’s no fit, throw the guess away and guess again (guesses are cheap after-all) and see if this fits all the facts. Lets call this top down or perhaps “end-state first”.

Both approaches are quite fine and just a matter of style. However, in a situations where there are too few facts or rules to allow us to use a “start to finish” approach, i.e situations where one has a sparsely populated data set – the “end-state first” approach is helpful. This occurs very frequently – indeed as seed investors, we’re faced with this situation very frequently.

Now, lets take Wired magazine’s article on Compressed Sensing. Here, a bunch of researchers have managed to deal with sparse data in a quite magical way. They have managed to reduce MRI scanner times by factors of 100x, and increase apparent photo resolution by 100x similarly etc etc. The break-through logic goes something like this. Imagine that instead of a nice high resolution photo, I have a lower resolution set of randomly spaced pixels. Now take some clever maths “l₁ minimization” that “guesses” “end-state first” at a set of coloured blocks that fit amongst the random pixels, in such a way as to “match” the random pixels and make them fit into a pattern. Green dots must be in green blocks and yellow in yellow of course. Magic and maths then ensue – and it turns out that if you have enough random pixels – it’s mathematically very unlikely that the “block guess answer” is going to be incorrect – and just as magically, researchers are finding that they can “decompress” sparse data into amazing results. “It’s as though you can give me the first 3 didgits of a 10 digit bank account number and I can use these to guess the next seven!” quotes Emmanuel Candes. This is quite simply Occam’s razor instantiated in mathematics.

This stuff is for real – already the military are using it to use sparse enemy signal capture to decompress into full data….

What’s going on? How cab this be true? We all know that we cannot “guess the last seven digits” of an account code if given the first three unless there is a pattern. Yet we often spot patterns around us based on very limited data – Blink (Malcolm Gladwell) is surely about this if about anything. Blink’s premise is that humans have not only developed an analytical side to their brains but also an intuitive fast responding judgment pattern recognising side. It’s this that is at issue here. Thinking without thinking, working with seemingly too little data.

So what’s the point. Well, machines are being systematically taught to pull patterns from limited data in ever more magical ways. My fear is that in climates of uncertainty, and in a world that is changing so rapidly, where old data is wrong data; humans are tempted to reach for ever increasing amounts of data and proof, and are thereby increasingly going to fail. All to often, large quantities of data and proof is just not present until “it’s too late”. The moment will have passed by the time we have collected it – so I’m with Gladwell – Humans need to practice and harness their “compressed sensing” skills in line with the machines.

A serious point – anyone in the UK working on such maths and its application – or anyone who knows of anyone – please get in touch – I’d love to talk, I’d love to find applications and I’d love to fund.