Compressed Sensing: Why does Rice Play Texas or How is CS a disruptive technology ? Part I

For those of you who do not know much about Texas, the question "Why does Rice Play Texas ?" was rhetorically asked by the late President John F.  Kennedy at the Rice University Stadium in the famous Moon speech:

.. Why, 35 years ago, fly the Atlantic? Why does Rice play Texas? We choose to go to the moon. We choose to go to the moon in this decade and do the other things, not because they are easy, but because they are hard, because that goal will serve to organize and measure the best of our energies and skills, because that challenge is one that we are willing to accept, one we are unwilling to postpone, and one which we intend to win, and the others, too. It is for these reasons that I regard the decision last year to shift our efforts in space from low to high gear as among the most important decisions that will be made during my incumbency in the Office of the Presidency... But if I were to say, my fellow citizens, that we shall send to the moon, 240,000 miles away from the control station in Houston, ... to an unknown celestial body, and then return it safely to earth, reentering the atmosphere at speeds of over 25,000 miles per hour, causing heat about half that of the temperature of the sun--almost as hot as it is here today--and do all this, and do it right, and do it first before this decade is out, then we must be bold."

The more complete question should be "Why does the Rice University football team plays the University of Texas team when the odds are so much in favor of the University of Texas ?". In effect, Rice University (located in Houston) always has had a much weaker (american) football team compared to the rival team at University of Texas (located in Austin). In short, this "Why does Rice Play Texas ?" is reminiscent of "Why does David Fight Goliath ?". To most foreigners, the sentence sounds weird because the word "university" has been removed. 

View Larger Map

The parallel between this speech on space exploration and a disruptive technology like Compressed Sensing here is apt (let us note that Rice is now the center of a new technology: The one-pixel camera) The big idea that gets the most press is how the single camera works but it is interesting to see that it takes some amount of explaining to see the real difference between a normal camera and the Rice one pixel camera. In effect, as I mentioned previously, the real difference between Rice's camera and a normal camera is the number of samples the device takes ( the Rice camera could be run in a normal raster mode exactly as a normal camera). The Rice camera is a breakthrough not because of the way it is designed but rather because of the lower number of samples required to achieve the same quality of image as a normal camera. 

And so the question arising about the blurriness of the reconstructed images from the CS camera are justified (posted by rif in the comment section of this entry). I asked the question directly to Rich Baraniuk and Justin Romberg:

Do you have any good feel as to why the TV reconstruction of the images featured in this webpage and attendant publications, is still blurry with 40 % of the coefficients specifically for the mug and the soccer ball?

My current guesses are as follow:

• the camera is obtaining compressed measurements of a 3-d object but you use a dictionary of 2d functions for the reconstruction ?
• the pseudo-random family used for the projection is not optimally incoherent with the Haar wavelets as opposed to, say, noiselets ?
• exposure time is limited between different mirror configurations ?

Justin first responded :

1) The optical experiments the Rice team is running right now are probably "low resolution" in the following way. If they took many measurements (say 10s of thousands in order to reconstruct the 4096 pixel image) and then just reconstructed using least-squares (in effect averaging together a bunch of noisy, fully sampled observations) , the final image would still probably be a bit blurry. I don't know if they've tried this; I'll let Kevin and Rich comment.

2) I am not sure what values of epsilon they used in the recovery program min TV(x) s.t. ||Ax - y||_2 <= epsilon But if this value was more than something like 1-5% of ||y||_2, the TV recovery would start to get blurry even from "perfect" measurements.

Rich then responded by saying:

the reason for the blurriness is most likely due to misalignment of the optics; ie: even if we put a regular CCD array where our DMD was located the result would be blurry.

your guesses are good ones, but i'm not so sure they could have caused this issue. but we'll keep pondering them.

This is good to see that a better understanding of the issue is addressed by the folks involved in that research and the hope is to eventually obtain non-blurry images for less than the 40% coefficients currently being used. But as we can see, that technology has to find a good area where it is the only one to flourish in order to become one of these disruptive technologies of the future. The formidable opponent that is the current CMOS cameras sold at your high tech store near you has to have a shortfall that only Compressed Sensing can address.

In order to give oneself some guidance, let us look at the definition of disruptive technologies as viewed by Todd Proebsting when he was giving a talk on innovation in programming languages.

A “disruptive” technology

Disadvantage in primary market

Advantage in secondary market

Sold in small, low-margin market

Established companies concentrate and innovate on primary market; ignore secondary

Timely improvements lessen disruptive technology’s liabilities, increasing markets, market share, margins, etc.

A “disruptive” language safe, GC’ed interpreters

Disadvantage SLOW

Advantage Rapid Application Develop

Sold in small, low-margin market web developers, ISV’s

(established competitor ignored market)

Established companies concentrate on primary differentiator SPEED

Timely improvements lessen disruptive technology’s liabilities, increasing markets, market share, margins, etc.

Moore’s Law (for free!)

RAD enhancements

My criteria: technology must

Have disadvantages: Be mostly ignored by recent PLDI and POPL conferences

Alleviate real problems…"What does it do?"

For each candidate technology: 2 slides

• Opportunity what’s the issue?
• Current solutions what’s done now
• Proposal: New disruptive technology
  
• Disadvantages why some (many?) will scoff
• Unmet needs benefits to adopters

What are the 2 slides for Compressed Sensing ?