Also, this (again, from the article) is just bizarre:
"At present, most of our audiovisual info is stored in sophisticated compression formats. If, or when, the format becomes obsolete, you’ve got a painful conversion project on your hands. But in the CS future, Candès believes, we’ll record just 20 percent of the pixels in certain images, like expensive-to-capture infrared shots of astronomical phenomena. Because we’re recording so much less data to begin with, there will be no need to compress. And instead of steadily improving compression algorithms, we’ll have steadily improving decompression algorithms that reconstruct the original image more and more faithfully from the stored data."
Someone, Candès or the author, doesn't seem to understand what they're talking about.
Because what they are describing is compression, I mean its even called compressed sensing. I'm guessing that somewhere lost in the journalism is the suggestion that its better to place more computation on the decompression, which might be true in some application.
It seems like a great bit of technology, I don't think the author needed to sex it up with mention of compressing images. The applications where its actually hard to do sensing at all (like the MRI example in the article) are much more compelling. It seems like its main use seems to be in turning sparse data into its most human friendly form, but I do wonder about making clinical decisions based on such an aggressive interpolation rather than actual data.
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.
You can't generate information from nothing. Compression based on sparsity seems to be making assumptions about the level of detail in a picture[1]. If you stored 20% of the pixels in Obama's face you may miss a spot of acne.
I can't imagine trusting to this technique for pictures of the galaxy. After spending a bazillion dollars on a space telescope we aren't going to "throw away 80% of the pixels".
[1] - I'm not certain of this deduction. Can somebody with more background confirm or deny?
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.
"more impressive astronomer porn at five times the resolution!"
As long as we keep in mind that the filled in regions of space or background match the assumed entropy, I think it's worth doing. The applications of L1 appear to be limited to cases where the structure and assumptions match the dataset.
Maybe there's an underlying pattern we're recreating? Something inherent to physical laws, fractal replication, etc.
Your comment helped me to see that L1 isn't just a matter of interpolation but an assumed underlying pattern that is used to fill in or estimate the unknown data. Thanks.
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.
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.
This is more of a case where you aren't actually using all the information-bearing capacity of your pixels but are actually sampling from a much lower dimensional manifold. This isn't just interpolation and information need not be lost.
"At present, most of our audiovisual info is stored in sophisticated compression formats. If, or when, the format becomes obsolete, you’ve got a painful conversion project on your hands. But in the CS future, Candès believes, we’ll record just 20 percent of the pixels in certain images, like expensive-to-capture infrared shots of astronomical phenomena. Because we’re recording so much less data to begin with, there will be no need to compress. And instead of steadily improving compression algorithms, we’ll have steadily improving decompression algorithms that reconstruct the original image more and more faithfully from the stored data."
Someone, Candès or the author, doesn't seem to understand what they're talking about.