Suppose a bag contains 100 marbles, each with mass 10 grams, except for one defective off-mass marble. Given an accurate electronic balance that can accommodate anywhere from one to 100 marbles at a time, how would you find the defective marble with the fewest number of weighings? You may well have thought about this kind of problem before and know the answer. But what if there are two bad marbles, each of unknown mass? Or three or more? An efficient scheme isn't so easy to figure out now, is it? Is there a strategy that's both efficient and generalizable?
The answer is "yes," at least if the number of defective marbles is
sufficiently small. Surprisingly, the procedure involves a strong
dose of randomness. It's a nice example of a new and very active
research area called "compressed sensing" (CS), that spans
mathematics, signal processing, statistics, and computer science, and
has many surprising applications. In this talk I'll explain the
central ideas, which require nothing more than straightforward linear
algebra and a bit of probability. I'll then show some applications,
including how one can use this to build a high-resolution one-pixel
camera!
Pizza will be served.