Simple Metaphor About Compressed Sensing

post by ryan_b · 2018-07-17T15:47:17.909Z · LW · GW · 0 comments

Contents

No comments

Summary: Compressed Sensing is a subject I encountered in undergrad and thought was cool, but was far beyond my math ability. I return to it occasionally, and this is a metaphor I have developed to test my understanding.

Suppose you walked home from work every evening and passed a windowed office building without a sign or even a door. You change your route every day so as to view all sides of the building, and notice only that a different number of office windows are lit on each side. Eventually you determine to solve the mystery, and decide to peek into the windows directly. Which side of the building should you choose to look into?

We are accustomed to the idea that more information is better, so a natural answer would be "the side with the most windows lit." In the first window you see someone doing payroll - but all office buildings have people doing payroll. In the second window you see someone cleaning the floor - but all office buildings get cleaned. In the third window you see someone doing HR work - but all office buildings have people doing HR. These three windows effectively tell us nothing.

Suppose instead we chose the side of the building with the fewest windows lit. Then you might go up to the lone lit window and see schematics and models in the office. Aha! They make widgets.

And now suppose you wanted to tell all this to a friend. You could recount the whole story: walking around each side of the building; checking each window and what you found there. Or, you could just say in that building, they make widgets. This is much shorter, and more importantly has all the same information. This is because your friend already knows that all office buildings have people who do payroll, and cleaning, and HR in them; he can reconstruct those parts of the story himself.

In this metaphor what they do in the office is the signal of interest, the sides of the building are the domains of the signal, and the number of lit windows are the sparsity of the signal. I don't really understand the incoherence condition, so I'm not sure this story even gestures at it. Telling your friend is the application bit. For informed reading, see Terry Tao's blog.

0 comments

Comments sorted by top scores.