Rate Distortion Theorem

Theorem (Converse Part)

For any n1n\ge1 and source channel code (fn,gn)(f_{n},g_{n}) we have if E[d(Xn,gn(fn(Xn)))]DE[d(X^{n},g_{n}(f_{n}(X^{n})))]\le Dthen the rate RR of (fn,gn)(f_{n},g_{n}) satisfies RR(D)R\ge R(D)i.e. the Rate Distortion Function is the lower bound for all rates satisfying the distortion constraint.

Lemma (R(D)R(D) convex in DD)

The rate distortion function R(D)R(D) is a non-increasing, convex function of DD.

Theorem (Achievability of the Rate Distortion Function (Forward Part))

For any D0D\ge0 and δ>0\delta>0, if nn large enough, then (fn,gn)\exists(f_{n},g_{n}) with distortion E[d(Xn,gn(fn(Xn)))]<D+δE[d(X^{n},g_{n}(f_{n}(X^{n})))]<D+\delta and rate RR such that R<R(D)+δR<R(D)+\delta