Thursday, December 29, 2011

Compressed Sensing : An Overview #1

We shall try to get an analogy to the problem "Compressed Sensing"  through a few analogous example.

There are N buckets of gold coins where each of the coins weigh 2 grams except for a bucket which weighs 8 grams. The problem is to identify that particular bucket.

Approaching the Nyquist would be to weigh the coins from each bucket also called the point wise sampling. Otherwise we can number each bucket and accordingly take the coins with respect to the number of the buckets. Bucket 1 would give 1 coin and bucket 2 would give 2 coins up to n coins from bucket number n. 

Thus a total of 10 buckets would give us 55 coins. If all the coins were of 2 grams the total weight would be 110 grams. But if x is the actual weight the defective bucket would be (110-x)/(2-1.8). Thus just one measurement and the bucket number is retrieved. There is a critical assumption made to achieve the solution which is we have only one defective bucket. In fact this is the term 'Sparsity Prior'. Thus a linear measurement server the purpose. One information to retrieve thus a linear combination. More information would call for different linear combinations. This in fact is what is called as Group Testing

No comments:

Post a Comment