1

Successive Refinement of Abstract Sources

arXiv:1707.09567v1 [cs.IT] 29 Jul 2017

Victoria Kostina, Ertem Tuncel

Abstract—In successive refinement of information, the decoder
refines its representation of the source progressively as it receives
more encoded bits. The rate-distortion region of successive
refinement describes the minimum rates required to attain the
target distortions at each decoding stage. In this paper, we derive
a parametric characterization of the rate-distortion region for
successive refinement of abstract sources. Our characterization
extends Csiszár’s result [2] to successive refinement, and generalizes a result by Tuncel and Rose [3], applicable for finite alphabet
sources, to abstract sources. This characterization spawns a family of outer bounds to the rate-distortion region. It also enables
an iterative algorithm for computing the rate-distortion region,
which generalizes Blahut’s algorithm to successive refinement.
Finally, it leads a new nonasymptotic converse bound. In all the
scenarios where the dispersion is known, this bound is secondorder optimal.
In our proof technique, we avoid Karush-Kuhn-Tucker conditions of optimality, and we use basic tools of probability theory.
We leverage the Donsker-Varadhan lemma for the minimization
of relative entropy on abstract probability spaces.

where the maximization is over α(x) ≥ 0 and λ ≥ 0 satisfying
the constraint


exp (−λd(X, y))
E
≤ 1 ∀y ∈ Y.
(5)
α(X)
Furthermore, the maximizer is given by
λ⋆ = −R′ (d)
⋆

(6)
⋆

⋆

α (x) = E [exp(−λ d(x, Y ))] ,

(7)

where the expectation is with respect to the unconditional
distribution of Y ⋆ . The optimal distribution satisfies
dPY ⋆ |X=x
exp(−λ⋆ d(x, y))
(y) =
.
dPY ⋆
α⋆ (x)

(8)

dP
denotes the Radon-Nykodym derivative; if P
In (8), dQ
and Q are both discrete / continuous probability distributions,
dP
dQ is simply the ratio of corresponding probability mass
Index Terms—Successive refinement, rate-distortion theory, / density functions. Theorem 1 applies to the much more
single-shot analysis, d-tilted information, Blahut algorithm, congeneral setting of abstract probability spaces. It was Csiszár
verse, dispersion.
[2] who formulated and proved Theorem 1 in this generality.1
For finite alphabet sources, the parametric representation of
R(d) is contained in Shannon’s paper [4]; Gallager’s [5,
I. I NTRODUCTION
Theorem 9.4.1] and Berger’s [6] texts include the parametric
For a source random variable X ∈ X and a distortion
representation of R(d) for discrete and continuous sources.
measure d : X × Y 7→ [0, +∞], where X and Y are abstract
The parametric representation of R(d) plays a key role in
sets (source and reproduction alphabets), the classical inforthe Blahut algorithm [7] for computing the rate-distortion funcmational rate-distortion function is defined as the following
tion. For difference distortion measures, d(x, y) = d(x − y),
minimal mutual information quantity:
a certain choice of (α(x), λ) in (4) leads to the Shannon
lower
bound [4], a particularly simple, explicit lower bound
I(X; Y )
(1)
R(d) ,
inf
PY |X : X 7→Y
to
the
rate-distortion
function, which offers nice intuitions and
E[d(X,Y )]≤d
which is known to be tight in the limit d ↓ 0. Leveraging
This convex optimization problem rarely has an explicit solu- Theorem 1, a generalization of Shannon’s lower bound to
tion. The following result provides a parametric representation: abstract probability spaces was recently proposed [8], [9].
Theorem 1 (Parametric representation of R(d) [2]). Assume Furthermore, given (PX , d), the d-tilted information, defined
for each realization x ∈ X through the solution to (4) as
that the following conditions are met.
d (x, d) , − log α⋆ (x) − λ⋆ d,
(9)
(A) dmin < d < dmax , where

dmin , inf {d : R(d) < ∞}

(2)

dmax , inf {d : R(d) is constant on (dmax , ∞)} (3)
(B) There exists a transition probability kernel PY ⋆ |X that
attains the infimum in (1).
Then, it holds that
R(d) = max {−E [log α(X)] − λd}
α(x),λ

(4)

V. Kostina (e-mail: vkostina@caltech.edu) is with California Institute of
Technology. E. Tuncel (e-mail: ertem.tuncel@ucr.edu) is with University of
California, Riverside. This work was supported in part by the National Science
Foundation (NSF) under Grant CCF-1566567. It was presented in part at
ISIT 2017 [1].

governs the nonasymptotic fundamental limits of lossy compression [10], where the subscript d emphasizes the distortion
measure used.
In this paper, we state and prove a generalization of Theorem 1 to successive refinement of abstract alphabet sources. If
the source is successively refinable, that is, if optimal successive coding achieves the respective rate-distortion functions at
each decoding stage, our result recovers the representation in
Theorem 1. Our characterization extends a prior finite alphabet
result by Tuncel and Rose [3, Theorem 4] to abstract probability spaces. Our general setting necessitates the use of the
1 Even more generally, Csiszár [2] showed that (4) continues to hold even if
the infimum in (1) is not attained by any conditional probability distribution.

2

mathematical tools fundamentally different from the standard representation of the boundary of the set in (10):
convex optimization tools (Karush-Kuhn-Tucker conditions)
R2 (d1 , d2 , R1 ) , inf {R2 : (d1 , d2 , R1 , R2 ) satisfy (10)} .
that can be used to solve the finite alphabet case, as carried
(11)
out in [3]. We leverage the Donsker-Varadhan characterization
of the minimum relative entropy, and, to show the necessary Henceforth, we refer to the function R2 (d1 , d2 , R1 ) : R3+ 7→
optimality conditions, we compare a tentative solution to a R+ as the second stage rate-distortion function. It represents
the minimum asymptotically achievable total rate compatible
perturbation by a carefully selected auxiliary distribution.
with
rate R1 at the first stage and at-stage distortions d1 , d2 .
The new characterization of rate-distortion function for
For
any
achievable (R1 , R2 , d1 , d2 ), the following bound in
successive refinement on abstract alphabets allows us to identerms
of
the standard rate-distortion function in (1) clearly
tify the key random variable describing the nonasymptotic
holds:
fundamental limits of successive refinement, and to show a
new nonasymptotic converse bound. In all the scenarios where
(12)
R1 ≥ Rd1 (d1 )
the dispersion of successive refinement is known [11], [12],
(13)
R2 ≥ Rd2 (d2 )
this bound is second-order optimal.
The new characterization also enables an iterative algorithm, where Rd1 (·) and Rd2 (·) denote the rate-distortion functions
which can be used to compute an accurate approximation for distortion measures d1 and d2 , respectively. In Fig. 3,
to the rate-distortion function of successive refinement, even (d1 , d2 ) are fixed, and the region of achievable (R1 , R2 ) is
if the source and reproduction alphabets are not discrete. greyed out; R2 (d1 , d2 , R1 ) is its boundary drawn in red. If
We prove that when initialized appropriately, the algorithm the point (Rd1 (d1 ), Rd2 (d2 )) is attainable, the source is said
converges to
 the true value of rate-distortion function with to be successively refinable [16] at (d1 , d2 ).
speed O k1 , where k is the iteration number. The algorithm
R2
can be viewed as a generalization of Blahut’s algorithm [7]
and its extension to successive refinement by Tuncel and Rose
[3] for discrete alphabets. Methods to compute the capacity
and rate-distortion functions for continuous alphabets were
achievable (R1 , R2 )
proposed in [13] and [14].
The rest of the paper is organized as follows. The main
result of the paper characterizing the abstract rate-distortion
function (Theorem 2) is presented in Section II. The main
Rd2 (d2 )
nonasymptotic converse result, Theorem 3, is shown in Section III. A proof of Theorem 1, which streamlines Csiszár’s
argument [2], is presented in Section IV. The proof of Theorem 2, which leverages the ideas presented in Section IV and
in [3], is presented in Section V. Section VI discusses the
iterative algorithm for computation of rate-distortion function
Rd1 (d1 )
R1
of successive refinement.
Throughout the paper, R+ = [0, +∞) is the positive real Fig. 1. The rate-distortion region for successive refinement, for fixed d1 , d2 .
line; PX -a.e. x stands for ‘almost every x’, i.e. ’except on a Note that if d1 = d2 , and d2 < d1 , then R2 (d1 , d2 , R1 ) = R(d2 ) is
set with total PX measure 0’; PX → PY |X → PY signifies attained at some R1 < ∞.
that PY is the distribution observed at the output of random
Throughout the paper, we assume that the following conditransformation PY |X when the input is distributed according tions are met.
to PX , i.e. PY is the marginal of PX PY |X .
(a) R2 (d1 , d2 , R1 ) is finite in some nonempty region ⊆ R3+ .
(b) There exist transition probability kernels PY1⋆ |X and
PY2⋆ |XY1⋆ that attain the infimum in (11).
II. C HARACTERIZATION OF RATE - DISTORTION FUNCTION
The second stage rate-distortion function R2 (d1 , d2 , R1 )
Consider the source random variable X ∈ X and two is nondecreasing and jointly convex in (d , d , R ) (see
1 2
1
(possibly different) distortion measures d1 : X ×Y1 7→ [0, +∞] Lemma 4 in Section V below). The region of (d , d , R )
1 2
1
and d2 : X × Y1 7→ [0, +∞], quantifying the accuracy of lossy where the constraints are satisfied with equality is defined as
compression at the first and the second stages, respectively. follows.
Rimoldi [15] showed that the distortions (d1 , d2 ) are asymptot3
(14)
ically attainable with rates (R1 , R2 ) at first and second stages Ω , {(d1 , d2 , R1 ) ∈ R+ : ∀(ǫ1 , ǫ2 , ǫ3 ) > 0 :
if and only if
R2 (d1 + ǫ1 , d2 + ǫ2 , R1 + ǫ3 ) < R2 (d1 , d2 , R1 ) < ∞}.
I(X; Y1 ) ≤ R1
I(X; Y1 , Y2 ) ≤ R2

E [d1 (X, Y1 )] ≤ d1
E [d2 (X, Y2 )] ≤ d2 ,

(10)

where here and in the sequel, R2 refers to the total rate at both
stages. It is convenient to consider the following equivalent

In the important special case of d1 = d2 ,
Ω = {(d1 , d2 , R1 ) : R(d1 ) < R1 < R(d2 ), d1 ≤ dmax } , (15)
where dmax is the smallest positive scalar such that R(d) is
constant on (dmax , ∞).

3

To each (d1 , d2 , R1 ) ∈
(λ⋆1 , λ⋆2 , ν1⋆ ) ∈ R3+ such that
h − λ⋆1 d1 − λ⋆2 d2 − ν1⋆ R1

R3+ there corresponds a triplet
for some h ∈ R+ , the hyperplane
is tangent to R2 (d1 , d2 , R1 ) at

(d1 , d2 , R1 ).
Before we state our main result, we present the following
notation. For measurable functions β1 : X 7→ R+ , β2 : X ×
Y1 7→ R+ and nonnegative numbers λ1 , λ2 , ν1 , denote



λ1
d
(X,
y
)
−
λ
d
(X,
y
)
exp − 1+ν
1
1
2
2
2
1

Σ2 (y1 , y2 ) , E 
ν1
β1 (X)β2 (X|y1 ) 1+ν1
(16)



λ1
exp − 1+ν1 d1 (X, y1 )
.
Σ1 (y1 ) , E 
(17)
1
β1 (X)β2 (X|y1 )− 1+ν1

The quantities Σ1 (y1 ) and Σ2 (y1 , y2 ) generalize the expectation on the left side of (5) to successive refinement.
The main result of the paper can now be stated as follows.

Theorem 2 (Parametric representation). Assume that
(d1 , d2 , R1 ) ∈ Ω. The boundary of the rate-distortion region
of successive refinement can be represented as
R2 (d1 , d2 , R1 )


 
1
−
λ
d
−
λ
d
−
ν
R
= max E log
1 1
2 2
1 1 ,
β1 (X)1+ν1
(18)
where the maximization is over (β1 (x), ν1 , λ1 , λ2 ) ≥ 0 satisfying, for some β2 (x|y1 ) ≥ 0, the constraints
Σ2 (y1 , y2 ) ≤ 1
Σ1 (y1 ) ≤ 1

(19)
(20)

(21)
(λ⋆1 , λ⋆2 , ν1⋆ ) = −∇R2 (d1 , d2 , R1 )



⋆
1
λ1
⋆
⋆
d
(x,
Y
)
β1⋆ (x) = E β2 (x|Y1⋆ ) 1+ν1 exp −
1
1
1 + ν1⋆
(22)
=



λ⋆
exp − 1+ν1 ⋆ d1 (x, y1 )
dPX|Y1⋆ =y1 (x)
1
=
− 1
⋆
⋆
dPX (x)
β1 (x)β2 (x|y1 ) 1+ν1
dPX|Y1⋆ =y1 ,Y2⋆ =y2
exp(−λ⋆2 d2 (x, y2 ))
(x) =
dPX|Y1⋆ =y2
β2⋆ (x|y1 )

(26)
(27)

If the source is successively refinable at (d1 , d2 ), then the
optimal choice is
ν1

1

β1 (x) = α⋆1 (x) 1+ν1 α⋆2 (x) 1+ν1


λ1
β2 (x|y1 ) = exp − d1 (x, y1 ) f1⋆−1 (x)α⋆2 (x),
ν1
λ1 = −ν1 Rd′ 1 (d1 )
λ2 = −Rd′ 2 (d2 )

(28)
(29)
(30)
(31)

for an arbitrary ν1 > 0, where α⋆1 (·), α⋆2 (·) achieve the
maximum of (4) for {d1 , d1 } and {d2 , d2 }, respectively. It
is easy to verify that in this case, (19) and (20) are satisfied
and the function in (18) equals Rd2 (d2 ) when R1 = Rd1 (d1 ).
If the source is not successively refinable, choosing β1
and β2 as in (28) and (29) leads to an outer bound to the
rate-distortion region in (10) and, as we are about to see in
Corollary 1 below, to a nonasymptotic converse bound.
III. N ONASYMPTOTIC

CONVERSE BOUND

It was shown in [10] that for single stage compression, the
random variable called tilted information, defined in (9), plays
the key role in the corresponding nonasymptotic fundamental
limits. Leveraging the result of Theorem 2, we can define the
tilted information for successive refinement as follows.
Definition 1. Fix PX , d1 , d2 . Tilted information for successive
refinement of x at (d1 , d2 , R1 ) ∈ Ω is defined as
1
− λ⋆1 d1 − λ⋆2 d2 − ν1⋆ R1
β1⋆ (x)
(32)
where (β1⋆ (·), λ⋆1 , λ⋆2 , ν1⋆ ) achieve the maximum in (18).

(x, d1 , d2 , R1 ) , (1 + ν1⋆ ) log

for all (y1 , y2 ) ∈ Y1 × Y2 .
Furthermore, the choice

β2⋆ (x|y1 )

satisfy

E [exp(−λ⋆2 d2 (x, Y2⋆ ))|Y1⋆

= y1 ] .

(23)

achieves the maximum in (18), and the optimal solution in
(21)–(23) satisfies 0 ≤ β1⋆ (x) ≤ 1, 0 ≤ β2⋆ (x|y1 ) ≤ 1, and
Σ2 (y1 , y2 ) ≤ Σ1 (y1 )
≤1

(24)
(25)

for all (y1 , y2 ) ∈ Y1 × Y2 . Equality in (25) is attained for
PY1⋆ -a.e. y1 , and equality in (24) is attained for PY2⋆ |Y1⋆ =y1 a.e. y2 .2 The optimal backward transition probability kernels
2 By the definition of a transition probability kernel, the transition probability
kernels PY2⋆ |X,Y1 =y1 and PY2⋆ |Y1⋆ =y1 are well defined at every y1 (and not
only at PY1⋆ -a.e. y1 ).

If the source is successively refinable at d1 , d2 , then the
tilted information for successive refinement coincides with the
tilted information for single stage compression:
(x, d1 , d2 , Rd1 (d1 )) = d2 (x, d2 ).

(33)

In this section, we show a nonasymptotic converse bound
for successive refinement in terms of tilted information (Theorem 3 below), which generalizes the corresponding result for
one stage compression [10, Th. 7].
Codes for successive refinement are formally defined as
follows. An (M1 , M2 , d1 , d2 , ǫ) code for (PX , d1 , d2 ) is a pair
of encoders
f1 : X 7→ {1, . . . , M1 }

(34)

f2 : X 7→ {1, . . . , ⌊M2 /M1 ⌋}

(35)

and decoders
g1 : {1, . . . , M1 } 7→ Y1

(36)

g2 : {1, . . . , M1 } × {1, . . . , ⌊M2 /M1 ⌋} 7→ Y2

(37)

4

such that

Using elementary probability laws and Lemma 1, write
P[d1 (X, g1 (f1 (X))) ≤ d1 ,
d2 (X, g2 (f1 (X), f2 (X))) ≤ d2 ] ≥ 1 − ǫ.

P [B] = P [B ∩ Ac2 ] + P [B ∩ A2 ]
≤ ǫ + P [B ∩ A2 ∩ F1 ≥ log M1 + γ1 ]
+ P [B ∩ A2 ∩ F1 < log M1 + γ1 ]

(38)

We allow randomized encoders and decoders, in which case
f1 , f2 , g1 , g2 are transition probability kernels rather than deterministic mappings.
The main result of this section is the following.
Theorem 3. For (M1 , M2 , d1 , d2 , ǫ) any code, Then, for all
(γ1 , γ2 ) > 0, it holds that


⋆
ǫ ≥ P (X, d1 , d2 , log M1 ) ≥ log M2 + ν1 γ1 + γ2
− exp(−γ1 ) − exp(−γ2 )

(39)

As we will see shortly in the proof of Theorem 3, the
inequality (39) is naturally generalized as follows:


ǫ ≥ P F ≥ log M2 + ν1 γ1 + γ2 − exp(−γ1 ) − exp(−γ2 )

(40)

where
F , (1 + ν1 ) log

1
− λ1 d1 − λ2 d2 − ν1 log M1
β1 (x)

(41)

F = ν1 (F1 − log M1 ) + F2 ,

(42)

where

≤ ǫ + exp (−γ1 ) + P [A2 ∩ F2 ≥ log M2 + γ2 ] (52)

−

F2 , log

P [F1 ≥ log M1 + γ1 ∩ A1 ]
Z
Z
M1
X
dPX (x)
≤
PW1 |X=x (w) dPY1 |W1 =w (y)
w=1

· 1 {M1 ≤ exp (F1 − γ1 )} 1 {d1 (x, y1 ) ≤ d1 }
(54)
≤ exp (−γ1 ) EPX ×QY1 [exp (F1 ) 1 {d1 (X, Y1 ) ≤ d1 }] (55)
≤ exp (−γ1 ) EQY1 [Σ1 (Y1 )]

(56)

≤ exp (−γ1 )

(57)

where
• (55) follows by upper-bounding PW1 |X=x (w) ≤ 1, and
1 {M ≤ exp (F1 − γ1 )} ≤

(43)

ν1

λ1
β2 (X|Y1 ) 1+ν1
d1 − λ2 d2 .
−
β1 (X)
1 + ν1

exp (−γ1 )
exp (F1 ) ; (58)
M1

(57) is due to (20).
We proceed to show (48). We have, for any γ2 ≥ 0

•

(44)

Lemma 1, presented next, will be instrumental in the proof
of Theorem 3.

A1 , {d1 (X, Y1 ) ≤ d1 }

(45)

A2 , A1 ∩ {d2 (X, Y2 ) ≤ d2 } ,

(46)

(47)

P [F2 ≥ log M2 + γ2 ∩ A2 ] ≤ exp(−γ2 )

(48)

Proof of Theorem 3. We will show (40) using Lemma 1. We
need to bound the probability of the event
(49)

(59)



(60)

w ,w

1
2

· E 1 {M2 ≤ exp (F2 − γ2 )}

· 1 {A2 } |X = x, W1 = w1 , W2 = w2

≤ exp (−γ2 ) EPX ×QY1 Y2 [exp (F2 ) 1 {A2 }]

where Y1 = g1 (f1 (X)) and Y2 = g2 (f1 (X), f2 (X))). It holds
that, for all (γ1 , γ2 ) > 0
P [F1 ≥ log M1 + γ1 ∩ A1 ] ≤ exp(−γ1 )

P [F2 ≥ log M2 + γ2 ∩ A2 ]
Z
X
PW1 ,W2 |X=x (w1 , w2 )
≤
dPX (x)
x∈X

Lemma 1. Fix an arbitrary (M1 , M2 , d1 , d2 , ǫ) code
(f1 , f2 , g1 , g2 ). Denote the successful decoding events

B , {F ≥ log M2 + ν1 γ1 + γ2 } .

(53)

Proof of Lemma 1. We employ Theorem 2 similar to how
Theorem 1 was employed in the proof of [10, Th. 7].
Let the two-stage encoder and decoder be the random
transformations (PW1 |X , PW2 |X,W1 ) and (PY1 |W1 , PY2 |W1 ,W2 ),
where W1 takes values in {1, . . . , M1 }, and W2 takes values
in {1, . . . , ⌊M2 /M1 ⌋}.
Furthermore, introduce the auxiliary distribution QW1 W2 ,
equiprobable on {1, . . . , M1 } × {1, . . . , ⌊M2 /M1 ⌋}, and let
QY1 Y2 be the distribution on Y1 × Y2 that arises after QW1 W2
is passed through the random transformation PY1 Y2 |W1 ,W2
defined by our code, i.e. QW1 W2 → PY1 Y2 |W1 ,W2 → QY1 Y2 .
To show (47), write, for any γ1 ≥ 0

1

λ1
β2 (X|Y1 ) 1+ν1
d1
−
F1 , log
β1 (X)
1 + ν1

(51)

≤ ǫ + exp(−γ1 ) + exp(−γ2 )

x∈X

for any (β1 (·), λ1 , λ2 , ν1 ) ≥ 0 that satisfy (19) and (20), for
some β2 (·|·) ≥ 0.
For a given (M1 , M2 , d1 , d2 , ǫ) code (f1 , f2 , g1 , g2 ), we can
let Y1 = g1 (f1 (X)) and split (41) into two terms (corresponding to the two stages of successive refinement) as follows:

(50)

(61)

≤ exp (−γ2 ) EQY1 Y2 [Σ2 (Y1 , Y2 )]

(62)

≤ exp (−γ2 ) ,

(63)

where
• (61) follows by upper-bounding PW1 ,W2 |X=x (w1 , w2 ) ≤
1, and
1 {M2 ≤ exp (F2 − γ2 )} ≤
•

(63) is due to (19).

exp (−γ2 )
exp (F2 ) ; (64)
M2

5

The following corollary to Lemma 1 is immediate from the
observation that (28)–(31) satisfy (19) and (20).
Corollary 1. Fix an (M1 , M2 , d1 , d2 , ǫ) code. Then, for all
(γ1 , γ2 ) > 0, it holds that


c
P [A1 ] ≥ P d1 (X, d1 ) ≥ log M1 + γ1 − exp(−γ1 ) (65)


c
P [A2 ] ≥ P d2 (X, d2 ) ≥ log M2 + γ2 − exp(−γ2 ). (66)
where d1 and d2 are the d1 - and d2 -tilted informations
(defined in (9)), respectively.
Proof. The inequalities


c
P [A1 ] ≥ P F1 ≥ log M1 + γ1 − exp(−γ1 ),


P [Ac2 ] ≥ P F2 ≥ log M2 + γ2 − exp(−γ2 )

(68)

I(P ) , I(X; Y )

(73)

ρ(P ) , E [d(X, Y )] .

(74)

Lemma 3 ( [2, Lemma 1.1]). R(d) is non-increasing, convex
and
R(d) =
inf
I(P ) dmin < d ≤ dmax .
(75)
P : ρ(P )=d

Let F (λ) denote the maximum of the vertical axis intercepts
of the straight lines of slope −λ which have no point above
the R(d) curve, i.e. using (75) for λ > 0 (see Fig. 2) 3
F (λ) , inf I(P ) + λρ(P ).

(67)

(76)

P

Furthermore, since R(d) is convex and nonincreasing, to each
R

follow immediately from Lemma 1: to show (67), write
P [F1 ≥ log M1 + γ1 ]
(69)
= P [F1 ≥ log M1 + γ1 ∩ Ac1 ] + P [F1 ≥ log M1 + γ1 ∩ A1 ]
≤ P [Ac1 ] + exp(−γ1 ),

Fix source distribution PX . For some transition probability
kernel P = PY |X , put

(70)

feasible I(P )
R(d)

and (68) is analogous.
Now, Corollary 1 follows from the observation that (28)–
(31) satisfy (19) and (20).
Corollary 1 applies whether or not the source is successively refinable. For successively refinable sources, Corollary 1
presents a refinement of Theorem 3.
For successively refinable finite alphabet sources, No et
al. [11] found the dispersion of successive refinement. The
dispersion of non-successively refinable finite alphabet sources
was recently computed in [12]. A straightforward second-order
analysis (along the lines of [10, (103)–(106)]) of the bounds in
Corollary 1 and Theorem 3 recovers the converse parts of the
dispersion results in [11] and [12], respectively, and extends
them to abstract stationary memoryless sources.

F (λ) − λd
d
Fig. 2. Lagrange duality for the rate-distortion problem.

d ≥ dmin , there exists λ ≥ 0 such that the straight line of slope
−λ through (d, R(d)) is tangent to the R(d) curve, and
R(d) , max (F (λ) − λd) .
λ≥0

(77)

Theorem 1 will follow from (77) and Theorem 4 below.
IV. P ROOF

OF

T HEOREM 1

In this section, we revisit the beautiful proof of Theorem 1
by Csiszár [2]. We streamline Csiszár’s argument by using
the the Donsker-Varadhan characterization of the minimum
relative entropy, stated below, which will be also instrumental
in the proof of Theorem 2.
Lemma 2 (Donsker-Varadhan, [17, Lemma 2.1]). Let ρ : X 7→
[−∞,
 +∞] andlet X̄ be a random variable on X such that
E exp −ρ(X̄) < ∞. Then,
D(XkX̄) + E [ρ(X)] ≥ log

1

E exp −ρ(X̄)


(71)

with equality if and only if X has distribution PX ⋆ such that
dPX ⋆ (x) =

exp (−ρ(x))

 dPX̄ (x)
E exp −ρ(X̄)

(72)

We now recall some useful general properties of R(d).

Theorem 4 (Necessary and sufficient conditions for an optimizer [2]). In order for PY ∗ |X to achieve the infimum in (76),
it is necessary and sufficient that
dPY ∗ |X=x =

exp(−λd(x, y))
dPY ∗
α(x)

(78)

where 0 ≤ α(x) ≤ 1 satisfies (5). Furthermore, the choice
α∗ (x) = E [exp(−λd(x, Y ∗ ))]

(79)

satisfies (78) and (5), and for any α(x) ≥ 0 satisfying (5) we
have for all P̃


1
(80)
I(P̃ ) + λρ(P̃ ) ≥ E log
α(X)
with equality if and only if P̃ = PY ∗ |X and α(x) = α∗ (x).
3 The optimization problem in (76) is known as the Lagrangian dual
problem, and the function F (λ) as the Lagrange dual.

6

Proof of Theorem 4. Consider the function
L(PY |X , PȲ ) = D(PY |X kPȲ |PX ) + λE [d(X, Y )]

(81)

= I(X; Y ) + D(Y kȲ ) + λE [d(X, Y )] (82)
≥ I(X, Y ) + λE [d(X, Y )]
(83)
Since equality in (83) holds if and only if PY = PȲ , F (λ)
can be expressed as
F (λ) = inf min L(PY |X , PȲ ).

(84)



ΣȲ (x) , E exp(−λd(x, Ȳ )) .

(85)

PȲ PY |X

Denote
Since d(x, y) ≥ 0, we have 0 ≤ ΣȲ (x) ≤ 1 , and Lemma 2
applies to conclude that equality in
D(PY |X=x kPȲ ) + λE [d(x, Y )|X = x] ≥ log

1
, (86)
ΣȲ (x)

is achieved if and only if PY |X=x = PȲ ∗ |X=x , where
PȲ ∗ |X=x is determined from
log

dPȲ ∗ |X=x (y)
1
+ λd(x, y) = log
.
dPȲ (y)
ΣȲ (x)

(87)

Although for a fixed PȲ we can always define the tilted
distribution PȲ ∗ |X via (87), in general we cannot claim that
PȲ ∗ = PȲ , where PX → PȲ ∗ |X → PȲ ∗ , unless PȲ is such
that for PȲ -a.e. y,


exp (−λd(X, y))
=1
(88)
E
ΣȲ (X)
Applying (86) to solve for the inner minimizer in (84), we
obtain


1
(89)
F (λ) = inf E log
PȲ
ΣȲ (X)


1
(90)
= E log
∗
ΣY (X)
where (90) holds by the assumption (B).
This concludes the proof that PY ∗ |X in (78) with α(x) =
α∗ (x), where α∗ (x) is defined in (79), is necessary and sufficient to achieve the minimum of L(λ) in (76). In particular,
(78) is a necessary condition for the minimizer.
We now show that α∗ (x) satisfies (5), which implies that
both (78) and (5) are necessary. Since PX → PY ∗ |X → PY ∗ ,
equality in (88) particularized to PY ∗ holds for PY ∗ -a.s. y,
which is equivalent to equality in (5). To show (5) for all y,
note using (89) that for any PȲ ,




1
1
≤ E log
(91)
E log
ΣY ∗ (X)
ΣȲ (X)
For an arbitrary ȳ ∈ Y and 0 ≤ ǫ ≤ 1, let
PȲ = (1 − ǫ)PY ∗ + ǫδȳ

(92)

for which
ΣȲ (x) = (1 − ǫ)ΣY ∗ (x) + ǫ exp (−λ∗ d(x, ȳ))

Substituting (93) in (91), we obtain


Σ (X)
(94)
0 ≥ E log Ȳ
ΣY ∗ (X)
 

exp (−λd(X, ȳ))
= E log 1 − ǫ + ǫ
(95)
Σ ∗ (X)

  Y
ǫ exp (−λd(X, ȳ))
= log (1 − ǫ) + E log 1 +
1−ǫ
ΣY ∗ (X)
(96)


log e
ǫx
≤ x1−δ
for all x ≥ 0 and 0 ≤
Since 0 ≤ 1ǫ log 1 + 1−ǫ
ǫ ≤ δ ≤ 1, by the dominated convergence theorem, the right
derivative of (96) with respect to ǫ evaluated at ǫ = 0 is


exp (−λd(X, ȳ))
log e ≤ 0
(97)
E −1 +
ΣY ∗ (X)
where the inequality holds because otherwise (94) would be
violated for sufficiently small ǫ. This concludes the proof that
α∗ (x) in (79) satisfies condition (5), so both (78) and (5) in
Theorem 4 are necessary.
The sufficiency of (78) and (5) for PY ∗ |X to achieve the
minimum in (76) follows from (80). To show (80), fix any
α(x) satisfying (5) and use the concavity of the logarithm to
show that

≥
=
≥
≥

I(P̃ ) + λρ(P̃ )


1
(98)
E log
ΣY ∗ (X)




ΣY ∗ (X)
1
− E log
(99)
E log
α(X)
α(X)


exp(−λd(X, Y ∗ ))
1
E log
− log E PX ×PY ∗
(100)
α(X)
α(X)


1
.
(101)
E log
α(X)

For the equality condition, observe that strict concavity of
logarithm implies that equality in (100) holds if and only if
Y ∗ (X)
the ratio Σα(X)
is constant, while equality in (101) holds if
and only if that constant is 1.
V. P ROOF

OF

T HEOREM 2

Fix source distribution PX . For a transition probability
kernel P = PY1 Y2 |X , put
I1 (P ) , I(X; Y1 )

(102)

I2 (P ) , I(X; Y1 , Y2 )

(103)

ρ1 (P ) , E [d1 (X, Y1 )]

(104)

ρ2 (P ) , E [d2 (X, Y2 )]

(105)

Lemma 4. The function R2 (d1 , d2 , R1 ) is non-increasing as
a function of each argument when the others are kept fixed,
jointly convex, and
R2 (d1 , d2 , R1 ) =

inf

P:
I1 (P )=R1
ρ1 (P )=d1
ρ2 (P )=d2

I2 (P ),

(d1 , d2 , R1 ) ∈ Ω,

(106)
(93)

where the set Ω is defined in (14).

7

Proof. That R2 (d1 , d2 , R1 ) is non-increasing is obvious by
definition. To show convexity, note first that since u log uv is
a convex function of (u, v), D(P kQ) is a convex function of
(P, Q), and so I2 (P ) is a convex function of P . Therefore,
I1 (P ) is convex as a composition of a convex function I2 (P )
with an affine mapping P 7→ PY1 |X .
Let the probability kernel Pǫ attain R2 (ǫd1 , ǫd2 , ǫR1 ) and
P1−ǫ attain R2 ((1 − ǫ)d1 , (1 − ǫ)d2 , (1 − ǫ)R1 ). Let P =
ǫPǫ + (1 − ǫ)P1−ǫ . Since I1 (P ) is convex and ρ1 (P ), ρ2 (P )
are affine,
I1 (P ) ≤ R1

(107)

ρ1 (P ) ≤ d1
ρ2 (P ) ≤ d2 .

(108)
(109)

Furthermore,
I2 (P ) ≤ ǫI2 (Pǫ ) + (1 − ǫ)I2 (P1−ǫ )
= ǫR2 (ǫd1 , ǫd2 , ǫR1 )

(110)
(111)

+ (1 − ǫ)R2 ((1 − ǫ)d1 , (1 − ǫ)d2 , (1 − ǫ)R1 ).

Theorem 2 is an immediate consequence of (115) and Theorem 5 below.
Theorem 5 (Necessary and sufficient conditions for an optimizer). In order for (PY1∗ |X , PY2∗ |XY1∗ ) to achieve the infimum
in (114), it is necessary and sufficient that


λ1
exp
−
d
(x,
y
)
1
dPY1∗ |X=x (y1 )
1+ν1 1
=
(116)
1
−
∗
dPY1 (y1 )
β1 (x)β2 (x|y1 ) 1+ν1
dPY2⋆ |X=x,Y1∗ =y1 (y2 )
exp(−λ2 d2 (x, y2 ))
=
,
dPY2∗ |Y1∗ =y1 (y2 )
β2 (x|y1 )

(117)

where 0 ≤ β1 (x) ≤ 1, 0 ≤ β2 (x|y1 ) ≤ 1 satisfy (24), (25).
Furthermore, the choice



1
λ1
β1∗ (x) = E β2∗ (x|Y1∗ ) 1+ν1 exp −
d1 (x, Y1∗ )
1 + ν1
(118)
β2∗ (x|y1 ) = E [exp(−λ2 d2 (x, Y2∗ ))|Y1∗ = y1 ]

(119)

Convexity of R2 (d1 , d2 , R1 ) follows by minimizing the left satisfies (24), (25), (116), (117).
Finally, for any β1 (x) ≥ 0, β2 (x|y1 ) ≥ 0 satisfying (19),
side of (111) over P satisfying the constraints (107)–(109).
we have for all PY1 Y2 |X
(20),
Now, (106) follows from the definition of Ω and



1
(112)
R2 (d1 , d2 , R1 ) = inf R̃2 (d˜1 , d˜2 , R̃1 ),
≥
(1
+
ν
)E
log
L
P
,
P
(120)
1
Y1 |X
Y2 |XY1
R̃1 ≤R
β1 (X)
d˜ ≤d
1

1

d˜2 ≤d2

with equality if and only if (PY1 |X , PY2 |XY1 , β1 , β2 ) =
where R̃2 (·, ·, ·) denotes the function in the right side of (106). (PY1∗ |X , PY2∗ |XY1∗ , β1∗ , β2∗ ) (except, perhaps, on a set of zero
PY1∗ measure).
Put
F (ν1 , λ1 , λ2 ) , max{h ≥ 0 : ∀(d1 , d2 , R2 )
h − λ1 d1 − λ2 d2 − ν1 R1 ≤ R2 (d1 , d2 , R2 )},

(113)

i.e. F (ν1 , λ1 , λ2 ) is the maximum of the R2 axis intercepts
of the hyperplanes h − λ1 d1 − λ2 d2 − ν1 R1 which have
no point inside of the rate-distortion region in (10), i.e. for
(λ1 , λ2 , ν1 ) ≥ 0

F (ν1 , λ1 , λ2 ) ,
inf
L PY1 |X , PY2 |XY1 , (114)
PY1 |X ,PY2 |XY1

Proof of Theorem 5. First, we show that


inf
L PY1 |X , PY2 |XY1 = E log
PY1 |X , PY2 |XY1

For fixed probability kernels PȲ1 and PȲ2 |Ȳ1 , consider the
function

(122)
L̄ PY1 |X , PY2 |XY1 , PȲ1 , PȲ2 |Ȳ1
, D(PY2 |XY1 kPȲ2 |Ȳ1 |PXY1 ) + (1 + ν1 )D(PY1 |X kPȲ1 |PX )
+λ1 E [d1 (X, Y1 )] + λ2 E [d2 (X, Y2 )] .

where



, I(X; Y1 , Y2 ) + ν1 I(X; Y1 )
+λ1 E [d1 (X, Y1 )] + λ2 E [d2 (X, Y2 )] .

In other words, L PY1 |X , PY2 |XY1 is the Lagrangian and
(114) is the Lagrangian dual problem.
Since R2 (d1 , d2 , R1 ) is convex and nonincreasing, to each
(d1 , d2 , R1 ) such that R2 (d1 , d2 , R1 ) < ∞, there exists
(ν1 , λ1 , λ2 ) ≥ 0 such that the hyperplane h − λ1 d1 − λ2 d2 −
ν1 R1 that passes through (d1 , d2 , R1 ) is tangent to the surface
R2 (d1 , d2 , R1 ), and
L PY1 |X , PY2 |XY1

R2 (d1 , d2 , R1 )
=

max

(F (ν1 , λ1 , λ2 ) − ν1 R1 − λ1 d1 − λ2 d2 ).

(ν1 ,λ1 ,λ2 )≥0

(115)


1
.
β1∗ (X)1+ν1
(121)

Since
L PY1∗ |X , PY2∗ |XY1∗
=

min



PY1 |X , PY2 |XY1 , PȲ1 , PȲ2 |Ȳ1

L̄ PY1 |X , PY2 |XY1 , PȲ1 , PȲ2 |Ȳ1



(123)
= L̄ PY1∗ |X , PY2∗ |XY1∗ , PY1∗ , PY2∗ |Y1∗
we have



(124)



L̄ PY1 |X , PY2 |XY1 , PȲ1 , PȲ2 |Ȳ1 ≥ L PY1∗ |X , PY2∗ |XY1∗ ,
(125)
with equality if and only if (PY1 |X , PY2 |XY1 , PȲ1 , PȲ2 |Ȳ1 ) =
(PY1∗ |X , PY2∗ |XY1∗ , PY1∗ , PY2∗ |Y1∗ ). Applying Lemma 2 twice,

8

we compute the minimum of the left side of (125) particularized to PȲ1 = PY1∗ and PȲ2 |Ȳ1 = PY2∗ |Y1∗ :

(126)
L̄ PY1 |X , PY2 |XY1 , PY1∗ , PY2∗ |Y1∗

≥ inf (1 + ν1 )D(PY1 |X kPY1∗ |PX ) + λ1 E [d1 (X, Y1 )]
PY1 |X


D(PY2 |XY1 kPY2∗ |Y1∗ |PXY1 ) + λ2 E [d2 (X, Y2 )]
+ inf
PY2 |XY1

= inf (1 + ν1 )D(PY1 |X |PY1∗ |PX ) + λ1 E [d1 (X, Y1 )]
PY1 |X


1
(127)
+ E log ∗
β2 (X|Y1 )


1
(128)
= (1 + ν1 )E log ∗
β1 (X)
where β1∗ (x) and β2∗ (x|y1 ) are given in (118) and (119),
respectively, and the optimizing PY1∗ |X and PY2∗ |XY1∗ are
specified in (116) and (117), letting β1 (x) = β1∗ (x) and
β2 (x|y1 ) = β2∗ (x|y1 ) therein.
We proceed to show that β1∗ (x) and β2∗ (x|y1 ) satisfy (24)
and (25). For PY1∗ -a.e. y1 , we take expectations with respect
to PX of both sides of (26) to conclude that
Σ1 (y1 ) = 1 .

(129)

Likewise, for PY1∗ Y2∗ -a.e. (y1 , y2 ), we take expectations with
respect to PXY1∗ of both sides of (27) to conclude that
Σ2 (y1 , y2 ) = 1 .

(130)

We next proceed to show that
Σ2 (y1 , y2 ) ≤ 1

PY1∗ -a.e. y1 , ∀y2 ∈ Y2

(131)

Particularizing the left side of (125) to PY1 |X = PY1∗ |X ,
PȲ1 = PY1∗ , PȲ2 |Ȳ1 = PY2∗ |Y1∗ we apply Lemma 2 to
characterize the minimum of the left side of (125) as

L̄ PY1∗ |X , PY2 |XY1∗ , PY1∗ , PY2∗ |Y1∗
(132)
≥ (1 + ν1 )I(X; Y1∗ ) + λ1 E [d1 (X, Y1∗ )]

D(PY2 |XY1∗ kPY2∗ |Y1∗ |PXY1∗ )
+ inf

To finish the proof of (24) and (25), it remains to show that
for all y1 , y2 outside of the support of PY1∗ Y2∗ , (24) and (25)
hold. Consider

L̄ PY1 |X , PY2 |XY1 , PȲ1 , PȲ2 |Ȳ1

≥ inf (1 + ν1 )D(PY1 |X kPȲ1 |PX ) + λ1 E [d1 (X, Y1 )]
PY1 |X


D(PY2 |XY1 kPȲ2 |Ȳ1 |PXY1 ) + λ2 E [d2 (X, Y2 )]
+ inf
PY2 |XY1

= inf (1 + ν1 )D(PY1 |X kPȲ1 |PX ) + λ1 E [d1 (X, Y1 )]
PY1 |X


1
(134)
+ E log
β̄2 (X|Y1 )


1
= (1 + ν1 )E log
(135)
β̄1 (X)
where


λ1
exp −
β̄1 (x) = E ḡ2 (x|Ȳ1 )
d1 (x, Ȳ1 )
1 + ν1


(136)
β̄2 (x|y1 ) = E exp(−λ2 d2 (x, Ȳ2 ))|Ȳ1 = y1 .


Due to (125),
inf

PȲ1 ,PȲ2 |Ȳ1

To evaluate the infimum in (132), we apply Theorem 1 to
conclude that for PY1∗ -a.e. y1 , it holds that
D(PY2 |X,Y1∗ =y1 kPY2∗ |Y1∗ =y1 |PX|Y1∗ =y1 )
+ λ2 E [d2 (X, Y2 )|Y1∗ = y1 ]


1
≥ E log ∗
Y1∗ = y1
β2 (X|y1 )

(133)

with


exp(−λ2 d2 (X, y2 )) ∗
E
|Y1 = y1 ≤ 1 PY1∗ -a.e. y1 , ∀y2
β2∗ (X|y1 )
which, using (26), is equivalent to (131).




1
1
= E log ∗
β1 (X)
β̄1 (X)

(137)

for some 0 ≤ ǫ ≤ 1, where PȲ2 |Ȳ1 is an arbitrary transition
probability kernel.
With this choice,
β̄1 (x) =(1 − ǫ)β1∗ (x)
+ ǫβ̄2 (x|y1 )

(138)


λ1
exp −
d1 (x, y1 )
1 + ν1
(139)


λ1
d1 (x, y1 )
exp −
1 + ν1

1
1+ν1

β̄1′ (x)|ǫ=0 = − β1∗ (x)
1

+ β̄2 (x|y1 ) 1+ν1

1

+λ2 E [d2 (X, Y2 )]


E log

Now, we choose PȲ1 and PȲ2 |Ȳ1 (not independently of each
other!) as
(
(1 − ǫ)PY1∗ Y2∗ (y1 , y2 ) for PY1∗ -a.e. y1
PȲ1 Ȳ2 (y1 , y2 ) =
otherwise
ǫδy1 PȲ2 |Ȳ1 =y1 (y2 )

PY2 |XY ∗



1
1+ν1

Due to (137), the minimum of (135) is attained at ǫ = 0, so
its right derivative with respect to ǫ evaluated at ǫ = 0 must
be nonnegative:


1
∂
E log
(140)
∂ǫ
β̄1 (X) ǫ=0



1
λ1
β̄2 (X|y1 ) 1+ν1 exp − 1+ν
d1 (X, y1 )
1

= 1 − E
β1∗ (X)
≥ 0,

(141)

and (25) follows by substituting PȲ2 |Ȳ1 = PY2∗ |Y1∗ in (141).
Note that bringing the differentiation inside of the expectation is permitted by the dominated convergence theorem: the
negative of the integrand in (140) is log((1 − ǫ)a + ǫb) =
ǫ b
log(1 − ǫ) + log a + log 1 + 1−ǫ
a , for some a ≥ 0, b ≥ 0,

9

and the difference
quotient
of the last term is bounded as


ǫ b
a log e
≤
0 ≤ log 1ǫ 1 + 1−ǫ
a
b 1−ǫ0 , for all 0 ≤ ǫ ≤ ǫ0 < 1.

To show (24), notice that (141) implies that the necessary
condition for PY1∗ |X , PY2∗ |XY1∗ to achieve the minimum is that
(141) holds for all choices of the auxiliary kernel PȲ2 |Ȳ1 , and
so


sup E 

PȲ2 |Ȳ1

β̄2 (X|y1 )

1
1+ν1

exp



β1∗ (X)

≤1.

(142)

To simplify (142), we will find the conditions under which
PY2∗ |Y1∗ =y1 attains the supremum in the left side of (142). Put
PȲ2 |Ȳ1 = (1 − ǫ)PY2∗ |Y1∗ + ǫδy2 .

+ I(X; Y2 |Y1 ) + λ2 E [d2 (X, Y2 )]


≥ (1 + ν1 )I(X; Y1 ) + λ1 E [d1 (X, Y1 )] + E log



λ1
− 1+ν
d1 (X, y1 )
1

We proceed to show (120), which will imply the sufficiency
part. We apply Theorem 1 twice to write

L PY1 |X , PY2 |XY1
≥ (1 + ν1 )I(X; Y1 ) + λ1 E [d1 (X, Y1 )]

(143)

With this choice,
β̄2 (x|y1 ) = (1 − ǫ)β2∗ (x|y1 ) + ǫ exp(−λ2 d2 (x, y2 ))
∂
exp(−λ2 d2 (x, y2 ))
log β̄2 (x|y1 ) ǫ=0 = −1 +
(144)
∂ǫ
β2∗ (x|y1 )


≥ (1 + ν1 )E log

1
β1 (X)



(145)


1
β2 (X|Y1 )
(146)

(147)

where (146) holds for all β2 (x|y1 ) ≥ 0 satisfying


exp(−λ2 d2 (X, y2 ))
|Y1 = y1 ≤ 1 ∀(y1 , y2 ) ∈ Y1 × Y2
E
β2 (X|y1 )
(148)
=
with equality if and only if (PY2 |X,Y1 =y1 , β2 )
(PY2∗ |,X,Y1∗ =y1 , β2∗ ) for PY1 -a.e. y1 .
Likewise, (147) holds for all β1 (x) ≥ 0 satisfying (20), with
equality if and only if


1
λ1
1+ν1
exp
−
d
(x,
y
)
β
(x|y
)
1
1
2
1
dPX|Y1 =y1
1+ν1
(x) =
dPX
β1 (x)
(149)



1
λ1
d1 (x, Y1 ) .
β1 (x) = E β2 (x|Y1 ) 1+ν1 exp −
1 + ν1
(150)
Substituting (149) into (148), we obtain (19), and (120)
follows, together with condition for equality.

The right derivative of the expression in the left side of
(142) with respect to ǫ evaluated at ǫ = 0 is displayed in
(151) below and is equivalent to (24). Note that bringing
the differentiation inside of the expectation is allowed by the
dominated convergence theorem: the difference quotient
of the
ν2
−aν2
, for
integrand in (142) is proportional to ((1−ǫ)a+ǫb)
ǫ
a ≥ 0, b ≥ 0, which is bounded below by 0 and above by a
constant times aν2 −1 b in the range ǫ ≤ ǫ0 < 1, for some ǫ0 .




1
λ1


β2∗ (X|y1 ) 1+ν1 exp − 1+ν
d
(X,
y
)
1
1
exp
(−λ
d
(X,
y
))
1
2
2
2
 ≥ 0,
E
1−
β1∗ (X)
β2∗ (X|y1 )

(151)

VI. I TERATIVE ALGORITHM
A. Computation of single stage rate-distortion function
In the context of finite source and reproduction alphabets,
an algorithm for computation of rate-distortion functions was
proposed by Blahut [7]. Below, we state it for general alphabets in Algorithm 1 and provide its convergence analysis in
Theorem 6. In Section VI-B below, we generalize these results
to successive refinement.
Theorem 6. Suppose Y ∗ attains the minimum in (76), and let
Y0 be such that D(Y ∗ kY0 ) < ∞. Consider Algorithm 1. The
sequence Fk (λ) is monotonically decreasing to F (λ), and the
convergence speed is bounded as
Fk (λ) − F (λ) ≤

D(Y ∗ kY0 )
.
k

(153)

Algorithm 1: The generalized Blahut algorithm.
input : λ > 0; maximum number of iterations K.
output : An estimate FK (λ) of F (λ), the Lagrange dual
of R(d), defined in (76).
Fix PY0 .
for k = 1, 2, . . . , K do
Compute, using (85), ΣYk−1 (x);
Compute, using (87), the transition probability kernel
PYk |X and the corresponding output distribution
PYk , PX → PYk |X → PYk , where PYk |X achieves
the minimum in
Fk (λ) = min L(PY |X , PYk−1 ),
PY |X

and L is defined in (81);

(152)

10

Proof. The analysis below is inspired by Csiszár [18]. From
(82), we have
Fk−1 (λ) = L(PYk |X , PYk ) + D(Yk kYk−1 )

(154)

≥ Fk (λ) + D(Yk kYk−1 ),

(155)

and
Fk (λ) ≤ Fk−1 (λ),

(156)

with equality if and only if Yk = Yk−1 , which implies that
Fk−1 (λ) = Fk (λ) = F (λ).
Taking an expectation of (87) (particularized to Ȳ = Yk−1 )
with respect to PXY ∗ , we conclude
Fk (λ) = F (λ) + D(Y ∗ kYk−1 ) − D(PY ∗ |X kPYk |X kPX )
(157)
∗
∗
≤ F (λ) + D(Y kYk−1 ) − D(Y kYk )
(158)
where (158) holds by the data processing inequality for relative
entropy.
To show (153), we apply (156) and (158) as follows.
KFK (λ) − KF (λ) ≤
≤

K
X

k=1
K
X

Algorithm 2: The generalized Blahut algorithm for successive refinement.
input : (ν1 , λ1 , λ2 ) > 0; maximum number of iterations
K.
output : An estimate FK (ν1 , λ1 , λ2 ) of F (ν1 , λ1 , λ2 ),
the Lagrange dual of R2 (d1 , d2 , R1 ), defined in
(114).
Fix PY01 and PY02 |Y1 ;
for k = 1, 2, . . . , K do
Compute
β2k−1 (x|y1 )
= EP k−1
[exp(−λ2 d2 (x, Y2 ))|Y1 = y1 ] ,
Y2 |Y1 =y1

β1k−1 (x)
(165)



1
λ1
d1 (x, Y1 ) ;
= EP k−1 β2k−1 (x|Y1 ) 1+ν1 exp −
Y1
1 + ν1
Using
dPYk1 |X=x (y1 )
dPYk−1
(y1 )
1

Fk (λ) − KF (λ)

(159)

=



λ1
d
(x,
y
)
exp − 1+ν
1
1
1

,
1
β1k−1 (x)β2k−1 (x|y1 )− 1+ν1
(166)

dPYk2 |X=x,Y1 =y1 (y2 )
∗

dPYk−1
(y2 )
2 |Y1 =y1

∗

(D(Y kYk−1 ) − D(Y kYk ))

=

k=1

(160)

= D(Y ∗ kY0 ) − D(Y ∗ kYK ).

(161)

Note that D(Y ∗ kY0 ) < ∞ is a sufficient condition for convergence of Algorithm 1. This condition is trivially satisfied
if the reproduction alphabet is finite and PY0 is supported
everywhere.
An alternative convergence guarantee can be obtained as
follows. Considering (158) and noting that
D(Y ∗ kYk−1 ) − D(Y ∗ kYk ) ≤ sup log
y∈Y

dPYk
(y),
dPYk−1

(162)

(164)

exp(−λ2 d2 (x, y2 ))
,
β2k−1 (x|y1 )
(167)

compute the transition probability kernels PYk1 |X
and PYk2 |XY1 that achieve the minimum in
Fk (ν1 , λ1 , λ2 )

(168)


k−1
k−1
=
min
L̄ PY1 |X , PY2 |XY1 , PY1 , PY2 |Y1
PY1 |X , PY2 |XY1


1
;
(169)
= (1 + ν1 )E log k−1
β1 (X)
where L̄ is defined in (122), and the minimum is
computed in (135). Compute the corresponding PYk1
and PYk2 |Y1 ;

we can employ the following stopping criterion for the
Blahut algorithm to guarantee estimation accuracy δ: if
dP
supy∈Y log dPYYk (y) ≤ δ, then stop and output F̃ (λ) = ∞ and D(PY2∗ |Y1∗ kPY02 |Y1 |PY1∗ ) < ∞. Consider Algorithm 2.
k−1
Fk (λ). If the same stopping rule is applied for all λ ≥ 0, The sequence Fk (ν1 , λ1 , λ2 ) is monotonically decreasing to
using (77), we find that the corresponding estimate of the rate- F (ν1 , λ1 , λ2 ), and the convergence speed is bounded as
distortion function R̃(d) satisfies the same accuracy guarantee:
Fk (ν1 , λ1 , λ2 ) − F (ν1 , λ1 , λ2 )
(170)

1
0
0
∗
∗
∗
∗
|P
)
.
)
+
D(P
kP
(1
+
ν
)D(P
kP
≤
Y
1
Y
R(d) ≤ R̃(d) ≤ R(d) + δ.
(163)
Y2 |Y1
Y1
Y2 |Y1
1
1
k
B. Computation of the rate-distortion function for successive
refinement
A generalization of discrete Blahut’s algorithm to successive
refinement is proposed in [3]. Algorithm 2 presents a generalization of the algorithm to abstract alphabets, and Theorem 7
presents its convergence analysis.
Theorem 7. Suppose (PY∗1 , PY2∗ |Y1∗ ) attain the minimum in
(76), and let PY01 and PY02 |Y1 be such that D(PY1∗ kPY01 ) <

Proof. We build upon the ideas in the proof of Theorem 6.
From the definition of L̄ and PYk1 |X , PYk2 |XY1 , we have
, PYk−1
)
Fk−1 = L̄(PYk1 |X , PYk2 |XY1 , PYk−1
1
2 |Y1

(171)

+ D(PYk2 |Y1 kPYk−1
)
kPYk1 ) + (1 + ν1 )D(PYk1 kPYk−1
1
2 |Y1
≥ Fk
+

D(PYk2 |Y1 kPYk−1
kPYk1 )
2 |Y1

(172)
+ (1 +

ν1 )D(PYk1 kPYk−1
),
1

11

where we suppressed the dependence of Fk on (ν1 , λ1 , λ2 ) for
brevity, i.e. Fk = Fk (ν1 , λ1 , λ2 ). It follows that
Fk ≤ Fk−1 ,

(173)

with equality if and only if PYk−1
P k−1 = PYk2 |Y1 PYk1 , which
2 |Y1 Y1
implies that Fk−1 = Fk = F .
Taking expectations of the logarithms of (166) and (167)
with respect to PXY1∗ Y2∗ and using (135), we deduce that
Fk


= F + (1 + ν1 ) D(PY1∗ kPYk−1
) − D(PY1∗ |X kPY1k |X kPX )
1

be N (0, 1) and N (y1 , 1), respectively, ensuring that all the
densities in Algorithm 2 are Gaussian, and all the integrals
can be computed in closed form. We chose 31 exponentially
spaced slope samples λ2 > 0, and we ran the algorithm
for the maximum of K = 20 iterations at each choice of
λ2 . In Fig. 3, 31 straight lines of slopes −λ2 correspond
to FK − λ2 d2 − λ1 d1 − ν1 R1 . Their upper convex envelope
is the numerical estimate of R2 (d1 , d2 , R1 ) according to the
algorithm. In Fig. 3, it is undistinguishable from the the thick
curve, which represents the theoretical minimum total rate,
1
1
2 log d2 .

+ D(PY2∗ |Y1∗ kPYk−1
|PY1∗ )
2 |Y1

− D(PY2∗ |X1 Y1∗ kPYk2 |X1 Y1 |PX1 Y1∗ )
kPYk−1
)
1

+ D(PY2∗ |Y1∗ kPYk−1
|PY1∗ ) −
2 |Y1



where (175) holds by the data processing inequality for relative
entropy.
To show (170), we apply (173) and (175) as follows.
KFK − KF
≤
≤

K
X

1.6

1.4

1.2

1

0.8

0.6

Fk − KF

(176)
0.4

k=1
K h
X
k=1

1.8

(175)
− D(P kPYk1 )
k
∗
∗
∗
D(PY2 |Y1 kPY2 |Y1 |PY1 )
Y1∗

R2

≤ F + (1 + ν1 ) D(P

Y1∗

2

(174)


) − D(PY1∗ |X kPYk1 ) (177)
(1 + ν1 ) D(PY1∗ kPYk−1
1

i
k
∗)
∗ ) − D(P ∗
∗ kP
+ D(PY2∗ |Y1∗ kPYk−1
|P
|P
Y
Y
Y
|Y
Y
|Y
2
1
1
1
2
1
2 |Y1

= (1 + ν1 )(D(PY1∗ kPY01 ) − D(PY1∗ kPYK1 ))

(178)

0.2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

d2

Fig. 3. The minimum total rate at stage 2 for Gaussian successive refinement,
for fixed λ1 = 5/9 (corresponding to d1 = 0.9, R1 = −.5 log .9 ≈ .05).

+ D(PY2∗ |Y1∗ kPY02 |Y1 |PY1∗ ) − D(PY2∗ |Y1∗ kPYK2 |Y1 |PY1∗ )
VII. C ONCLUSION
Using (175), we can obtain the following analog of the stopping criterion in (162): to achieve accuracy Fk (ν1 , λ1 , λ2 ) −
F (ν1 , λ1 , λ2 ) ≤ δ, stop as soon as
sup

(1 + ν1 ) log

(y1 ,y2 )∈Y1 ×Y2

dPYk1

(y) +
k−1

dPY1

dPYk2 |Y1
dPYk−1
2 |Y1

(y) ≤ δ.

(179)
For finite alphabet sources, a counterpart of (179) was proposed by Tuncel and Rose [3].
C. Numerical example
Consider successive refinement of X ∼ N (0, 1) under
squared error distortion. As is well known, Gaussian source
under squared distortion is successively refinable [16], so at
any 0 < d2 ≤ d1 ≤ 1 and R(d1 ) ≤ R1 , R2 (d1 , d2 , R1 ) =
R(d2 ) = 12 log d12 .
In this experiment, we ran Algorithm 2 to verify that it
computes an estimate of R2 (d1 , d2 , R1 ) that closely matches
R(d2 ).
We fixed λ1 = 5/9, which corresponds to d1 = 0.9. We
also fixed ν1 = 1 (for this example, the choice of ν1 > 0
is immaterial and can be chosen arbitrarily, as per discussion
after (31)). We set starting densities PY01 and PY02 |Y1 =y1 to

In this paper, we revisited the parametric representation of
rate-distortion function of abstract sources (Theorem 1, proof
in Section IV). We showed its generalization to the successive
refinement problem (Theorem 2, proof in Section V). That
representation leads to a tight nonasymptotic converse bound
for successive refinement, presented in Section III. It also
helps to formulate and prove the convergence of an iterative
algorithm that can be applied to compute the rate-distortion
function on abstract alphabets, presented in Section VI.
It will be interesting to see whether the approach presented
in this paper can be applied to study rate-distortion regions
of other important multiterminal information theory problems,
such as lossy compression with side information available
at decoder (the Wyner-Ziv problem [19]), the multiple descriptions problem [20] and lossy compression with possibly
absent side information (the Kaspi problem [21]). It also paves
the way to a refined nonasymptotic analysis of successive
refinement for abstract sources.
R EFERENCES
[1] V. Kostina and E. Tuncel, “The rate-distortion function for successive
refinement of abstract sources,” in Proceedings 2017 IEEE International
Symposium on Information Theory, Aachen, Germany, June 2017.

12

[2] I. Csiszár, “On an extremum problem of information theory,” Studia
Scientiarum Mathematicarum Hungarica, vol. 9, no. 1, pp. 57–71, Jan.
1974.
[3] E. Tuncel and K. Rose, “Computation and analysis of the n-layer
scalable rate-distortion function,” IEEE Transactions on Information
Theory, vol. 49, no. 5, pp. 1218–1230, 2003.
[4] C. E. Shannon, “Coding theorems for a discrete source with a fidelity
criterion,” IRE Int. Conv. Rec., vol. 7, no. 1, pp. 142–163, Mar. 1959,
reprinted with changes in Information and Decision Processes, R. E.
Machol, Ed. New York: McGraw-Hill, 1960, pp. 93-126.
[5] R. Gallager, Information theory and reliable communication.
John
Wiley & Sons, Inc. New York, 1968.
[6] T. Berger, Rate distortion theory. Prentice-Hall, Englewood Cliffs, NJ,
1971.
[7] R. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Transactions on Information Theory, vol. 18, no. 4, pp.
460–473, Jul. 1972.
[8] V. Kostina, “When is Shannon’s lower bound tight?” in Proceedings 54th
Annual Allerton Conference on Communication, Control and Computing,
Monticello, IL, Oct. 2016.
[9] ——, “Data compression with low distortion and finite blocklength,”
IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4268–
4285, July 2017.
[10] V. Kostina and S. Verdú, “Fixed-length lossy compression in the finite
blocklength regime,” IEEE Transactions on Information Theory, vol. 58,
no. 6, pp. 3309–3338, June 2012.
[11] A. No, A. Ingber, and T. Weissman, “Strong successive refinability and
rate-distortion-complexity tradeoff,” IEEE Transactions on Information
Theory, vol. 62, no. 6, pp. 3618–3635, 2016.
[12] L. Zhou, V. Y. Tan, and M. Motani, “Second-order and moderate
deviations asymptotics for successive refinement,” IEEE Transactions
on Information Theory, vol. 63, no. 5, pp. 2896–2921, 2017.
[13] C.-I. Chang and L. D. Davisson, “On calculating the capacity of an
infinite-input finite (infinite)-output channel,” IEEE Transactions on
Information Theory, vol. 34, no. 5, pp. 1004–1010, Sep 1988.
[14] K. Rose, “A mapping approach to rate-distortion computation and
analysis,” IEEE Transactions on Information Theory, vol. 40, no. 6, pp.
1939–1952, Nov 1994.
[15] B. Rimoldi, “Successive refinement of information: Characterization of
the achievable rates,” IEEE Transactions on Information Theory, vol. 40,
no. 1, pp. 253–259, 1994.
[16] W. H. Equitz and T. M. Cover, “Successive refinement of information,”
IEEE Transactions on Information Theory, vol. 37, no. 2, pp. 269–275,
1991.
[17] M. D. Donsker and S. R. S. Varadhan, “Asymptotic evaluation of certain
markov process expectations for large time, I,” Communications on Pure
and Applied Mathematics, vol. 28, no. 1, pp. 1–47, 1975.
[18] I. Csiszár, “On the computation of rate-distortion functions (corresp.),”
IEEE Transactions on Information Theory, vol. 20, no. 1, pp. 122–124,
1974.
[19] A. D. Wyner and J. Ziv, “The rate-distortion function for source coding
with side information at the decoder,” IEEE Transactions on Information
Theory, vol. 22, no. 1, pp. 1–10, 1976.
[20] J. K. Wolf, A. D. Wyner, and J. Ziv, “Source coding for multiple
descriptions,” Bell Labs Technical Journal, vol. 59, no. 8, pp. 1417–
1426, 1980.
[21] A. H. Kaspi, “Rate-distortion function when side-information may be
present at the decoder,” IEEE Transactions on Information Theory,
vol. 40, no. 6, pp. 2031–2034, 1994.

