Sphere Covering for Poisson Processes

The geometric interpretation of sphere covering describing the rate distortion problem of a Gaussian source with the squared-error distortion measure is generalized to a Laplacian source and the ℓ₁-distortion measure. Using additional constraints on the distortion measure, sphere covering is further generalized to exponential sources and to Poisson point processes.

I. Introduction

It is well-known that the rate-distortion problem of a Gaussian source and a squared-error distortion measure can be understood geometrically by counting the minimum number of small distortion balls required to completely cover the volume of the ball describing the possible outputs of the Gaussian source [1], [Sec. 10.9], [2], [Sec. 10.5]. This beautiful picture of sphere covering, however, is not restricted to the special case of Gaussian sources with an ℓ₂-distortion measure, but can be generalized to sources and corresponding distortion measures in the general ℓ_p-space. In this paper, we focus on the case for p = 1, i.e., a Laplacian source with the ℓ₁-distortion measure, and then show how it can be adapted to find a corresponding geometric interpretation of the well-known rate-distortion function of a Poisson point process. The general case in ℓ_p is deferred to a later publication.