Credal Rate-Distortion Theory

We develop a rate–distortion theory for lossy compression when each source symbol is associated with a credal set of plausible downstream laws. Existing universal and minimax formulations account for uncertainty in the source or distortion model but typically retain a point-valued probabilistic description for each input. Credal-set metrics, on the other hand, compare set-valued uncertainty models without specifying how several such sets should be represented when their inputs share a codeword. Under support-only semantics, we assign each codeword the convex hull of its constituent credal sets. We introduce a directed free-energy replacement distortion and prove that the distortion of a compression cell equals its worst pairwise constituent distortion. Consequently, one-shot codebook size and minimum output entropy are characterized by the chromatic number and chromatic entropy of an incompatibility graph. For product credal families, coordinatewise observation yields disjunctive graph powers, with a fixed-length exponent determined by the fractional chromatic number and an expected-prefix rate given by Körner graph entropy, while bounded-window observation yields non-tensorizing block graphs and a regularized expected-prefix rate. Under unrestricted observation and every distortion tolerance below one, the asymptotic costs reduce to those of transmitting the credal equality classes. We characterize the exact graph-saturation window and bound its size. A three-symbol construction separates the coordinatewise, two-coordinate, and unrestricted expected-prefix rates as 0, 2/3, and log2 3 bits per symbol. Experiments on the Street View House Numbers dataset illustrate the difference between credal-preserving compression and point-summary clustering.