4
$\begingroup$

I'm currently playing around with some compression algorithms and I'm asking myself if there is a type of data distribution / noise distribution that is easier to target with quantization (meaning less distortions at same rate). To my understanding i.d.d. Gaussian is the upper bound on "compression difficulty".

Are there distributions that especially efficient to compress, maybe via quantizers designed for those (I know about LLoyd-Max but I'm looking for something that works generally well with a known distribution and doesn't need to be optimized samplewise)? Does it make sense to transform the data into such a distribution prior to quantizing it?

$\endgroup$
  • $\begingroup$ Are you assuming iid sources? $\endgroup$ – Laurent Duval Jul 28 '18 at 0:00
  • $\begingroup$ In my use case, yes, I do! $\endgroup$ – Jane Dough Jul 28 '18 at 0:05
1
$\begingroup$

I'm currently playing around with some compression algorithms and I'm asking myself if there is a type of data distribution / noise distribution that is easier to target with quantization (meaning less distortions at same rate). To my understanding i.d.d. Gaussian is the upper bound on "compression difficulty".

Fat32's answer and your distortion aspect are on-spot here:

The continuous Gaussian distribution is the distribution that maximizes differential entropy.

But things get a bit hairy in your general problem:

a type of data distribution / noise distribution that is easier to target with quantization (meaning less distortions at same rate).

discrete input, lossless compression

So, I'd argue that a data distribution is already given in discrete quantities – and for discrete sources it's trivial to show that the minimum entropy is 0 (discrete information is non-negative, and hence so is its expectation, the entropy), and can be realized by a source where all but one element have probability 0 (and thus, the remaining element probability 1), since then the expectation value of probability-weighed informations collapses to the information in the only occurring value, and $\log_2(P=1)\equiv 0$.

Hence, the source that always gives the same value has 0 bit of information, and can be compressed the best. By simply ignoring the source. As it gives no information.

Now assume you've got a discrete source of information that you want to compress losslessly. Can you map that to a different distribution that has lower entropy without losing info? No, you can't.

  • Either you find a mapping that combines multiple input values into one output value, which means you lose information, and hence are lossy,
  • or you only increase the entropy (or, best case, you just keep the same entropy), by splitting events that are identical into multiple bins, thus approximating the discrete uniform source more, which has maximum entropy.

So, losslessly, you can't do anything to improve your source if its i.i.d.; compression that works better than a plain Huffman codec on average (for example, lossless audio codecs) uses the fact that observations aren't independent; no matter what you do, your losslessly compressed data still has at least as much bits as there was entropy in the source (that's a fundamental result of basic information theory).

Now, the more interesting case is that of noise, or signal, in the continuous case.

continuous source, quantization

The problem you're describing, *how much information do I lose when I subject a source of information to a specific quantization" is called Rate-Distortion Theory. It's a fun field full of fun integrals!

So, let's start with a short consideration of what quantization is:

It takes a continuous source and maps it to discrete case. Quite intuitively, this is a lossy process (or your source wasn't really continuous from the start): The probability of any one of the continuously possible values is (surely) 0 – thus, the information in the event "value $v$ has been observed" is $-\log_2\left(P_X(v)\right)=-\log_2(0)$, and that is unbound (the event "has infinite information", but I hesitate saying that, because "infinite" is not something you should quantize things with). Thus, the continous source has unbounded entropy in the discrete information theory sense – and since any quantization in this world can only give you a finite amount of bits, you're bound to lose some of the original information. (I could've explained that more plastically – how do you quantize $e$, $3$ and $\pi$ with the same quantizer and still "hit" all three values exactly?)

So, the question is, what continuous distribution $F_X$ of the source $X$ suffers the least distortion when being sampled (by a quantization function $Q: \{x\in X\}\mapsto \{y\in Y\}$ with $Q^{-1}(y)=x\;\forall y\in Y$, i.e. a quantization that leaves the values it can "exactly" produce untouched) with a fixed bit depth $r$, giving us the discrete source $Y$?

Now, following the usual Rate-Distortion theory approach, we should first define a distortion function $D$ that tells us how "far" the quantized value $x$ is from the input value $y$, but we don't have to: any reasonable metric would have the property of being $D=0$ for $y=x$, and always $D\ge0$.

Hence, the infimum of the distortion would occur under optimal distribution $\tilde F_X$ of $X$ (let's assume said distribution is differentiable to its density $\tilde f$, else things just get uglier):

\begin{align} d &= \inf_{F_X} E\left[D(X,Y=Q(X))\right]\\ &= \inf_{F_X} \int\limits_X f_X(x)D(x,y=Q(x))\,\mathrm{d}x \\ &= \int\limits_X \tilde f_X(x)D(x,Q(x))\,\mathrm{d}x \\ &= \int\limits_{\left\{x\in X| Q(x)=x\right\}} \tilde f_X(x)D(x,Q(x))\,\mathrm{d}x + \int\limits_{X \backslash \left\{x\in X| Q(x)=x\right\}} \tilde f_X(x)D(x,Q(x))\,\mathrm{d}x \\ &= \int\limits_{X \backslash \left\{x\in X| Q(x)=x\right\}} \tilde f_X(x)D(x,Q(x))\,\mathrm{d}x \\ &=\int\limits_{X \backslash \left\{x\in X| Q(x)=x\right\}} \tilde f_X(x)D(x,Q(x))\,\mathrm{d}x \\ &= 0 \\ &\iff \tilde f(x) = 0\; \forall \notin Y\\ &\implies \tilde F_X = F_Y \end{align}

So, this might not be a surprising result, but it's quite fundamental to understand: No matter how you (sensibly) define distortion/loss, the closer you get to the output distribution of your quantizer, the less distortion you see.

Optimizing for something better than just transmitting the least bits possible

With that result, we can move on: we already know the optimally compressible output distribution $F_Y$, namely the constant output mentioned above, so the optimal continous source distribution in terms of compression is just the same.

Assuming you really want your quantizer to give you an $r$-bit observation of reality, you'd build it to have $2^r$ steps of equal probability, and since "wasting" steps is a bad idea, we just pick $r$ to be an integer.

Hence, you'd look at the source distribution and find a continuous mapping so that the output of $Q$ is discretely uniform.

That means you'd just find a mapping so that the density mass in each of the quantization bins is equal.

In the uniform step width quantization ("linear ADC"), that means finding the inverse of $F_X(x)$.

$\endgroup$
  • $\begingroup$ Nice! But it seems your auto-complete prefers property over probability ? Or It should have been so long, since I'm away from the field :)) And honestIy I though you should have never mentioned the differential entropy.. :-) Anyway, OP is already playing with these things :-) $\endgroup$ – Fat32 Jul 28 '18 at 17:39
  • $\begingroup$ aargh :) yeah, probability. I was kind of hesitant to introduce that term, too, hm, maybe I should surgically remove that from the post. $\endgroup$ – Marcus Müller Jul 28 '18 at 17:53
  • $\begingroup$ Noo it's quite ok! Hard to understand though... As anything with information theory! $\endgroup$ – Fat32 Jul 28 '18 at 19:58
  • $\begingroup$ Great answer! In the last part you were describing compressor/expander quantization, right? Does it matter whether we map Fx to match Fy or whether we use an algorithm like LLoyd to describe Fx with our quantizer? $\endgroup$ – Jane Dough Jul 28 '18 at 20:02
2
$\begingroup$

It's very easy to make fundamental mistakes on the topic of information theory, unless you have some PhD or alike in the field. That being said as far as I remember the following could roughly be stated about your question.

Considering a discrete probability and source model of iid, the most efficient compression of a source happens when the source has minimum Entropy (information) in it; i.e, its average codeword length (in bits) per symbol is minimum. Such a variable length code would have the highest compression and the most efficient coding to represent the source in a lossless manner.

Such a case would happen when one of the symbols of the source alphabet has a probability close to 1, and all other probabilities are close to zero. Such a distribution is said to be highly skewed. But I'm not sure if a unique minimum can be shown to exist unlike the case of maximum Entropy (minimum compression) which happens when all the symbols have equal probability.

On the other hand, you are talking about lossy Quantizers and probability distributions. PDF optimized lossy quantizer design is about finding the best input decision and output reconstruction levels for a given soure PDF such that the the expected quantization error (MMSQE) per given source distribution a minimum. And that's the Max-Lloyd quantizer for the scalar case. Rate-Distortion theory shall be invoked for various considerations here.

Merging these two concepts you would say that, for a given source power (or dynamic range) the one which required minimum number of quantization levels while still providing least possible quantization error (distortion) would be given by a source whose PDF is dense at a certain region. In that case you would put a few fine quantizer levels at those dense signal positions and then use larger step size levels outside of that region, which would still provide minimum expected distortion.

$\endgroup$
  • $\begingroup$ Thanks for the answer! Regarding "locally dense" PDFs, my intuition would be the same, derived from the laplacian distributions of DPCM/DCT coeffcients in practice. Also geometric distributions. I'm just thinking for laplacian for example, wouldn't the fat tails (as opposed to gaussian) outweight the benefit of the dense mean? Depends on the scale probably. $\endgroup$ – Jane Dough Jul 28 '18 at 2:22
  • $\begingroup$ Your welcome! Unfortunately my answer was more of a intuition than a precise mathematical one... As you state, the output coefficients of a DCT / DPCM encoder resemble that of a Laplacian distribution which also suggests that their residuals carry quite minimal information, yet I'm not sure how to mathematically call it as the minimum... $\endgroup$ – Fat32 Jul 28 '18 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.