2
$\begingroup$

Consider the problem of lossily compressing a memoryless binary source $X \sim \operatorname{Bernoulli}\left(\frac{1}{2}\right)$ at target Hamming distortion $D < \frac{1}{2}$. According to the analysis in 9.3.1 Example: Binary Source from this note, the marginal distribution of the optimal reconstruction $\hat{X}$ is also $\operatorname{Bernoulli}\left(\frac{1}{2}\right)$, which means $H(\hat{X}) = H(X) = 1$. Moreover, the rate of the compression, i.e., the mutual information between $X$ and $\hat{X}$, is $I(X; \hat{X}) = 1 - H(D) < 1$.

My question is, what exactly is stored on the disk, or more formally, transmitted through the channel? Based on the rate-distortion theory, we can compress $k$ samples from $X$ (denoted $x \in \{0, 1\}^k$) down to $k(1 - H(D))$ bits (denoted $z \in \{0, 1\}^{k(1 - H(D))}$), and the reconstruction (denoted $\hat{x} \in \{0, 1\}^k$) can achieve an expected distortion of $D$.

  • What is the function that maps $x$ to $z$? I believe $z$ is essentially the "mutual information" between $X$ and $\hat{X}$, but I have no clue how to compute it.
  • What is the function that maps $z$ to $\hat{x}$? I think this must be a stochastic function, because $\hat{x}$ has higher entropy than $z$ ($k > k(1 - H(D))$).

I am confused because most material on lossy compression only talks about the rate-distortion theory, without explaining how we can do lossy compression with it. After all, the entire point of lossy compression is to shorten the bitstream, and I need to know a concrete way of doing that.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I'm not an expert in this topic, but my approach would be to apply vector quantization. In other words, take $n$ bits from the source and approximate them with $nR < n$ bits. Note that this is similar to conventional quantization, since you can consider the $n$ bits as a floating point number, which you then somehow "truncate" to a defined number of decimals.

There are several textbooks that go into more details about vector quantization than the note you posted above; off the top of my head I recall Gallagher's book on digital communications covers this. I'm pretty sure Proakis does as well.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, this is very informative. I have a quick follow-up question if you don't mind. The RD theory states that the optimal reconstruction $\hat{X}$ must have distribution $\operatorname{Bernoulli}\left(\frac{1}{2}\right)$. Does the optimal VQ reconstruction also follow this distribution? That would surprising because it means the entropy of $\hat{X}$ would be $n$ but the compressed $X$ only has $nR < n$ bits. Where did the remaining $n(1-R)$ bits of entropy in $\hat{X}$ come from given a deterministic codebook? $\endgroup$
    – nalzok
    Commented Feb 3 at 17:18
  • $\begingroup$ Not sure. Note that the $nR$ bits are still Bernoulli(1/2); maybe the theory assumes that both entropies are equal when $n$ grows without limit? Also, keep in mind that all this theory becomes interesting when the source symbol probabilities are not equal, and that Rate Distortion Theory applies to lossy compression. $\endgroup$
    – MBaz
    Commented Feb 3 at 19:25
  • $\begingroup$ @nalzok the reconstruction $\hat{X}$ of a scheme with deterministic codebooks is not iid. $\endgroup$
    – AlexTP
    Commented Feb 4 at 9:50
  • 2
    $\begingroup$ @nalzok for example, you can make $\hat{X}$ iid, in the simplest scheme, by adding independent $n(1-R)$ bits that are independent of the other $nR$ bits. The reconstruction random source has the entropy of $n$, but the mutual information $I(X;\hat{X})$ is still $H(D)$ less stemming the distortion $D$ you are willing to sacrifice. $\endgroup$
    – AlexTP
    Commented Feb 4 at 9:59
2
$\begingroup$

The rate distortion theory simply doesn't answer the questions you ask if how you do it.

It does answer questions like "is this rate sufficient to get things across with at most distortion D", or, "what is the best I can do in this situation", but it has no answer to the question of how.

And that is pretty fine, because the how usually is concerned with how the source you actually care about is structured differently than a binary memoriless equiprobable source.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the response! I wonder what theory answers the question of how? For simplicity, let's just assume the source I care about is really a binary memoryless equiprobable source. $\endgroup$
    – nalzok
    Commented Feb 3 at 2:13
  • $\begingroup$ Abstract concepts like «memoryless equiprobable source» are useful for developing generic theory and absolute limits. For real-world problems, there tends to be structure in information (and how that information is to be consumed in case of lossy compression) that require domain-specific knowledge. $\endgroup$
    – Knut Inge
    Commented Feb 3 at 8:32
  • $\begingroup$ I suspect that your memoryless equiprobably source case is nearly useless in practice. Usually you see lossy compression used when you can identify extraneous information and compress in a way that loses that information but not the important stuff. The two biggest examples of this that I know of are audio and image compression for consumption by humans: in both of these cases, the human perceptual system itself is less able to perceive high-frequency content, so the compression routines intentionally allow loss at high frequencies. $\endgroup$
    – TimWescott
    Commented Feb 3 at 20:59
  • $\begingroup$ I don't know whether "useless" would be my choice of words, but I'd say it's a very degenerate case, where the source is discrete, hence has classical entropy of 1 bit, and zero differential entropy. Not much to do there for rate distortion theory. You lose exactly the binary entropy of your bit error probability in mutual information. Done. $\endgroup$
    – sina bala
    Commented Feb 4 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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