Tuesday, August 30, 2011

The Compressive Sensing Handle

What are the connection between the different problems of finding a defective coin or coins within a large set of known non defective ones when there is:
It could be coins, precious rings or balls, they all ask the same question. How do you assemble some measurement process in order to recover an ugly duckling ? More important, all these riddles are a handle: The story reminds you

  • that the act of finding a defective coin is not as important as how you find it, 
  • that compressive sensing that can be made simple to describe and eventually map to a large set of fields.

Why is that important ? Being familiar with a particular problem sometimes hinders your ability to identify the big picture. You may have worked for years in coded aperture yet cannot make a clear connection between that and fertilizers and crops. You may know certain techniques with no firm theoretical grounding yet when you hear about compressive sensing, you know and find that there is indeed a connection. The handle acts as a Rosetta stone. One breakthrough in one field immediately translate into many other fields. Empirical methods that work all the time cannot remain empirical. Should you wait for this theoretical underpinning to come to fruition before you can publish ? No worry, the filter bubble of peer review make that decision for you

At a different level, one can also ask whether Marcel Kolodziejczyk's solution to the balance puzzle provides a new insight for better or faster sparse signal recovery solvers used in compressive sensing and other fields ? Maybe. Can one map the coin problem into a Sudoku problem ? it would be a interesting path.

What are the handles for the different matrix factorization techniques, structured sparsity norms that are springing up left and right ?

Two courses are offered this fall on compressive sensing and beyond that might help in developing this insight:

P.S:  Marcel worked out the 40 coin problem with four weightings, I didn't know somebody had done that.
P.P. S.: A recent entry on the connection between compressive sensing and group testing.
P.P.P.S: Terry Tao uses the same handle.

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from

No comments: