Rate-Distortion, Lossy Compression, and the Shannon Lower Bound¶

Job: develop the rate-distortion function $R(D)$, the Shannon lower bound, the Gaussian $R(D)$ / reverse water-filling, the successive refinement, and the strong converse / finite-blocklength — with the Gaussian $R(D)=\frac12\log(\sigma^2/D)$ / reverse water-filling as the worked example.

Core¶

The rate-distortion function $R(D)$¶

The $R(D)=\min_{p(\hat x|x):\mathbb{E}d(x,\hat x)\le D}I(X;\hat X)$ (the min over the test channels, the optimization).

$R(D)$ / Shannon lower bound / converse	Description
$R(D)$	$\min_{p(\hat x
Shannon lower bound	$R(D)\ge H(X)-h(D)$ (the lower, the Shannon)
Converse / achievability	the converse the $R(D)$ the lower, the achievability the random coding

The Gaussian rate-distortion¶

Gaussian $R(D)$ / MSE / reverse water-filling	Description
Gaussian $R(D)$	$R(D)=\frac12\log(\sigma^2/D)$ for $D<\sigma^2$ (the MSE $d=(x-\hat x)^2$, the Shannon)
MSE	$d(x,\hat x)=(x-\hat x)^2$ (the mean-square error)
Reverse water-filling	the vector Gaussian the $R(D)=\sum\frac12\log(\sigma_i^2/D_i)^+$ with $\sum D_i=D$ (the water-filling, the Cover)

Vector / successive refinement	Description
Vector Gaussian	the independent components, the reverse water-filling the allocation
Successive refinement	the $R(D)$ the scalable / the successive (the Equitz–Cover, the progressive)

The lossy source coding and the strong converse¶

Strong converse / finite-blocklength / dispersion	Description
Strong converse	$R<R(D)$ the error $\to1$ (the strong, the $R>R(D)$ the error $\to0$)
Finite-blocklength	the Polyanskiy–Poor–Verdú: the $R(D)$ the finite, the dispersion
Dispersion	the finite-blocklength the dispersion (the PPV)

See it¶

Gaussian $R(D)=\frac12\log(\sigma^2/D)$ and the reverse water-filling. The Gaussian $X\sim\mathcal{N}(0,\sigma^2)$, the MSE $d=(x-\hat x)^2$, the $R(D)=\min I(X;\hat X)$ s.t. $\mathbb{E}(X-\hat X)^2\le D$. The optimal test channel: $\hat X=(1-D/\sigma^2)X$ (the scaling, the MMSE), the $I(X;\hat X)=\frac12\log(\sigma^2/D)$ (the Shannon). The reverse water-filling: the vector Gaussian $(X_1,\dots,X_n)$ with variances $\sigma_i^2$, the $R(D)=\sum\frac12\log(\sigma_i^2/D_i)^+$ with $\sum D_i=D$ the water-filling (the $D_i=\min(\sigma_i^2,\lambda)$ the level $\lambda$). The key point: the Gaussian $R(D)$ the $\frac12\log(\sigma^2/D)$, the reverse water-filling the vector the allocation.

Check¶

Show that the Gaussian $R(D)=\frac12\log(\sigma^2/D)$ via the MMSE test channel, and explain the reverse water-filling.

The Gaussian $X\sim\mathcal{N}(0,\sigma^2)$, the MSE. The test channel: $\hat X=(1-D/\sigma^2)X+Z$ ($Z$ independent), the $\mathbb{E}(X-\hat X)^2=D$ (the MMSE), the $I(X;\hat X)=\frac12\log(\sigma^2/D)$ (the Shannon). The reverse water-filling: the vector $(X_1,\dots,X_n)$ with $\sigma_i^2$, the $R(D)=\sum\frac12\log(\sigma_i^2/D_i)^+$ with $\sum D_i=D$, the $D_i=\min(\sigma_i^2,\lambda)$ (the water-filling, the $\lambda$ the level, the $D_i$ the allocation). So the Gaussian $R(D)$ the $\frac12\log(\sigma^2/D)$, the reverse water-filling the vector.

Explain the Shannon lower bound $R(D)\ge H(X)-h(D)$ and the achievability.

The Shannon lower bound: the $R(D)=\min I(X;\hat X)$ s.t. $\mathbb{E}d\le D$, the $I(X;\hat X)=H(X)-H(X|\hat X)\ge H(X)-h(D)$ (the $H(X|\hat X)\le h(D)$ the distortion, the Shannon). The achievability: the random coding (the test channels, the typical), the $R(D)$ the achievable (the $R>R(D)$ the error $\to0$). The converse: the $R(D)$ the lower bound (the Shannon), the achievability the upper (the random coding), the $R(D)$ the tight.

Pitfalls¶

The $R(D)$ the min over test channels (the optimization, the $p(\hat x|x)$) — the $R(D)$ the optimization, the test channels.
The Gaussian the MMSE (the $\hat X=(1-D/\sigma^2)X$ the scaling, the $I=\frac12\log(\sigma^2/D)$) — the Gaussian the MMSE, the explicit.
The reverse water-filling the vector (the $D_i=\min(\sigma_i^2,\lambda)$ the allocation, the $\sum D_i=D$) — the vector the water-filling, the independent the components.
The successive refinement (the $R(D)$ the scalable, the Equitz–Cover) — the progressive the scalable, the refinement the layered.
The strong converse (the $R<R(D)$ the error $\to1$, the strong) — the strong converse, the finite-blocklength the PPV.

Refs¶

Shannon, "Coding theorems for a discrete source with a fidelity criterion" (1959); the $R(D)$
Cover, Information Theory (the reverse water-filling); Equitz–Cover, "Successive refinement" (1991)
Polyanskiy–Poor–Verdú, "Minimum channel dispersion" (2010); the finite-blocklength

Next¶

IT index · Foundations · Network Information · Finite-Blocklength & Dispersion · Quantum & Large Deviations · Optimization

Gaussian \(R(D)\) / MSE / reverse water-filling	Description
Gaussian \(R(D)\)	\(R(D)=\frac12\log(\sigma^2/D)\) for \(D<\sigma^2\) (the MSE \(d=(x-\hat x)^2\), the Shannon)
MSE	\(d(x,\hat x)=(x-\hat x)^2\) (the mean-square error)
Reverse water-filling	the vector Gaussian the \(R(D)=\sum\frac12\log(\sigma_i^2/D_i)^+\) with \(\sum D_i=D\) (the water-filling, the Cover)