Thomas M. Cover, Joy A. Thomas. Elements of information theory

Подождите немного. Документ загружается.

SUMMARY 335

as a double maximization using Lemma 10.8.1,

C = max

q(x|y)

max

r(x)



r(x)p(y|x)log

q(x|y)

r(x)

. (10.145)

In this case, the Csisz

ar–Tusnady algorithm becomes one of alternating

maximization—we start with a guess of the maximizing distribution r(x)

and ﬁnd the best conditional distribution, which is, by Lemma 10.8.1,

q(x|y) =

r(x)p(y|x)



r(x)p(y|x)

. (10.146)

For this conditional distribution, we ﬁnd the best input distribution

r(x) by solving the constrained maximization problem with Lagrange

multipliers. The optimum input distribution is

r(x) =



(

q(x|y)

)

p(y|x)





(

q(x|y)

)

p(y|x)

, (10.147)

which we can use as the basis for the next iteration.

These algorithms for the computation of the channel capacity and the

rate distortion function were established by Blahut [65] and Arimoto [25]

and the convergence for the rate distortion computation was proved by

Csisz

ar [139]. The alternating minimization procedure of Csisz

ar and Tus-

nady can be specialized to many other situations as well, including the EM

algorithm [166], and the algorithm for ﬁnding the log-optimal portfolio

for a stock market [123].

SUMMARY

Rate distortion. The rate distortion function for a source X ∼ p(x)

and distortion measure d(x, ˆx) is

R(D) = min

p( ˆx|x):



(x, ˆx)

p(x)p(ˆx|x)d(x,ˆx)≤D

I(X;

X), (10.148)

where the minimization is over all conditional distributions p( ˆx|x) for

which the joint distribution p(x, ˆx) = p(x)p( ˆx|x) satisﬁes the expected

distortion constraint.

336 RATE DISTORTION THEORY

Rate distortion theorem. If R>R(D), there exists a sequence of

codes

) with the number of codewords |

(·)|≤2

with

Ed(X

)) → D.IfR<R(D), no such codes exist.

Bernoulli source. For a Bernoulli source with Hamming distortion,

R(D) = H(p)− H(D). (10.149)

Gaussian source. For a Gaussian source with squared-error distortion,

R(D) =

log

. (10.150)

Source–channel separation. A source with rate distortion R(D) can

be sent over a channel of capacity C and recovered with distortion D

if and only if R(D) < C.

Multivariate Gaussian source. The rate distortion function for a mul-

tivariate normal vector with Euclidean mean-squared-error distortion is

given by reverse water-ﬁlling on the eigenvalues.

PROBLEMS

10.1 One-bit quantization of a single Gaussian random variable.Let

X ∼

N(0,σ

) and let the distortion measure be squared error.

Here we do not allow block descriptions. Show that the optimum

reproduction points for 1-bit quantization are ±



σ and that the

expected distortion for 1-bit quantization is

π−2

. Compare this

with the distortion rate bound D = σ

−2R

for

R = 1.

10.2 Rate distortion function with inﬁnite distortion. Find the rate dis-

tortion function R(D) = min I(X;

X) for X ∼ Bernoulli (

) and

distortion

d(x, ˆx) =







0,x= ˆx

1,x= 1, ˆx = 0

∞,x= 0, ˆx = 1.

PROBLEMS 337

10.3 Rate distortion for binary source with asymmetric distortion .Fix

p( ˆx|x) and evaluate I(X;

X) and D for

X ∼ Bernoulli





d(x, ˆx) =



0 a

b 0



(The rate distortion function cannot be expressed in closed form.)

10.4 Properties of R(D). Consider a discrete source X ∈

X =

{1, 2,...,m} with distribution p

,...,p

and a distortion

measure d(i,j).LetR(D) be the rate distortion function for

this source and distortion measure. Let d



(i, j ) = d(i,j) − w

a new distortion measure, and let R



(D) be the corresponding

rate distortion function. Show that R



(D) = R(D + w),where

w =



, and use this to show that there is no essential loss of

generality in assuming that min

ˆx

d(i, ˆx) = 0 (i.e., for each x ∈ X,

there is one symbol ˆx that reproduces the source with zero dis-

tortion). This result is due to Pinkston [420].

10.5 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; that is,

d(x, ˆx) =



0ifx = ˆx,

1ifx = ˆx.

10.6 Shannon lower bound for the rate distortion function.Consider

a source X with a distortion measure d(x, ˆx) that satisﬁes the

following property: All columns of the distortion matrix are per-

mutations of the set {d

,...,d

}. Deﬁne the function

φ(D) = max



i=1

≤D

H(p). (10.151)

The Shannon lower bound on the rate distortion function [485]

is proved by the following steps:

(a) Show that φ(D) is a concave function of D.

(b) Justify the following series of inequalities for I(X;

X) if

Ed(X,

X) ≤ D,

I(X;

X) = H(X)− H(X|

X) (10.152)

338 RATE DISTORTION THEORY

= H(X)−



ˆx

p( ˆx)H(X|

X = ˆx) (10.153)

≥ H(X)−



ˆx

p( ˆx)φ(D

ˆx

) (10.154)

≥ H(X)− φ





ˆx

p( ˆx)D

ˆx



(10.155)

≥ H(X)− φ(D), (10.156)

where D

ˆx



p(x|ˆx)d(x, ˆx).

R(D) ≥ H(X)− φ(D), (10.157)

which is the Shannon lower bound on the rate distortion func-

tion.

(d) If, in addition, we assume that the source has a uniform

distribution and that the rows of the distortion matrix are per-

mutations of each other, then R(D) = H(X)− φ(D) (i.e., the

lower bound is tight).

10.7 Erasure distortion. Consider X ∼ Bernoulli (

), and let the dis-

tortion measure be given by the matrix

d(x, ˆx) =



01∞

∞ 10



. (10.158)

Calculate the rate distortion function for this source. Can you

suggest a simple scheme to achieve any value of the rate distortion

function for this source?

10.8 Bounds on the rate distortion function for squared-error distortion.

For the case of a continuous random variable X with mean zero

and variance σ

and squared-error distortion, show that

h(X) −

log(2πeD) ≤ R(D) ≤

log

. (10.159)

For the upper bound, consider the following joint distribution:

PROBLEMS 339

−

X X

(

−

Are Gaussian random variables harder or easier to describe than

other random variables with the same variance?

10.9 Properties of optimal rate distortion code. A good (R, D) rate

distortion code with R ≈ R(D) puts severe constraints on the rela-

tionship of the source X

and the representations

. Examine the

chain of inequalities (10.58–10.71) considering the conditions for

equality and interpret as properties of a good code. For example,

equality in (10.59) implies that

is a deterministic function

of X

10.10 Rate distortion. Find and verify the rate distortion function R(D)

for X uniform on

X ={1, 2,...,2m} and

d(x, ˆx) =



1forx − ˆx odd,

0forx − ˆx even,

where

X is deﬁned on

X ={1, 2,...,2m}.(Youmaywishtouse

the Shannon lower bound in your argument.)

10.11 Lower bound.Let

X ∼

−x



∞

−∞

−x

and



−x



−x

= c.

Deﬁne g(a) = max h(X) over all densities such that EX

≤ a.

Let R(D) be the rate distortion function for X with the density

above and with distortion criterion d(x, ˆx) = (x − ˆx)

. Show that

R(D) ≥ g(c) −g(D).

340 RATE DISTORTION THEORY

10.12 Adding a column to the distortion matrix.LetR(D) be the rate

distortion function for an i.i.d. process with probability mass func-

tion p(x) and distortion function d(x, ˆx), x ∈

X,ˆx ∈

X.Now

suppose that we add a new reproduction symbol ˆx

X with asso-

ciated distortion d(x, ˆx

), x ∈ X. Does this increase or decrease

R(D), and why?

10.13 Simpliﬁcation. Suppose that

X ={1, 2, 3, 4},

p(i) =

, i = 1, 2, 3, 4, and X

,... are i.i.d. ∼ p(x).The

distortion matrix d(x, ˆx) is given by

1234

1 0011

0011

1100

(a) Find R(0), the rate necessary to describe the process with

zero distortion.

(b) Find the rate distortion function R(D). There are some irrel-

evant distinctions in alphabets

X and

X, which allow the

problem to be collapsed.

i = 1, 2, 3, 4. What is R(D)?

10.14 Rate distortion for two independent sources. Can one compress

two independent sources simultaneously better than by compress-

ing the sources individually? The following problem addresses this

question. Let {X

} be i.i.d. ∼ p(x) with distortion d(x, ˆx) and rate

distortion function R

(D). Similarly, let {Y

} be i.i.d. ∼ p(y) with

distortion d(y, ˆy) and rate distortion function R

(D). Suppose we

now wish to describe the process {(X

)} subject to distortions

Ed(X,

X) ≤ D

and Ed(Y,

Y) ≤ D

. Thus, a rate R

X,Y

)

is sufﬁcient, where

X,Y

) = min

p( ˆx, ˆy|x,y):Ed(X,

X)≤D

,Ed(Y,

Y)≤D

I(X,Y;

Y).

Now suppose that the {X

} process and the {Y

} process are inde-

pendent of each other.

(a) Show that

X,Y

) ≥ R

) + R

PROBLEMS 341

(b) Does equality hold?

Now answer the question.

10.15 Distortion rate function.Let

D(R) = min

p( ˆx|x):I(X;

X)≤R

Ed(X,

X) (10.160)

be the distortion rate function.

(a) Is D(R) increasing or decreasing in R?

(b) Is D(R) convex or concave in R?

the converse by focusing on D(R).LetX

,...,X

i.i.d. ∼ p(x). Suppose that one is given a (2

,n) rate dis-

tortion code X

→ i(X

) →

(i(X

)), with i(X

) ∈ 2

and suppose that the resulting distortion is D = Ed(X

(i(X

))). We must show that D ≥ D(R). Give reasons for the

following steps in the proof:

D = Ed(X

(i(X

))) (10.161)

(a)

= E



i=1

d(X

) (10.162)

(b)



i=1

Ed(X

) (10.163)

(c)

≥



i=1



I(X

;

)

(10.164)

(d)

≥ D





i=1

I(X

;

)



(10.165)

(e)

≥ D



I(X

;

)



(10.166)

(f)

≥ D(R). (10.167)

10.16 Probability of conditionally typical sequences. In Chapter 7 we

calculated the probability that two independently drawn sequences

and Y

are weakly jointly typical. To prove the rate distor-

tion theorem, however, we need to calculate this probability when

342 RATE DISTORTION THEORY

one of the sequences is ﬁxed and the other is random. The tech-

niques of weak typicality allow us only to calculate the average

set size of the conditionally typical set. Using the ideas of strong

typicality, on the other hand, provides us with stronger bounds

that work for all typical x

sequences. We outline the proof that

Pr{(x

) ∈ A

∗(n)



}≈2

−nI (X;Y)

for all typical x

. This approach

was introduced by Berger [53] and is fully developed in the book

by Csisz

ar and K

orner [149].

Let (X

) be drawn i.i.d. ∼ p(x, y). Let the marginals of X and

Y be p(x) and p(y), respectively.

(a) Let A

∗(n)



be the strongly typical set for X. Show that

∗(n)



nH (X)

. (10.168)

(Hint: Theorems 11.1.1 and 11.1.3.)

(b) The joint type of a pair of sequences (x

) is the proportion

of times (x

) = (a, b) in the pair of sequences:

(a, b) =

N(a,b|x

) =



i=1

I(x

= a, y

= b).

(10.169)

The conditional type of a sequence y

given x

is a stochastic

matrix that gives the proportion of times a particular element

Y occurred with each element of X in the pair of sequences.

Speciﬁcally, the conditional type V

(b|a) is deﬁned as

(b|a) =

N(a,b|x

)

N(a|x

)

. (10.170)

Show that the number of conditional types is bounded by (n +

|X ||Y|

∈ Y

with conditional type V with

respect to a sequence x

is called the conditional type class

). Show that

(n + 1)

|X ||Y|

nH (Y |X)

≤|T

)|≤2

nH (Y |X)

. (10.171)

(d) The sequence y

∈ Y

is said to be -strongly conditionally

typical with the sequence x

with respect to the conditional

distribution V(·|·) if the conditional type is close to V .The

conditional type should satisfy the following two conditions:

PROBLEMS 343

(i) For all (a, b) ∈ X × Y with V(b|a) > 0,



N(a,b|x

) − V(b|a)N(a|x

)



≤



|Y|+1

(10.172)

(ii) N(a,b|x

) = 0forall(a, b) such that V(b|a) = 0.

The set of such sequences is called the conditionally typi-

cal set and is denoted A

∗(n)



(Y |x

). Show that the number

of sequences y

that are conditionally typical with a given

∈ X

is bounded by

(n + 1)

|X ||Y|

n(H (Y |X)−

)

≤|A

∗(n)



(Y |x

≤ (n + 1)

|X ||Y|

n(H (Y |X)+

)

, (10.173)

where 

→ 0as → 0.

(e) For a pair of random variables (X, Y ) with joint distribution

p(x, y),the-strongly typical set A

∗(n)



is the set of sequences

) ∈ X

× Y

satisfying

(i)



N(a,b|x

) − p(a, b)





|X||Y|

(10.174)

for every pair (a, b) ∈

X × Y with p(a, b) > 0.

(ii) N(a,b|x

) = 0forall(a, b) ∈ X × Y with

p(a, b) = 0.

The set of -strongly jointly typical sequences is called the

-strongly jointly typical set and is denoted A

∗(n)



(X, Y ).Let

(X, Y ) be drawn i.i.d. ∼ p(x,y).Foranyx

such that there

exists at least one pair (x

) ∈ A

∗(n)



(X, Y ),thesetofse-

quences y

such that (x

) ∈ A

∗(n)



satisﬁes

(n + 1)

|X ||Y|

n(H (Y |X)−δ())

≤|{y

: (x

) ∈ A

∗(n)



≤ (n + 1)

|X ||Y|

n(H (Y |X)+δ())

, (10.175)

where δ() → 0as → 0. In particular, we can write

n(H (Y |X)−

)

≤|{y

: (x

) ∈ A

∗(n)



}| ≤ 2

n(H (Y |X)+

)

(10.176)

344 RATE DISTORTION THEORY

where we can make 

arbitrarily small with an appropriate

choice of  and n.

(f) Let Y

,...,Y

be drawn i.i.d. ∼



p(y

).Forx

∈ A

∗(n)



the probability that (x

) ∈ A

∗(n)



is bounded by

−n(I (X;Y)+

)

≤ Pr((x

) ∈ A

∗(n)



) ≤ 2

−n(I (X;Y)−

)

(10.177)

where 

goes to 0 as  → 0andn →∞.

10.17 Source–channel separation theorem with distortion.LetV

,...,V

be a ﬁnite alphabet i.i.d. source which is encoded

as a sequence of n input symbols X

of a discrete memoryless

channel. The output of the channel Y

is mapped onto the recon-

struction alphabet

= g(Y

).LetD = Ed(V

) =



i=1

Ed(V

) be the average distortion achieved by this combined

source and channel coding scheme.

Channel Capacity

(

)

(a) Show that if C>R(D),whereR(D) is the rate distortion

function for V , it is possible to ﬁnd encoders and decoders

that achieve a average distortion arbitrarily close to D.

(b) (Converse) Show that if the average distortion is equal to D,

the capacity of the channel C must be greater than R(D).

10.18 Rate distortion.Letd(x, ˆx) be a distortion function. We have

a source X ∼ p(x). Let R(D) be the associated rate distortion

function.

(a) Find

R(D) in terms of R(D), where

R(D) is the rate

distortion function associated with the distortion

d(x, ˆx) =

d(x, ˆx) + a for some constant a>0. (They are not equal.)

(b) Now suppose that d(x, ˆx) ≥ 0forallx, ˆx and deﬁne a new

distortion function d

∗

(x, ˆx) = bd(x, ˆx), where b is some num-

ber ≥ 0. Find the associated rate distortion function R

∗

(D) in

terms of R(D).

) and d(x, ˆx) = 5(x − ˆx)

+ 3. What is

R(D)?