I think Candes (and/or the journalist) is contrasting sampling in an incoherent basis with the conventional route of compression (sample the full signal/image/whatever, then try to reduce its size). The former is a form of compression, just not the kind we usually do.

Isn't this a case where entropy shows it isn't possible? Once you degrade the quality/quantity of the information, you can't get it back. You can find a clever way to hide what you did, but this doesn't add information, you're just interpolating. This isn't bad however, as we normally don't use all data we could (do you look at your pictures with 400% zoom factor?), and a rescaled image can highlight some detail you would have missed.

By the way, those bazillion dollars aren't wasted, because if you take the image, don't throw away pixels, but do as if it were a bigger image which had lost pixels, you can get something useful out of it.

The article focuses on "missing pixels" which doesn't have much to do with the original Candes paper. The usual setup for compressed sensing is that you're sampling the entire image one coefficient at a time in some "incoherent" basis (ie, noiselets). Thus, every little spot of Obama's acne may very well be reconstructed-- though more generally you're right, if the image is too sharp then something gets lost.

You're not exactly making assumptions about the level of detail. You're making assumptions about the compressibility and entropy of the data. A circle requires the same amount of data to represent whether its radius is R or 2R[1]. L1-minimization tries to find the smallest number of circles regardless of size, whereas traditional compression methods look for the largest circles regardless of number. It attempts to minimize the entropy of the result image (roughly), and all real pictures that aren't literally static have low entropy.

A saw a presentation on this technique in college. Some of the details I saw escaped me, but one thing I remember is that the L1 decompression is optimal when it is "orthogonal" to the compression that it is reversing. Fourier-based compression schemes (including JPEG and MPEG, and even MP3) are "orthogonal" in the correct sense because they select based on size, preserving large structures better. Random sampling is "orthogonal" to basically all compression schemes, and tends to select more information from large structures as well.

With a high-res bazilion-dollar space telescope, you're not going to throw away 80% of the pixels and reconstruct an approximation. Rather, you'll take all of the recorded pixels, and then reconstruct even more impressive astronomer porn at five times the resolution!

[1] Well, close enough. If you store the circle as the (x,y) of the center and an integer radius R, then 2R takes 1 more bit. Storing R as floating-point means no difference. I don't know about other representations. Anyways, the point is, the image size of the feature is not strongly coupled to data size of the feature.