Mehmet Emre Tiryaki
Back to Notes

Rate Distortion

Setup

X1,X2,…,XnX_1, X_2, \ldots, X_n iid ∼p(x)\sim p(x) with support X\mathcal{X}. The encoder describes XnX^n by an index fn(Xn)∈{1,2,…,2nR}f_n(X^n) \in \{1, 2, \ldots, 2^{nR}\}, and the decoder represents XnX^n by an estimate X^n∈X^n\hat{X}^n \in \hat{\mathcal{X}}^n.

d:X×X^→R+d : \mathcal{X} \times \hat{\mathcal{X}} \to \mathbb{R}^+ measures the cost of representing xx by x^\hat{x}.

Hamming:d(x,x^)={0,x=x^1,x≠x^squared error:d(x,x^)=(x−x^)2\text{Hamming:} \quad d(x, \hat{x}) = \begin{cases} 0, & x = \hat{x} \\ 1, & x \neq \hat{x} \end{cases} \qquad\qquad \text{squared error:} \quad d(x, \hat{x}) = (x - \hat{x})^2

The distortion between sequences is the average distortion of their elements.

Rate Distortion Codes

A (2nR,n)(2^{nR}, n) rate distortion code consists of

  • an encoder fn:Xn→{1,2,…,2nR}f_n : \mathcal{X}^n \to \{1, 2, \ldots, 2^{nR}\},
  • a decoder gn:{1,2,…,2nR}→X^ng_n : \{1, 2, \ldots, 2^{nR}\} \to \hat{\mathcal{X}}^n.

The codebook is gn(1),gn(2),…g_n(1), g_n(2), \ldots and the assignment regions are fn−1(1),fn−1(2),…f_n^{-1}(1), f_n^{-1}(2), \ldots. The distortion of the code is

D=E[d(Xn,gn(fn(Xn)))]D = E\big[d\big(X^n, g_n(f_n(X^n))\big)\big]

(R,D)(R, D) is achievable if there is a sequence of (2nR,n)(2^{nR}, n) codes with lim⁡n→∞E[d(Xn,gn(fn(Xn)))]≤D\lim_{n \to \infty} E\big[d\big(X^n, g_n(f_n(X^n))\big)\big] \le D. The rate distortion region is the closure of the set of achievable (R,D)(R, D).