1.converse of rate distortion theorem.

Definition:   

the proof based on the following facts:

,which is a MC.

(a)  is at most

(b) data processing inequality

(c)definition of rate distortion function

(d)Jensen's inequality

2. Source&Channel separation theorem with distortion.

Let  be a finite alphabet i.i.d. source which is a

encoded as a sequence of n input symbols  of a discrete

memoryless channel with capacity C. The output of the channel  is

mapped onto the  reconstruction alphabet  . Let

be the

average distortion achieved by this combined source and channel

coding scheme. Then the distortion is achieved iff

3. Particular rate-distortion prolbems

Bernoulli(p) soucre with squared-error distortion.

(it is a template to compute R(D)) 

4. Compute rate-distortion functions

1. A simple Case.

Given two convex sets A and B in , how to find the minimun distance between them:

Algotithm: we would take any point , and find the   that is closest to it. Then fix this y and find the closest point in A. Repeating this process to minimum distance dereases at each stage.

2. 

,where .

3. .

,which can be obtained directly by  the fact of (2)

4.

,where A is the set of all joint distribution with marginal p(x) satisfy the distortion constraints.

 B is the set of product distributions  with arbitrary