We consider a novel variant of d-semifaithful lossy coding in which the distortion measure is revealed only to the encoder and only at run-time, as well as an extension of it in which the distortion constraint d is al...
详细信息
We consider a novel variant of d-semifaithful lossy coding in which the distortion measure is revealed only to the encoder and only at run-time, as well as an extension of it in which the distortion constraint d is also revealed at run-time. Two forms of rate redundancy are used to analyze the performance, and achievability results of both a pointwise and minimax nature are demonstrated. The first coding scheme uses ideas from VC dimension and growth functions, the second uses appropriate quantization of the space of distortion measures, and the third relies on a random coding argument.
We show the existence of variable-rate rate distortion codes that meet the distortion constraint almost surely and are minimax, i.e., strongly, universal with respect to an unknown source distribution and a distortion...
详细信息
We show the existence of variable-rate rate distortion codes that meet the distortion constraint almost surely and are minimax, i.e., strongly, universal with respect to an unknown source distribution and a distortion measure that is revealed only to the encoder and only at runtime. If we only require minimax universality with respect to the source distribution and not the distortion measure, then we provide an achievable O(1/root n) redundancy rate, which we show is optimal. This is in contrast to prior work on universal lossy compression, which provides O (log n/n) redundancy guarantees for weakly universal codes under various regularity conditions. We show that either eliminating the regularity conditions or upgrading to strong universality while keeping these regularity conditions entails an inevitable increase in the redundancy to O(1/root n). Our construction involves random coding with non-i.i.d. codewords and a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, and the VC dimension of distortion measures.
The problem of variable length and fixed-distortion universal source coding (or d-semifaithful source coding) for stationary and memoryless sources on countably infinite alphabets (infinity -alphabets) is addressed in...
详细信息
The problem of variable length and fixed-distortion universal source coding (or d-semifaithful source coding) for stationary and memoryless sources on countably infinite alphabets (infinity -alphabets) is addressed in this paper. The main results of this work offer a set of sufficient conditions (from weaker to stronger) to obtain weak minimax universality, strong minimax universality, and corresponding achievable rates of convergences for the worst-case redundancy for the family of stationary memoryless sources whose densities are dominated by an envelope function (or the envelope family) on infinity-alphabets. An important implication of these results is that universal d-semifaithful source coding is not feasible for the complete family of stationary and memoryless sources on infinity-alphabets. To demonstrate this infeasibility, a sufficient condition for the impossibility is presented for the envelope family. Interestingly, it matches the well-known impossibility condition in the context of lossless (variable-length) universal source coding. More generally, this work offers a simple description of what is needed to achieve universal d-semifaithful coding for a family of distributions Lambda. This reduces to finding a collection of quantizations of the product space at different blocklengths - reflecting the fixeddistortion restriction - that satisfy two asymptotic requirements: the first is a universal quantization condition with respect to Lambda, and the second is a vanishing information radius (I-radius) condition for Lambda reminiscent of the condition known for lossless universal source coding.
We consider a novel variant of lossy coding in which the distortion measure is revealed only to the encoder and only at run-time, as well as an extension of it in which the distortion constraint is also revealed at ru...
详细信息
ISBN:
(纸本)9781665421607;9781665421591
We consider a novel variant of lossy coding in which the distortion measure is revealed only to the encoder and only at run-time, as well as an extension of it in which the distortion constraint is also revealed at run-time. Two forms of rate redundancy are used to analyze the performance, and achievability results of both a pointwise and minimax nature are demonstrated. One proof uses appropriate quantization of the space of distortion measures while another uses ideas from VC dimension and growth functions.
We show the existence of universal, variable-rate rate-distortion codes that meet the distortion constraint almost surely and approach the rate-distortion function uniformly with respect to an unknown source distribut...
详细信息
ISBN:
(纸本)9781665421607;9781665421591
We show the existence of universal, variable-rate rate-distortion codes that meet the distortion constraint almost surely and approach the rate-distortion function uniformly with respect to an unknown source distribution and a distortion measure that is only revealed to the encoder and only at run-time. If the convergence only needs to be uniform with respect to the source distribution and not the distortion measure, then we provide an explicit bound on the minimax rate of convergence. Our construction combines conventional random coding with a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, the VC dimension of distortion measures, and the identification of an explicit, code-independent, finite-blocklength quantity, which converges to the rate-distortion function, that controls the performance of the best codes.
暂无评论