SUCCESSIVE REFINEMENT OF INFORMATION - CHARACTERIZATION OF THE ACHIEVABLE RATES

Let R(.) be the rate-distortion function. Assume that we want to describe a source with distortion no larger than DELTA1. From the rate-distortion theory we know that we need to do so at a rate R1 no smaller than R(DELTA1) [bits/symbol]. If it turns out that a more accurate description at distortion DELTA2, DELTA2 < DELTA1, is desirable, one can transmit additional information at some rate DELTAR. What is the minimal value for DELTAR? More generally, which are the achievable (R1, R2) pairs for which, with high probability, one can describe the source at rate R1 and incur distortion not exceeding DELTA1 and refine this description at a rate R2-R1 obtaining a final distortion not exceeding DELTA2? The achievable region containing those pairs is characterized. An interpretation of Equitz and Cover's Markov condition is given. The Markov condition characterizes those cases for which (R(DELTA1), R(DELTA2) is an achievable pair.