Gimp doesn't have this because in addition to the image, you need explicit knowledge of where the image came from.

Suppose you have an image which you already know is a cartoon. Compressed sensing can clean it up, but uses explicit knowledge of what cartoons look like. Similarly, if you know the image is scanned text, a different compressed sensing algorithm based on scanned text can clean it up.

But if you don't know where the image comes from to begin with, compressed sensing won't work.

This certainly could be done. Here are some MATLAB routines that implement it:

http://www.acm.caltech.edu/l1magic/

Seven examples using compressive sensing:

http://www.acm.caltech.edu/l1magic/downloads/l1magic.pdf