CUED Publications database

Sphere-covering, measure concentration, and source coding

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

Full text not available from this repository.


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
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:11
Last Modified: 27 Oct 2020 07:13
DOI: 10.1109/18.923735