Source coding with distortion profile constraints

In rate-distortion theory, three main types of distortion constraints have been popular: average, pointwise, and excess probability (aka-fidelity). A new setup is proposed here, which is suitable for fixed-length codes and constrains the distribution (profile) of distortions. This is accomplished by imposing multiple constraints on excess-distortion probabilities as well as an optional constraint on average distortion. We show that coding redundancy for compressing discrete memoryless sources is upper-bounded by R₂/√n + log n/2n + O(log log n/n) + R₄ + o(1) where n is the block length, R₂ the second-order coding rate, and R₄ a constant. For the special case of coding with a single-fidelity constraint, R₂ = √V Q^-1() where V is the source rate-dispersion function, and Q is the tail probability of a normal random variable. The upper bound is proved using a random coding scheme and deriving exact asymptotics for the probability of distortion balls with input type dependent radius.