SUCCESSIVE REFINEMENT OF INFORMATION

The successive refinement of information consists of first approximating data using a few bits of information, then iteratively improving the approximation as more and more information is supplied. The goal is to achieve an optimal description at each stage. In general an ongoing description is sought which is rate-distortion optimal whenever it is interrupted. It is shown that a rate distortion problem is successively refinable if and only if the individual solutions of the rate distortion problems can be written as a Markov chain. This implies in particular that tree structured descriptions are optimal if and only if the rate distortion problem is successively refinable. Successive refinement is shown to be possible for all finite alphabet signals with Hamming distortion, for Gaussian signals with squared-error distortion, and for Laplacian signals with absolute-error distortion. However, a simple counterexample with absolute error distortion and a symmetric source distribution shows that successive refinement is not always achievable.