Multidimensional sampling

Fig. 1: A hexagonal sampling lattice ${\displaystyle \Lambda }$ and its basis vectors v₁ and v₂

Fig. 2: The reciprocal lattice ${\displaystyle \Gamma }$ corresponding to the lattice ${\displaystyle \Lambda }$ of Fig. 1 and its basis vectors u₁ and u₂ (figure not to scale).

The concept of a bandlimited function in one dimension can be generalized to the notion of a wavenumber-limited function in higher dimensions. Recall that the Fourier transform of an integrable function ${\displaystyle f(\cdot )}$ on n-dimensional Euclidean space is defined as:

${\displaystyle {\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 ${\displaystyle \langle x,\xi \rangle }$ is the inner product of the vectors. The function ${\displaystyle f(\cdot )}$ is said to be wavenumber-limited to a set ${\displaystyle \Omega }$ if the Fourier transform satisfies ${\displaystyle {\hat {f}}(\xi )=0}$ for ${\displaystyle \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 ${\displaystyle \Lambda \subset \Re ^{n}}$ of the form ${\displaystyle \Lambda =\left\{\sum _{i=1}^{n}a_{i}v_{i}\;|\;a_{i}\in \mathbb {Z} \right\}}$ where {v₁, ..., v_n} is a basis for ${\displaystyle \Re ^{n}}$. The reciprocal lattice ${\displaystyle \Gamma }$ corresponding to ${\displaystyle \Lambda }$ is defined by

${\displaystyle \Gamma =\left\{\sum _{i=1}^{n}a_{i}u_{i}\;|\;a_{i}\in \mathbb {Z} \right\}}$

where the vectors ${\displaystyle u_{i}}$ are chosen to satisfy ${\displaystyle \langle u_{i},v_{j}\rangle =\delta _{ij}}$. That is, if the vectors ${\displaystyle u_{i}}$ form columns of a matrix ${\displaystyle A}$ and ${\displaystyle v_{i}}$ the columns of a matrix ${\displaystyle B}$, then ${\displaystyle A=B^{-T}}$. An example of a sampling lattice in two dimensional space is a hexagonal lattice depicted in Figure 1. The corresponding reciprocal lattice is shown in Figure 2. The reciprocal lattice of a square lattice in two dimensions is another square lattice. In three dimensional space the reciprocal lattice of a face-centered cubic (FCC) lattice is a body centered cubic (BCC) lattice.

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

Fig. 3: Support of the sampled spectrum ${\displaystyle {\hat {f}}_{s}(\cdot )}$ obtained by hexagonal sampling of a two-dimensional function wavenumber-limited to a circular disc. The blue circle represents the support ${\displaystyle \Omega }$ of the original wavenumber-limited field, and the green circles represent the repetitions. In this example the spectral repetitions do not overlap and hence there is no aliasing. The original spectrum can be exactly recovered from the sampled spectrum.

The generalization of the Poisson summation formula to higher dimensions[2] can be used to show that the samples, ${\displaystyle \{f(x):x\in \Lambda \}}$, of the function ${\displaystyle f(\cdot )}$ on the lattice ${\displaystyle \Lambda }$ are sufficient to create a periodic summation of the function ${\displaystyle {\hat {f}}(\cdot )}$. The result is:

${\displaystyle {\hat {f}}_{s}(\xi )\ {\stackrel {\mathrm {def} }{=}}\sum _{y\in \Gamma }{\hat {f}}\left(\xi -y\right)=\sum _{x\in \Lambda }|\Lambda |f(x)\ e^{-i2\pi \langle x,\xi \rangle },}$

(Eq.1)

where ${\displaystyle |\Lambda |}$ represents the volume of the parallelepiped formed by the vectors {v₁, ..., v_n}. This periodic function is often referred to as the sampled spectrum and can be interpreted as the analogue of the discrete-time Fourier transform (DTFT) in higher dimensions. If the original wavenumber-limited spectrum ${\displaystyle {\hat {f}}(\cdot )}$ is supported on the set ${\displaystyle \Omega }$ then the function ${\displaystyle {\hat {f}}_{s}(\cdot )}$ is supported on periodic repetitions of ${\displaystyle \Omega }$ shifted by points on the reciprocal lattice ${\displaystyle \Gamma }$. If the conditions of the Petersen-Middleton theorem are met, then the function ${\displaystyle {\hat {f}}_{s}(\xi )}$ is equal to ${\displaystyle {\hat {f}}(\xi )}$ for all ${\displaystyle \xi \in \Omega }$, and hence the original field can be exactly reconstructed from the samples. In this case the reconstructed field matches the original field and can be expressed in terms of the samples as

${\displaystyle f(x)=\sum _{y\in \Lambda }|\Lambda |f(y){\check {\chi }}_{\Omega }(y-x)}$,

(Eq.2)

where ${\displaystyle {\check {\chi }}_{\Omega }(\cdot )}$ is the inverse Fourier transform of the characteristic function of the set ${\displaystyle \Omega }$. This interpolation formula is the higher-dimensional equivalent of the Whittaker–Shannon interpolation formula.

As an example suppose that ${\displaystyle \Omega }$ is a circular disc. Figure 3 illustrates the support of ${\displaystyle {\hat {f}}_{s}(\cdot )}$ when the conditions of the Petersen-Middleton theorem are met. We see that the spectral repetitions do not overlap and hence the original spectrum can be exactly recovered.

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