It is not at all obvious how compressive sensing works! Even if you have a background in signal processing or linear algebra. Most people approach linear algebra to solve over-determined systems of equations, not under-determined systems. But it turns out you can validly pose the problem if you have some a priori knowledge of the structure of your signal.

Actually, the camera uses a single pixel, not a single bit. The measurements from pixel are from a 16-bit ADC so we get pretty good grayscale information. There are some single bit compressive sensing implementations, often used for radar where the SNR is low.

There's even a startup that is building commercial implementations of single pixel cameras. We work with the Rice researchers you linked to. http://www.inviewcorp.com/