Random Sampling of Entire Functions of Exponential Type in Several Variables

Abstract

We consider the problem of random sampling for band-limited functions. When can a band-limited function $f$ be recovered from randomly chosen samples $f(x_j),j\in \mathbb{N}$? We estimate the probability that a sampling inequality of the form A\|f\|_2^2 \leq \sum_{j\in \mathbb{N}} |f(x_j)|^2 \leq B \|f\|_2^2 hold uniformly all functions $f\in L^2({\mathbb{R}}^d)$ with supp $\hat{f}\subseteq [-1/2,1/2{]}^d$ or some subset of \bdl functions. In contrast to discrete models, the space of band-limited functions is infinite-dimensional and its functions "live" on the unbounded set ${\mathbb{R}}^d$. This fact raises new problems and leads to both negative and positive results. (a) With probability one, the sampling inequality fails for any reasonable definition of a random set on ${\mathbb{R}}^d$, e.g., for spatial Poisson processes or uniform distribution over disjoint cubes. (b) With overwhelming probability, the sampling inequality holds for certain compact subsets of the space of band-limited functions and for sufficiently large sampling size.

22 pages Revised the section on covering numbers and clarified some estimates. Added two references