JPEG compression works in a similar way: the image is segmented in blocks, each of them is transformed to frequency domain via DCT and then the frequency coefficients are quantized, or discarded if small. The rules for the last step are optimized to minimize human perception of discrepancy between original and compressed image.

What compressed sensing shows is that even a very rough optimization step, completion unaware of contents and human perception, can give worse but comparable results.