Compressed Sensing - Getting something for nothing

Wired has an interesting article on the data-manipulation techniques that could lead to real Blade-Runner / CSI style image enhancement.

1 Undersample
A camera or other device captures only a small, randomly chosen fraction of the pixels that normally comprise a particular image. This saves time and space.

2 Fill in the dots
An algorithm called l₁ minimization starts by arbitrarily picking one of the effectively infinite number of ways to fill in all the missing pixels.

3 Add shapes
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.

4 Add smaller shapes
The algorithm inserts the smallest number of shapes, of the simplest kind, that match the original pixels. If it sees four adjacent green pixels, it may add a green rectangle there.

5 Achieve clarity
Iteration after iteration, the algorithm adds smaller and smaller shapes, always seeking sparsity. Eventually it creates an image that will almost certainly be a near-perfect facsimile of a hi-res one.

I haven't seen the original paper, so I'm a little skeptical. I'd like to see what kind of error is incurred by this successive approximation.   How different is the reconstructed image from the original?  There are always limits to these things.