# Compressed Sensing vs Common Compression Approaches

I have a very basic question regarding common compressing approaches. Often, I have heard something like "The problem in our common way to compress data is, that we have to acquire a huge number of samples from our signal, because of the Nyquist-Shannon theorem. But then, when we compress these samples, we throw most of the information away."

I do not really understand the last sentence, probably because of lack of knowledge. So, my question is: what do you throw away and why?

Here are some sources:

Michael Lustig, at 0:26 he says

Why we need to acquire all the data in the first place, and then throw most of it away.

Mark Davenport, on Slide 4 at 0:45 he says

The very first thing that we do after we acquire some data is we compress it and seemingly throw away a lot of information that we painstakingly acquired.

## 1 Answer

Compression works by reducing redundancy and there are a number of ways that this can be done.

Very briefly, consider the pair of functions $C = f(S_{original}, \Theta_{f}), S_{recovered} = g(C, \Theta_g)$, where $f,g$ are the compressor and decompressor functions respectively, $\Theta$ is the set of parameters specific to $f,g$ and $C, S_{original}, S_{recovered}$ are the compressed, original and decompressed sequences respectively. If the compression is loseless then the error between the original and recovered sequences should be zero ($S_{recovered}-S_{original}=0$).

However, we might accept some small error so that $S_{recovered}-S_{original}<=e$. In this case, the compression is lossy.

What $f$ does is to reduce the redundancy in $S_{original}$ so that it can be represented using less data so that the length of $C$ is less than the length of $S_{original}$ ($|C| < |S_{original}|$).

Run-length encoding achieves this by looking for sequences of repeated values and substituing them for a pair of "value, count". The redundancy here is most obvious.

Huffman encoding, does this by creating a carefully constructed "dictionary" of codewords based on knowledge about the source of a signal. In this, frequently occuring values are mapped to short codewords and infrequently occuring values are mapped to longer codewords. In this way, instead of representing all values with the same amount of data (for example 8 bits), frequent values are represented with less data (less than 8 bits) and on average lead to describing a long $S_{original}$ with a short $C$. More frequently appearing characters than others, again, imply redundancy.

Lempel-Ziv-Welch encoding reduces redundancy by looking for repeating sequences. Once a repeating sequence is found it is placed in memory and assigned a codeword. The next time the same sequence is found it is substituted with its codeword. In this way, long sequences (of more than one values) are substituted with just one value (an index into the dictionary).

Other methods rely on preserving just a part of the frequency spectrum of a signal or image therefore reducing the overall ammount of data that needs to be described.

The key thing to remember here is redundancy. Repeating values, slow varying signals (which again implies nearby samples having similar values) or even components with negligible contribution. If a signal contains redundancy then it is predictable and if it is predictable then it can be captured in a model. (As a side note, please note that this redundancy, or amount of information in a signal can be quantified by Entropy).

So, compressed sensing is in a way similar to lossy compression in the sense that we are trying to recover an $S_{original}$ from a (shorter) $C$ accepting some small error $e$ in the recovery with some "decompressor" $g$.

BUT, to do this we need to make certain assumptions about the dynamics of $S_{original}$. For example, it is varying slowly, therefore it is not necessary to sample the full spectrum of frequencies that could generate some potential $S_{original}$

Another way to think about this is to look at a picture or a drawing and cut (or black)out a rectangle from it. That is, throw away some data or, don't acquire a part of data from the beginning. If the picture is predictable enough then it is easy to reconstruct the missing part. WHY is it predictable? Because it is a repeating pattern and we assume that the missing bit behaves similarly. If the picture is less predictable then we can still attempt to reconstruct a rectangle of it from the surrounding information but perhaps it will not be as accurate.

If we were to take this to the extreme (as it is done in practice anyway), then we could say that we don't really need to acquire all of the pixels of the image. We can acquire some of the data and by exploiting the redundancy of the signal and the fact that it is not going to be too unpredictable (i.e. we can model it) reconstruct the missing bits...almost as closely to reality.

This is exactly what iterative reconstruction techniques (a family of $g$ "decompressors") are doing by progressively trying to minimise the error between an $S_{recovered}$ at some iteration $n$ and the subset of known values contained in the actually acquired $C$ and stopping this process once the error drops below an "acceptable" $e$.

For more information please see this link which is a relatively simple iterative reconstruction scheme that shows how to "update" the unknown values from the known values. For even more information please this link.

Hope this helps.