[SOLVED] Ee276 homework #8 p0

1. Shannon lower bound.
Let X be a continuous random variable with mean zero and variance σ2. R(D) is the corresponding rate-distortion function for mean-squared distortion.
(a) Show the lower bound:
.
(b) Using the joint distribution shown in Figure 1, show the upper bound on R(D):
(1)
Are Gaussian random variables harder or easier to describe in bits – in the sense of achieving small mean squared error distortion – than other random variables with the same variance?
Z ∼ N 0, σDσ2−2D 2
σ −D σ2
‘$?
&% ?u
X – – -Xˆ
Figure 1: Joint distribution for upper bound on rate distortion function. The circle with the dot represents multiplication.
2. Rate distortion for uniform source with Hamming distortion.
Consider a source X uniformly distributed on the set {1,2,…,m}. Find the rate distortion function for this source with Hamming distortion, i.e.,

via the following steps:
(a) Argue that R(D) = 0 when .
(b) Show that for 1) for any joint distribution (X,Xˆ) satisfying the distortion constraint D. Hint: Fano’s inequality.
(c) Find distribution p(xˆ|x) that achieves the above lower bound when 0 . Hint:
Consider the form below.

(d) Use the above parts to write down the rate-distortion function R(D) for D ≥ 0.
3. Rate distortion for two independent sources. Can one simultaneously compress two independent sources better than by compressing the sources individually? This problem addresses this question. Let {Xi} be iid ∼ p(x) with distortion d(x,xˆ) and rate distortion function RX(D). Similarly, let {Yi} be iid ∼ p(y) with distortion d(y,yˆ) and rate distortion function RY (D).
Suppose the {Xi} process and the {Yi} process are independent of each other.
Suppose we now wish to describe the process {(Xi,Yi)} subject to distortions E[d(X,Xˆ)] ≤
D1 and E[d(Y,Yˆ)] ≤ D2. Thus a rate RX,Y (D1,D2) is sufficient, where

(a) Show
RX,Y (D1,D2) ≥ RX(D1) + RY (D2).
(b) Does equality hold?
4. Distortion-rate function. Let
D(R) = min E[d(X,Xˆ)] (2)
p(xˆ|x):I(X;Xˆ)≤R
be the distortion rate function.
(a) Is D(R) increasing or decreasing in R?
(b) Is D(R) convex or concave in R?
(c) Let X1,X2,…,Xn be i.i.d. ∼ p(x). Suppose one is given a code () with

We want to show that). Give reasons for the following steps in the proof:
(3)
(4)
(5)
!
(6)
(7)
(8)