Information and communication theory, circuits Theorem

Landau's necessary density conditions for sampling

Builds on Band-limited function Fourier transform Lp space

Statement

Let $d \ge 1$ and let $S \subset \R^d$ be a compact set of positive measure whose boundary has Lebesgue measure zero. Let $PW_S$ be the space of band-limited functions with spectrum in $S$ : the $f \in L^2(\R^d)$ whose Fourier transform $\hat f(\xi) = \int f(x) e^{-i x \cdot \xi} \, dx$ vanishes outside $S$ . Let $\Lambda \subset \R^d$ be uniformly discrete, that is, $\inf \set{\abs{\lambda - \lambda'} : \lambda \ne \lambda' \in \Lambda} > 0$ . Define the lower and upper Beurling densities $D^-(\Lambda) = \liminf_{r \to \infty} \inf_{x \in \R^d} \frac{\#(\Lambda \cap (x + [0, r]^d))}{r^d}, \qquad D^+(\Lambda) = \limsup_{r \to \infty} \sup_{x \in \R^d} \frac{\#(\Lambda \cap (x + [0, r]^d))}{r^d}.$

If $\Lambda$ is a sampling set for $PW_S$ , that is, there are $0 < A \le B$ with $A \norm{f}_2^2 \le \sum_{\lambda \in \Lambda} \abs{f(\lambda)}^2 \le B \norm{f}_2^2$ for all $f \in PW_S$ , then $D^-(\Lambda) \ge \abs{S} / (2\pi)^d$ .
If $\Lambda$ is an interpolation set for $PW_S$ , that is, for every square-summable $(a_\lambda)_{\lambda \in \Lambda}$ there is $f \in PW_S$ with $f(\lambda) = a_\lambda$ for all $\lambda$ , then $D^+(\Lambda) \le \abs{S} / (2\pi)^d$ .

Here $\abs{S}$ is the Lebesgue measure of $S$ .

Remarks

Henry Landau proved these conditions in 1967. The proof compares the eigenvalues of two concentration operators: the operator that restricts $f \in PW_S$ to a large cube, and its discrete analogue on the samples in that cube. The number of eigenvalues of the first operator that are not close to $0$ or $1$ is small compared with the volume of the cube. The main count is $\abs{S} r^d / (2\pi)^d$ .

Example: for $d = 1$ and $S = [-\pi, \pi]$ , the integers form a sampling and interpolation set, and $D^-(\Z) = D^+(\Z) = 1 = \abs{S}/2\pi$ . This is the critical case of the Nyquist–Shannon sampling theorem. So uniform sampling at the Nyquist rate is optimal, and no irregular scheme can sample stably at a lower average rate.

Since $f(\lambda) = (2\pi)^{-d} \int_S \hat f(\xi) e^{i\lambda \cdot \xi} \, d\xi$ , the set $\Lambda$ is a sampling set if and only if the exponentials $e^{i\lambda \cdot \xi}$ , $\lambda \in \Lambda$ , form a frame of $L^2(S)$ . It is a sampling and interpolation set if and only if they form a Riesz basis of $L^2(S)$ , and then both parts give $D^-(\Lambda) = D^+(\Lambda) = \abs{S}/(2\pi)^d$ .

Going deeper

For a student

The Shannon sampling theorem gives a sufficient condition for one regular lattice. Landau's theorem gives a necessary condition for every uniformly discrete set, measured by the Beurling densities. It shows that the Nyquist rate is sharp also for irregular sampling. It also implies that a Riesz basis of exponentials for $L^2(S)$ must have uniform density exactly $\abs{S}/(2\pi)^d$ , which links it with the theory of nonharmonic Fourier series. The theorem has analogues for Gabor systems and for other spaces of functions with localized transforms.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Band-limited function concept
Fourier transform concept
Lp space concept
Landau's necessary density conditions for sampling statement

Tag	`XWV6VS7BQM`
URI	`m2://XWV6VS7BQM`
Kind	statement, theorem
Writing	W0 stub
MSC	94A20, 42C15, 30D15
Status	This copy of the site has no build data. Run `m2 status XWV6VS7BQM`.
About	Band-limited function
Uses	Band-limited function, Fourier transform, Lp space