Kontoyiannis, I (2001) *Sphere-covering, measure concentration, and source coding.* IEEE Transactions on Information Theory, 47. pp. 1544-1552. ISSN 0018-9448

## Abstract

Suppose A is a finite set, let P be a discrete distribution on A, and let M be an arbitrary "mass" function on A. We give a precise characterization of the most efficient way in which An can be almost-covered using spheres of a fixed radius. An almost-covering is a subset Cn of An, such that the union of the spheres centered at the points of Cn has probability close to one with respect to the product distribution Pn. Spheres are defined in terms of a single-letter distortion measure on An, and an efficient covering is one with small mass Mn(Cn). In information-theoretic terms, the sets Cn are rate-distortion codebooks, but instead of minimizing their size we seek to minimize their mass. With different choices for M and the distortion measure on A our results give various corollaries as special cases, including Shannon's classical rate-distortion theorem, a version of Stein's lemma (in hypothesis testing), and new converse to some measure-concentration inequalities on discrete spaces. Under mild conditions, we generalize our results to abstract spaces and nonproduct measures.

Item Type: | Article |
---|---|

Subjects: | UNSPECIFIED |

Divisions: | Div F > Signal Processing and Communications |

Depositing User: | Cron Job |

Date Deposited: | 08 Jan 2018 20:11 |

Last Modified: | 04 Apr 2019 02:02 |

DOI: | 10.1109/18.923735 |