Slashdot Mirror
Recovering Data From Noise
An anonymous reader tips an account up at Wired of a hot new field of mathematics and applied algorithm research called "compressed sensing" that takes advantage of the mathematical concept of sparsity to recreate images or other datasets from noisy, incomplete inputs. "[The inventor of CS, Emmanuel] Candès can envision a long list of applications based on what he and his colleagues have accomplished. He sees, for example, a future in which the technique is used in more than MRI machines. Digital cameras, he explains, gather huge amounts of information and then compress the images. But compression, at least if CS is available, is a gigantic waste. If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? ... The ability to gather meaningful data from tiny samples of information is also enticing to the military."
Enhance!
Because it's hard to know what is needed and what isn't to produce a photograph that still looks good to a human, and pushing that computing power down to the camera sensors where power is more limited than a computer is unlikely to save either time or power.
to just subscribe to Cinemax instead of going through all this trouble to de-scramble the pr0n?
If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? ..
That's what a digital camera is about, isn't it?
Nae king! Nae laird! Nae yurrupiean pressedent! We willna be fooled again!
The algorithm then begins to modify the picture in stages by laying colored shapes over the randomly selected image. The goal is to seek what’s called sparsity, a measure of image simplicity.
The thing is in a medical image couldn't that actually remove a small growth or lesion? I know the article says:
That image isn’t absolutely guaranteed to be the sparsest one or the exact image you were trying to reconstruct, but Candès and Tao have shown mathematically that the chance of its being wrong is infinitesimally small.
but how often do analysis like this make assumptions about the data, like you are unlikely to get a small disruption in a regular shape and if you do it is not significant.
on the bright side, when Moore's law allows real-time processing we can look forward to night vision cameras which really are "as good as daylight", and for this sort of application the odd distortion really won't matter so much.
fgr ts ot no bch!
The military probably wants the ability to send/receive without revealing the data or the location of its source to the enemy. For example, its nuclear subs need to surface in order to communicate, and they don't want the enemy to be able to use triangulation to pinpoint the location of the subs. So, they make the data they're transmitting appear as noise. That way if the enemy happens to be listening on that frequency, they don't detect anything.
Digital photography - compensate for noisy sensors.
Code breaking
Code making
telecommunications
video compression
I see some really interesting products coming down the line.
I seriously doubt that the Obama demo image is real. There is no way that the teeth and the little badge on his jacket are produced, and that no visual artifacts were created.
Exactly. This algorithm doesn't create absent data nor does it infer it, it just makes the uncertainties it has "nicer" than the usual smoothing.
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.
If the enemy uses this same technology against us, then the military wants to be able to recover as much information as they can.
It would be nice to have a GIMP plug-in for this.
Does this only apply to image data, or will we be able to use this to clean up other databases? Will it work with sampled sounds? Names and addresses and inventory?
More importantly, HOW does it work?
Sorry of TFA answers these questions, but I've never known Wired to get into any kind of detail on stuff like this.
Free Martian Whores!
So, if I feed this algorithm an image that actually IS noise, what do I get?
Pictures of angels?
When it comes to art photography, I for one would rather have a RAW image than a compressed one.
Why? What the camera takes is not my final output. I want to be able to choose what to manipulate and remove.
Now, for everyday snapshots, there might be something here. But as others pointed out, it might be less efficient to do the compression in the sensor than the way it's being done today.
As for other applications, time will tell.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
It is clear that in order for this to work it needs a "model" of the real world. In his simple case the model is "everything has smooth colours" which matches his test image really well. Trying to find an unexpected detail in a large image would be impossible with this model.
However if you have a good model of what you expect then it will probably find it. Much like voice compression is very efficient because we know what to expect, if you have a good model of what you expect it will reconstruct it from limited data.
From a legal point of view it is creating what you expect to find from nothing so it may have a tendency to find what you are expecting! So not much use in court where it just proves your assumptions.
The Medical Imaging has enough "artefacts" in the image as it is.
After applying the Noise filter to mess up my image I hit Undo and my image is back to normal.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
Did we really need to refer to it as CS in the summary? A quick glance of the summary could lead one to think that this guy is the inventor of Computer Science, rather than the correct Compressed Sensing... In the summary of an article that is concerned (in part) with maintaining information after compression, we lost quite a bit of information in abbreviating the name of his algorithm.
Damn_registrars has no butt-hole. Damn_registrars has no use for a butt-hole.
MOD PARENT UP for this: "This algorithm doesn't create absent data nor does it infer it, it just makes the uncertainties it has "nicer" than the usual smoothing."
Fraud alert: The title, "Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples" should have been "A better smoothing algorithm".
Enhance 34 to 36. Pan right and pull back. Stop. Enhance 34 to 46. Give me a hard copy right there.
It doesn't add information, it just fills in what you already expected to see.
Slashdot - News for Nerds, Stuff that Matters, in ISO-8859-1 Has just realised that beta makes this signature redundant
The description of the algorithm in the article is quite poor. To reconstruct an MR image you effectively model it with wavelet basis functions, subject to someconstraints: a) the wavelet domain should be as sparse as possible, b) the Fourier coefficients you actually acquired (MR is acquired in the Fourier domain, not the image domain) have to match and usually c) the image should be real. You often also require that the total variation of the image should be as low as possible as well.
Since the image is acquired in the Fourier domain, every measurement you make contains information about all the pixels in the image. For reasonable* under acquisitions CS can produce a perfectly reconstructed image.
* the exact limits of "reasonable" are still under investigation, but typically you only need to acquire about a quarter of the data to be pretty much guaranteed you'll be able to get a perfect reconstruction.
These are fancy words, for what is nothing else that automated educated guessing. (And re-vectorization.)
Yes, you can guess that a round shape is round, even when a couple of pixels are missing. But you can not guess that one of these missing pixels actually was a dent. So this mechanism here would still make that dent vanish. Just in a less-obvious way. (Which can be very bad, if that dent was critical.)
Essentially if you have a lossy process, you are always going to have a lack of details, and that’s not going to change.
Just that this process does to images when compared to e.g JPEG, what MP3 does to music when compared to analog recordings.
In analog recordings, loss is audible noise. In MP3 it’s the opposite. Usually mostly not audible, but still missing.
In JPEG, loss is visible artifacts. In this method it’s the opposite. Usually mostly not visible, but still missing.
Any sufficiently advanced intelligence is indistinguishable from stupidity.
Perhaps we want cameras that produce Fourier coefficients instead of images?
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
I could not find any examples showing similar image reconstructions on Jarvis Haupt or Robert Nowak's websites/publication histories -- the researchers credited with the Obama restoration photo.
Therefore, I am skeptical that this wired article is not to be trusted.
I wonder if this can somehow be extended to other forms of data scrubbing besides two-dimensional color images. I've got a waveform capture of a really small, and really noisy, electric motor current that I want scrubbed without losing the shape I think I'm supposed to get out of it.
(((dB)))
Here's how Compressed Sensing works with standard JPGs.
First the program takes the target JPG (which you want to be very large), and treats it as random noise. Simply a field of random zeros and ones. Then, within that vast field, the program selects a pattern or frequency to look for variations in the noise pattern.
The variations in the noise pattern act as a beacon - sort of a signal that the payload is coming. Common variations include mathematical pulses at predictable intervals - say something that would easily be recognizable by a 5th-grader, like say a pattern of prime numbers.
Then it searches for a second layer, nested within the main signal. Some bits are bits to tell how to interpret the other bits. Use a gray scale with standard interpolation. Rotate the second layer 90 degrees. Make sure there's a string break every 60 characters, and search for an auxiliary sideband channel. Make sure that the second layer is zoomed out sufficiently, and using a less popular protocol language; otherwise it won't be easily recognizable upon first glance.
Here's the magical part: It then finds a third layer. Sort of like in ancient times when parchment was in short supply people would write over old writing... it was called a palimpsest. Here you can uncompress over 10,000 "frames" of data, which can enhance a simple noise pattern to be a recognizable political figure.
Further details on this method can be found here.
--
Recycle when possible!
Why in the world would you use this in a medical image? That seems like quite the straw man.
You pr0n addicts should really get a grip on yourselves
..... oh wait!
RTFA!
"If it sees four adjacent green pixels, it may add a green rectangle there."
Which is brilliant...unless the tumor you were looking for is a white dot in the middle of those 4 pixels. Now it's all just a smooth green field.
It started off with pixels missing; when done the pixels are filled. How is that not creating absent data by inferring it?
Any algorithm that generates more data than was sent in is inferring. That's not to say it isn't useful, but if, for example, all of the pixels of the bile duct blockage (FTFA) were missing, the picture would have to have been reconstituted with no blockage. If the only three pixels in an area were discolored, then that whole area (or some significant portion of it) would be discolored.
The algorithm is very impressive, but when you fill in the blanks, that's pretty much the definition of creating absent data. (Barring examples like e.g. knowing three values of a degree 2 polynomial and inferring the whole polynomial, but in cases like those the data you have really is a complete description.)
I can finally stop reading the articles and the summaries, and apply this algorithm to the first post to understand the article instead. What a time saver!
"This post contains words, known to the State of California to cause thought. Wash brain thoroughly after reading."
Just in time to help decipher Valve's latest update...
http://www.rockpapershotgun.com/2010/03/02/portal-theres-something-going-on/
I've been working with digital images for a long time and I can tell you this: this is too good to be true
You can't get professional results even when trying to interpolate 5% extra data, and even though I guess this is not oriented to professional quality images, it will just make crappy images good enough to recognize the points of interest, it will be acceptable to that point but then there's the Obama sample, I have seen the printed image (in the dead tree version of the mag) and it certanly looks faked, there's some detail that couldn't have beeen retrieved, not with the current algorithms, actually as some have pointed out, the lapel pin data is not present at all so how could you recreate that, sounds to me like something more from the realm of magic than math, hence fake!
While I'm certainly no expect on this, it seems almost everyone here is being mislead by the word "noise". From what I gather, this is not cleaning up noise, it is filling in missing pieces in data whose samples are assumed to be noise-free. This is drastically different from "smoothing" that is intended to filter out noise.
So, in the case of a small growth or lesion, as long as there is at least one sample of it that is different from the surrounding area, the "sparsity" (this is my guess based on a quick reading of the article and some related ones) would result in an identifiable spot of some kind. This would be due to the fact that that the one pixel sample of the lesion is different from its closest available neighbors. This difference would be assumed by the algorithm to be an accurate representation of that pixel, not a random speck of noise. So, something would show up, say a small blob, that would be obviously different in the reconstructed image. Now the less pixels you have of this lesion, the less accurate the shape and size of that blob will be, but nonetheless it is something that would stand out and warrant further investigation.
i agree, the description of the algorithm is too vague to really understand what is going on.
30 seconds of googling turned up this brief lecture on compressed sensing. written for undergrads, "the prerequisites for understanding this lecture note material are linear algebra, basic optimization, and basic probability."
http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/baraniukCSlecture07.pdf
side note: rich baraniuk was one of the best professors i had in undergrad
From the referenced reports, it looks like people might get the wrong idea about the possible applications. This algorithm starts with discrete data points with gaps in-between, and works out the remaining arbitrary data points in a pleasing way, as if it were a continuous field (represented as a fourier transform, for example).
In other words, it works with data where the signal is already separated from the noise. My last sentence is crucial for an understanding of the possible applications: it will not infer elements that are absent in the measured signal, but will instead repeat elements that are already present. I expect this story will be mis-reported in future, by reporters who do not understand how it really works (and I might count myself in that, as I've only glanced at a couple of the arxiv papers).
Some of the designs for CS cameras basically do just that. You can do CS just as well with images acquired in the image domain though, the intuitive reasoning for why it works just gets a little... less intuitive.
I'm not sure CS is going to quickly catch on in your common camera because it doesn't really solve a pressing problem but it will certainly find lots of applications.
As soon as I read the article, it seemed fishy to me. How can you create data where it doesn't already exist? If you take a scan of a patient, a tumour will either show up or not show up in the data. If it shows up, there's no need for enhancement. If it doesn't show up, no amount of enhancement can cause it to do so.
Then I came across this blog post by Terence Tao, one of the researchers mentioned in the Wired article.
It has some very interesting explanations of how this is supposed to work. I'm still not sure that I'm convinced though. Common sense is still screaming at me "this cannot possibly work" - but then that happens with quantum mechanics too.
In the old movie "The Conversation" Gene Hackman walks right into that trap when he infers away all the nuances inside the spotty data of a surveillance recording. Two lessons: 1 - Same dangers, different application. 2 - Same fundamental method, different decade, nothing really new here.
Relevant information: I'm a physicist, and my research group is actively researching quantum state tomography via compressed sensing.
This technique is quite useful also in quantum state tomography. Consider a qubyte. We represent it by an 2^8 x 2^8 matrix of complex numbers. Now we want to measure it. We have to make 2^16 measurements (keep in mind that a quantum measurement is a nontrivial task), and use this data to reconstruct the original matrix, which again is a very intensive task, if done right (there are quick-and-dirty algorithms to do it, but they don't work very well). It is just plain impossible to process so much data, in a day-by-day basis.
But here comes compressed sensing! Normally, we are interested in states that are pure, or quasi-pure. That is, are represented by a sparse matrix, in the correct basis. So, using this technique, we only need to do a quantity of measurements that scale linearly with the dimension of the state (as opposed to the quadratic growth that a full measurement requires), and the amount of processing that we need is also proportional to the amount of measurements.
So, we can shift the limiar of impossibility. Before we needed O(2^(2d)) measurements, now only O(2^d). Still unpleasant, but makes the problem tractable today.
entropy happens
The article was a bit poor. The data sets aren't really incomplete in most cases. They only seem that way from a traditional standpoint. The missing samples often contain absolutely no information, in which case the original image/signal can be reconstructed perfectly. In brief, nyquist is a rule about sampling non-sparse data, so if you rotate your sparse data into a basis in which it is non-sparse, and you satisfy the nyquist rule in that basis (though not in the original one), you are still fine.
I like this link better l1 magic
refactor the law, its bloated, confusing and unmaintainable.
Could this be applied to radiotelescope data sets? SETI Anyone?
Nobody thought of this? Is this still /.?
Great, now we only need the "uncrop" algorithm to be on-par with TV shows!
Essentially the reason this sparsity is a functional concept is that in a very large data set, noise appears more often than just once. The more sparse a sample is, the more interesting it is because the less likely it is just noise. So if you seek strange artifacts in your data that do not correspond to any other noise then you may have just found additional data captured by your equipment. Statistically, anyway. Essentially this technique reduces your uncertainty in your data by processing it in search of these unique events which are within the noise floor of the equipment.
Let them try get data from this:
zzzsksksdS..c.zx.czx.czvvv....L.sssd asdaAszzss sskkkSkkk rrrsrH...rrwr..w.ere.r.rrrregewwwe.D ....rtyergsfrr rredddaOdecwrb bbfpppT.qwrrIrrdeeess ssksSeerrrrer eeAtrrtttttkkWggp rrroEpttrrdddd Seeerrrf cppphhtOwweerpp ppttttMweeeeccczz zzxxE!
The key is that the image must be sparse (and almost all useful images are sparse). By definition, a sparse image contains less information than the pixels that make it up can store. Thus, it is compressible. So you're not creating data where it doesn't exist, you're just not sampling and storing the redundant parts.
It's no more magic than gzip or jpeg compression.
Chloe O'Brian has been able to do this for years while hiding in an improvised safe house with a computer array composed of old Vic-20s and acoustic modems.
Super Redonkulous Fluffhance!
[The inventor of CS, Emmanuel] Candès...
The way I understand it, there is actually a bit of controversy over whether Candès or David Donoho "invented" compressed sensing. It seems to me that Donoho was actually first, but Candès ended up getting most of the credit.
After cropping, I may end up with a 1-2 megapixel image (sometimes much lower)
Try image stacking. A program I've used successfully for this is PhotoAcute. Provided your body+lens combo is in their database, you can stack multiple near-identical images (use Burst or Auto-bracket mode) and get "super resolution". Of course, this doesn't work so well if your subject is moving. If your body+lens combo isn't in their database, you can volunteer a couple hours of your time to make a set of ~ 100 specific images they can use to create a profile for your gear. If they accept it, they'll offer you a free license for the software. I have no connection with the company other than being a satisfied customer.
--
.nosig
Sorry to be dense, but I don't understand where compression comes into this. You're not compressing anything, you're somehow discovering data that wasn't sampled in the first place. I don't see the relationship between the two concepts.
Can you explain what I'm missing, in terms of my original example? If there's a dark spot on the image indicating a potential tumour, then that information is there in your data, and no clever processing is necessary. If the dark spot is not there, no amount of processing will make it appear. What am I missing?
This is an ENTIRE FIELD in the satellite remote sensing community.. Theres so many papers on improving limited satellite imagery its nauseating. Browse.. http://www.igarss09.org/Papers/RegularProgram_MS.asp
---------
No matter how thin you slice it, its still baloney.
CS as described in the article will NOT recover a signal from noise any better than 'conventional' techniques.
What it seems to do spectacularly is enhance sparse data sets where the noise is low and the data bandwidth of the signal is relatively narrow.
To detect frequency hopping signals, CS needs a good idea of the nature of the signal. It shouldn't be too difficult to create signals that defeat CS. It will do OK at detecting frequency hopping in a noise free environment but will perform poorly with noise present.
The data bandwidth of the recovered signal depends on the signal bandwidth and the noise. Shannon's law still applies. In a channel with no noise, the data bandwidth is theoretically infinite. In such a system, the entire Encyclopedia Britannica could be encoded in a single symbol. That is about as sparse as a data set can be ;-)
Nostradamus predictions... each new researcher recover new data from that noise. (each word of this should be quoted, as almost none is what it mean).
Is risky to "fill in the blanks" or give your own (i.e. following a set of rules) meaning to noise, it will show things as you think they should be, and the exceptions will be missed or discarded.
You're missing the scope of the sampling. It doesn't sample a 200x200 square and give you a 1024x768 image, it samples random pixels from the range you are looking to come out with in the end.</p>
To put it in Javascript...
for(rows=1; rows < maxrows; rows++){
for(cols=1; cols < maxcols; cols++){
if(Math.rand() < 0.2){ StorePixel(cols,rows) }
}
}
And if taking an image of something that typically appears in the natural world, you will come out with a picture that is "not wrong." That means that it won't put something there that isn't supported by the data, data that is randomly sampled and likely to represent at least a portion of every significant aspect of the original object. In practice, they have used this to great efficacy, so the arguments of "it won't work" are invalid. It has, it does.
If they can do it for a picture can this same methodology be utilized for audio/data signals - then they can go through and reanalyze all the Seti@home data that has already been analyzed. It has often been said that if the aliens have any potential intelligence it would be indistinguishable from noise.
It doesn't sample a 200x200 square and give you a 1024x768 image, it samples random pixels from the range you are looking to come out with in the end.
Can you explain how picking a pixel at random is better than sampling every 4th pixel? Surely the randomness just increases the chance that you'll miss some essential feature in the image?
Say the size of a potential tumour in the image is 5 pixels wide. Sampling every 4 pixels would guarantee you catch the tumour (the number of pixels to sample is chosen on the basis of the smallest size tumour which it is necessary to catch). Sampling an identical number of random pixels, on the other hand, would mean there is a good chance you will not sample any data point within the tumour, resulting in it being totally missed.
In practice, they have used this to great efficacy, so the arguments of "it won't work" are invalid. It has, it does.
I'm not arguing that "it won't work". I have not done the research to support such a claim, and I suspect I do not have the requisite technical expertise to do said research within a reasonable period of time.
What I am saying is that I've got no idea how it can possibly work. It goes against all common sense. I was hoping someone could explain it to me by pointing out the flaws in my logic. No-one's managed to do so yet.
Can you explain how picking a pixel at random is better than sampling every 4th pixel? Surely the randomness just increases the chance that you'll miss some essential feature in the image?
I would imagine that it's something to do with the nature of the underlying statistics. One explanation I can think of is that this method works by looking for "patterns" in the underlying data. If you are sampling every 4th pixel then you could be systematically missing a pattern in the data. Worse than that, the method of sampling you describe could actually introduce spurious patterns!
When you compress something you represent it in such a way that you can reconstruct the original based on less data. Effectively you're "discovering" data that wasn't sampled (stored) in the first place. Except, with lossless compression at least, you're not really doing this. The compression process discards only redundant data.
Compressed sensing works in much the same way except that you effectively treat your acquisition and display process as you would your reading-from-disk-and-decompressing process. Instead of sampling everything you skip sampling points that are likely to be redundant.
If you go too far then yes, you get image degradation. If you keep things reasonable (and reasonable depends to some extent on what kind of image you're acquiring), you can get a perfect reconstruction, just like you do when you reconstruct a gzip compressed image.
Regarding your example: it's easier if you consider the process as it actually occurs in MR. The image is actually acquired in the Fourier domain so every point you acquire has information about every pixel in the image. So you've got a dark spot indicating a tumor. Yes, that information has to be in your acquired data but that doesn't mean you're going to be able to actually distinguish that tumor when you reconstruct the image. Noise and artifacts may obscure it.
Compressed sensing effectively tells you what you need to sample in order to retain the information about that tumor in your reduced data set (with high likelihood), and how to reconstruct the data so that the tumor is actually evident in the image (mostly be reducing artifacts).
Here's an example (sorry, I can't post an image with a tumor due to privacy).
Image C is the original, where features are clearly visible. D is undersampled in a way you might do to make an MR scan faster. What looks like noise in the image isn't really noise, it's decoherent aliasing artifacts due to the undersampling. The information to reconstruct the image is still there, but the naive reconstruction technique can't reveal it. CS reconstruction (E) reveals it.
Here's an idea. Lets pretend that a rigorous bayesian method like maximum entropy doesn't exist. :P
This message was scanned by European governments and contains no terrorism.
The /. headline and the Wired article do tend to misrepresent Compressed Sensing as some kind of noise-remover, despeckler, or image enhancer. This is simply not the case. In Compressed Sensing, we are intentionally sampling a signal in an incoherent domain so that each measurement evaluates the entire image globally. In other words, each sample has as much weight as any other, so when we hold on to fewer of them, we may obtain more information about the original signal than if we sub-sampled the signal in the original domain. When we reconstruct the original image from our compressed/sub-sampled measurements in an incoherent domain, we are trying to find the most sparse signal that matches the measurements we observed (solving an ill-posed inverse problem via constrained optimization). The signal sparsity can be thought of the orderedness or "structured-ness" of the signal. In other words, the most ordered image that matches our compressed measurements is correct solution with high degree of probability. For a technical primer, check out this paper ( http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/CSintro.pdf ).
Okay, yes, that might be a little bit weighty if you aren't in the field, but I would suggest you check out Nuit Blanche ( http://nuit-blanche.blogspot.com/ ) for a description of what exactly CS is, how it works, and what it is useful for. Today's article is especially interesting in this regard.
Any potential application of this in the SETI program?
"It's not fraud, it's just some editor being as sensationalist..."
Definition of fraud: A deliberate deception used to get an unfair result.
The editor wanted to get more attention for the article than the article deserved.
"This should have been obvious the second you saw the word "Wired" anyway."
If Wired is routinely fraudulent, that does not diminish the fact that tricking people to get attention is fraud.
The article is of interest only to mathematicians and those interested in smoothing data.
See this comment below. Quote: "The idea that we could use this algorithm for medical diagnosis is just nonsense."
To clear-up and guess "details" in such a manner that a picture, wave, music, whatever can be seen or heard more easily by a human is very nice. Good for old pictures and sounds. I can even buy garbled culprit face reconstruction as long as it cannot be used as proof in a court. This sounds like a new, must-have, expensive, photoshop/gimp filter and congratulations.
But ...
Anybody doing anything serious would use a secure, ciphered, way of communication. Not clear text, clear waves, or screen fonts/colors easy to "measure" electromagnetically from afar. So the eavesdropping enemy communication does not, in my humble opinion, hold. (Maybe a century ago)
And last but not least. The bigger issue is that it does not show the most important thing: reality.
Nobody can create reality from a subset. You can be smart as a monkey* but you can only guess, presume, imagine what's missing.
If an MRI is taken from any part of my body, I want ALL the REAL dots there. Even one missing dot could actually be something serious (Will it be guessed ? Not guessed ? Just my luck.). And a wrongly guessed one could make me panic enough to give me a serious heart condition. So no thank you.
*:this sounds better in my native tongue
Irrelevant news and morons using moderation to mod down what they disagree on. 2018 resolution: so long.
Compressed sensing is the same mathematics behind the Rice single pixel camera covered on Slashdot a few years ago.
To the Zappruder film!
/jk
.. to a Hi-Res Fiction. If there's no data, there's no data.
What if that black pixel over Obama's right shoulder that got "enhanced" to be a white pixel was actually an assassin with a high powered rifle standing 1000' in the background?
What if that dot on the map that gets turned from white to brown was actually a missile silo and not dirt?
I don't see much use for this other than in special cases, and maybe games, where you need stuff to look real, but not be real.
but given a photo of Barack Obama's face with half of it blacked out, you can estimate with great accuracy what was in the other half.
It's rather easy to guess what's in the half that isn't blacked out, yeah? ;-)
The point of the concept is that there are many signals which do not actually contain as much information as they possibly could. For those signals, it's possible to analyze the samples in a different domain and reproduce the original signal.
For instance...a pure sine wave audio signal could take a lot of space if encoded as a WAV file. However, it would be possible to reproduce it 100% accurately by simply encoding the frequency and duration. This would take much less space than the WAV file.
What they're doing is analogous to sampling a musical signal at random and then working on the fourier transform to figure out the least complicated way of combining various frequencies to give the observed samples. It turns out that in many cases the least complicated solution accurately provides the non-sampled values as well.
This is not making information out of nothing, but simply realizing that the original signal was constrained in some way. If the original signal was purely random or else contained the theoretical maximum amount of information, this technique wouldn't work.
"Can you explain how picking a pixel at random is better than sampling every 4th pixel? Surely the randomness just increases the chance that you'll miss some essential feature in the image?"
You're missing an element of complexity. They're not directly sampling pixels, but rather some other "basis".
Take a look at the one-pixel camera described at "http://dsp.rice.edu/cscamera". Rather than actually sensing a single pixel at a time, they sense the whole image combined with random patterns. By taking multiple samples with different random patterns (but fewer than the number of pixels in the image) the resulting image can be regenerated with a good degree of accuracy.
Ultimately it's similar to sampling a large number of pixels then compressing the image to a jpg--the difference is that they're doing it all in one step. This can be useful if you want low-powered sensors, for instance.
The algorithm does not work at all in the way that the wired article describes. In CS you make the assumption that your unknown data set is sparse, it is now known that a random sample of a sparse data set contains all the information about the sparsity of that data set. From here you seek the most sparse data set which agrees with your sample, and it will be the exact solution provided all your assumptions are true and your sampled data is perfect. If your assumptions are nearly true and your sampled data is nearly perfect, then you will recreate very nearly the exact data set.
If you want to know the 'algorithm' used in CS is probably some variant of the simplex algorithm, or some interior point method for solving convex optimisation problems.