Can white noise be (losslessly) compressed?

Question

Can I expect a vector whose components are i.i.d. Gaussian noise to be compressible (lossless compression)? Why or why not? If so, how much?

EDIT: To be clear, I mean "compressible" as in "compressible by some compression algorithm", so I would get to choose the compression algorithm after seeing the sampled noise.

Answer 1

You may need to think carefully about definitions here.

First question: when quantifying "compression", are you counting in the length of the decompression algorithm itself?

If not, then the answer is trivially yes. In fact, you can compress any input vector to zero bits by setting the decompression algorithm as follows:

if(length(compressed.input)==0) then decompressed.output = (hardcoded vector matching the outcome that you just observed) else decompressed.output = vector(0) [or anything else at all, it doesn't matter since the "else" won't get triggered].

So let's assume that the length of the decompression algorithm matters, otherwise the question isn't very interesting (and the answer is of no practical use).

Second question: are your inputs in fact the exact outcomes of an i.i.d. Gaussian process, or are they approximations of those outcomes represented in some finite machine precision?

If the former, then there are infinitely many possible inputs, each occurring with probability zero.

For any finite m and n, there are 2^m possible decompression algorithms of length m bits, and 2^n possible inputs of length n bits. Hence there are at most 2^(m+n) possible outputs that could be produced by a decompression algorithm of length m acting on an input of length n.

It follows that the probability that the first value in your vector is expressible as the output of (decompression algorithm of length m) acting on (compressed representation of length n) is the sum of probabilities for a finite number of events which each have probability zero... i.e. zero.

That is to say, there is probability 1 that you will need an infinitely long decompression algorithm and/or compressed input in order to exactly represent the first entry in your vector. So, no, you can't has compression in that case.

If you are dealing with a finite-length machine-precision approximation of a Gaussian variable, and you just need your output to match that approximation, things are looking better.

The details will depend on exactly how your computer stores floating-point numbers. But in general:

• Assuming the approximated Gaussian values are rounded to n bits, there are 2^n possible values they can take (maybe a few less).
• In general, those values will NOT all have the same probability of occurring.
• You can use this inequality of probabilities to develop a compression algorithm suitable for Gaussian-distributed numbers (see Shannon's seminal info-theory paper; basically, come up with a coding that assigns shorter strings to higher-probability inputs). You'll need information about the mean and variance of your Gaussian function, but you can get that from the inputs.
• Then apply that algorithm to compress each element of your vector.

Answer 2

In general, white gaussian noise (WGN) is non-compressible. However, the realizations of WGN do have sparse representations. These are conclusions of a paper by Ori Shental. Herewith I provide the links to his work:

Sparse Representation of White Gaussian Noise with Application to L0-Norm Decoding in Noisy Compressed Sensing

or you can read the following presentation:

Replica Method for Sparse Representation of White Gaussian Noise with Application to Noisy Compressed Sensing