Multidimensional sampling

The Nyquist–Shannon sampling theorem for sampling one-dimensional bandlimited functions can be generalized to a theorem on sampling wavenumber-limited functions on lattices in higher-dimensional Euclidean spaces. This article presents the basic result due to Petersen and Middleton

In essence, the theorem shows that a wavenumber-limited function can be perfectly reconstructed from its values on an infinite lattice of points, provided the lattice is fine enough. The theorem provides conditions on the lattice under which perfect reconstruction is possible.

As with the Nyquist–Shannon sampling theorem, this theorem also assumes an idealization of any real-world situation, as it only applies to functions that are sampled over an infinitude of points. Perfect reconstruction is mathematically possible for the idealized model but only an approximation for real-world functions and sampling techniques, albeit in practice often a very good one.

Preliminaries

Analogous to the concept of a bandlimited function in one dimension, one can introduce the notion of a wavenumber-limited function in higher dimensions as a generalization of the concept of a bandlimited function in one dimension. Recall that the Fourier transform of an integrable function ƒ(.) on n-dimensional space is defined as:

${\hat {f}}(\xi )={\mathcal {F}}(f)(\xi )=\int _{\Re ^{n}}f(x)e^{-2\pi i\langle x,\xi \rangle }\,dx$

where x and ξ are n-dimensional vectors, and $\langle x,\xi \rangle$ is the inner product of the vectors. The function ƒ(.) is said to be wavenumber-limited to a set $\Omega$ if the Fourier transform satisfies ${\hat {f}}(\xi )=0$ for $\xi \notin \Omega$.

Similarly, the configuration of uniformly spaced sampling points in one-dimension can be generalized to a lattice in higher dimensions. A lattice is a collection of points $\Lambda \subset \Re ^{n}$ of the form $\Lambda =\left\{\sum _{i=1}^{n}a_{i}v_{i}\;|\;a_{i}\in {\mathbb {Z}}\right\}$ where {v₁, ..., v_n} is a basis for $\Re ^{n}$. The reciprocal lattice $\Gamma$ corresponding to $\Lambda$ is defined by $\Gamma =\left\{\sum _{i=1}^{n}a_{i}u_{i}\;|\;a_{i}\in {\mathbb {Z}}\right\}$ where the vectors $u_{i}$ are chosen to satisfy $\langle u_{i},v_{j}\rangle =2\pi \delta _{ij}$.

The theorem

Let $\Lambda$ denote a lattice in $\Re ^{n}$ and $\Gamma$ the corresponding reciprocal lattice. The theorem of Petersen and Middleton states that a function f(.) that is wavenumber-limited to a set $\Omega \subset \Re ^{n}$ can be exactly reconstructed from its measurements on $\Lambda$ provided that the set $\Omega$ does not overlap with any of its shifted version $\Omega +x$ where the shift x is any non-zero element of the reciprocal lattice $\Gamma$. In other words, f(.) can be exactly reconstructed from its measurements on $\Lambda$ provided that $\Omega \cap \{x+y:y\in \Omega \}=\phi$ for all $x\in \Gamma$.

Implications

Aliasing

Main article: Aliasing

The theorem gives conditions on sampling lattices for perfect reconstruction of the sampled. If the lattices are not fine enough to satisfy the Petersen Middleton condition, then the field cannot be reconstructed exactly from the samples in general. In this case we say that the samples may be aliased.

Properly sampled image of brick wall.

Spatial aliasing in the form of a Moiré pattern.

Optimal sampling lattices

One of the objects of interest in designing a sampling scheme for bandlimited fields is to identify the configuration of points that leads to the minimum sampling density, i.e., the density of sampling points per unit spatial volume in $\Re ^{n}$. The theorem of Petersen and Middleton can be used to identify the optimal lattice for sampling fields that are wavenumber-limited to a given set $\Omega \subset \Re ^{d}$. For example, it can be shown that the lattice in $\Re ^{2}$ with minimum spatial density of points that admits perfect reconstructions of fields wavenumber-limited to a circular disc in $\Re ^{2}$ is the hexagonal lattice. As a consequence, hexagonal lattices are preferred for sampling isotropic fields in $\Re ^{2}$.

Applications

The Petersen-Middleton theorem is useful in designing efficient sensor placement strategies in applications involving measurement of spatial phenomena such as seismic surveys and spatial audio-field measurements.