Strong universal source coding subject to a rate-distortion constraint
The following problem in universal source coding is explored. Some members of a class of sources have various constraints on the maximum rate at which they may be encoded, and thc remainder have various constraints on the maximum distortion that may result from encoding. It is desired to find a universal code that will adapt its performance so that whatever source in the class is encoded, the resulting performance meets the constraint and is optimal in the rate-distortion function sense for that particular source. It is shown that such codes exist when the class is totally bounded and the constraints are uniformly continuous in an appropriate sense. A key result shows that the value of any uniformly continuous function on a totally bounded class can be uniformly well estimated from observations of the output of any source in