International
Tables for Crystallography Volume B Reciprocal space Edited by U. Shmueli © International Union of Crystallography 2006 |
International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 45-49
|
Let be such that has compact support K. Let φ be sampled at the nodes of a lattice , yielding the lattice distribution . The Fourier transform of this sampled version of φ is which is essentially Φ periodized by period lattice , with period matrix A.
Let us assume that Λ is such that the translates of K by different period vectors of Λ are disjoint. Then we may recover Φ from by masking the contents of a `unit cell' of Λ (i.e. a fundamental domain for the action of Λ in ) whose boundary does not meet K. If is the indicator function of , then Transforming both sides by yields i.e. since is the volume V of .
This interpolation formula is traditionally credited to Shannon (1949), although it was discovered much earlier by Whittaker (1915). It shows that φ may be recovered from its sample values on (i.e. from ) provided is sufficiently fine that no overlap (or `aliasing') occurs in the periodization of Φ by the dual lattice Λ. The interpolation kernel is the transform of the normalized indicator function of a unit cell of Λ containing the support K of Φ.
If K is contained in a sphere of radius and if Λ and are rectangular, the length of each basis vector of Λ must be greater than , and thus the sampling interval must be smaller than . This requirement constitutes the Shannon sampling criterion.
Let be a period lattice in with matrix A, and let be the lattice reciprocal to , with period matrix . Let be defined similarly, and let us suppose that is a sublattice of , i.e. that as a set.
The relation between and may be described in two different fashions: (i) multiplicatively, and (ii) additively.
Let us now consider the two reciprocal lattices and . Their period matrices and are related by: , where is an integer matrix; or equivalently by . This shows that the roles are reversed in that is a sublattice of , which we may write:
The above relations between lattices may be rewritten in terms of the corresponding lattice distributions as follows: where and are (finite) residual-lattice distributions. We may incorporate the factor in (i) and into these distributions and define
Since , convolution with and has the effect of averaging the translates of a distribution under the elements (or `cosets') of the residual lattices and , respectively. This process will be called `coset averaging'. Eliminating and between (i) and (ii), and and between and , we may write: These identities show that period subdivision by convolution with (respectively ) on the one hand, and period decimation by `dilation' by on the other hand, are mutually inverse operations on and (respectively and ).
Finally, let us consider the relations between the Fourier transforms of these lattice distributions. Recalling the basic relation of Section 1.3.2.6.5, i.e. and similarly:
Thus (respectively ), a decimated version of (respectively ), is transformed by into a subdivided version of (respectively ).
The converse is also true: i.e. and similarly
Thus (respectively ), a subdivided version of (respectively ) is transformed by into a decimated version of (respectively ). Therefore, the Fourier transform exchanges subdivision and decimation of period lattices for lattice distributions.
Further insight into this phenomenon is provided by applying to both sides of (iv) and (v) and invoking the convolution theorem: These identities show that multiplication by the transform of the period-subdividing distribution (respectively ) has the effect of decimating to (respectively to ). They clearly imply that, if and , then Therefore, the duality between subdivision and decimation may be viewed as another aspect of that between convolution and multiplication.
There is clearly a strong analogy between the sampling/periodization duality of Section 1.3.2.6.6 and the decimation/subdivision duality, which is viewed most naturally in terms of subgroup relationships: both sampling and decimation involve restricting a function to a discrete additive subgroup of the domain over which it is initially given.
The usual presentation of this duality is not in terms of lattice distributions, but of periodic distributions obtained by convolving them with a motif.
Given , let us form , then decimate its transform by keeping only its values at the points of the coarser lattice ; as a result, is replaced by , and the reverse transform then yields which is the coset-averaged version of the original . The converse situation is analogous to that of Shannon's sampling theorem. Let a function whose transform has compact support be sampled as at the nodes of . Then is periodic with period lattice . If the sampling lattice is decimated to , the inverse transform becomes hence becomes periodized more finely by averaging over the cosets of . With this finer periodization, the various copies of Supp Φ may start to overlap (a phenomenon called `aliasing'), indicating that decimation has produced too coarse a sampling of φ.
Let be such that has compact support ( is said to be band-limited). Then is -periodic, and is such that only a finite number of points of have a non-zero Fourier coefficient attached to them. We may therefore find a decimation of such that the distinct translates of Supp by vectors of do not intersect.
The distribution Φ can be uniquely recovered from by the procedure of Section 1.3.2.7.1, and we may write: these rearrangements being legitimate because and have compact supports which are intersection-free under the action of . By virtue of its -periodicity, this distribution is entirely characterized by its `motif' with respect to :
Similarly, φ may be uniquely recovered by Shannon interpolation from the distribution sampling its values at the nodes of is a subdivision of ). By virtue of its -periodicity, this distribution is completely characterized by its motif:
Let and , and define the two sets of coefficients Define the two distributions and The relation between ω and Ω has two equivalent forms:
By (i), . Both sides are weighted lattice distributions concentrated at the nodes of , and equating the weights at gives Since , is an integer, hence
By (ii), we have Both sides are weighted lattice distributions concentrated at the nodes of , and equating the weights at gives Since , is an integer, hence
Now the decimation/subdivision relations between and may be written: so that with , hence finally
Denoting by and by , the relation between ω and Ω may be written in the equivalent form where the summations are now over finite residual lattices in standard form.
Equations (i) and (ii) describe two mutually inverse linear transformations and between two vector spaces and of dimension . [respectively ] is the discrete Fourier (respectively inverse Fourier) transform associated to matrix N.
The vector spaces and may be viewed from two different standpoints:
These two spaces are said to be `isomorphic' (a relation denoted ≅), the isomorphism being given by the one-to-one correspondence:
The second viewpoint will be adopted, as it involves only linear algebra. However, it is most helpful to keep the first one in mind and to think of the data or results of a discrete Fourier transform as representing (through their sets of unique weights) two periodic lattice distributions related by the full, distribution-theoretic Fourier transform.
We therefore view (respectively ) as the vector space of complex-valued functions over the finite residual lattice (respectively ) and write: since a vector such as ψ is in fact the function .
The two spaces and may be equipped with the following Hermitian inner products: which makes each of them into a Hilbert space. The canonical bases and and and are orthonormal for their respective product.
By virtue of definitions (i) and (ii), so that and may be represented, in the canonical bases of and , by the following matrices:
When N is symmetric, and may be identified in a natural manner, and the above matrices are symmetric.
When N is diagonal, say , then the tensor product structure of the full multidimensional Fourier transform (Section 1.3.2.4.2.4) gives rise to a tensor product structure for the DFT matrices. The tensor product of matrices is defined as follows: Let the index vectors and be ordered in the same way as the elements in a Fortran array, e.g. for with increasing fastest, next fastest, slowest; then where and where
The DFT inherits most of the properties of the Fourier transforms, but with certain numerical factors (`Jacobians') due to the transition from continuous to discrete measure.
References
Shannon, C. E. (1949). Communication in the presence of noise. Proc. Inst. Radio Eng. NY, 37, 10–21.Google ScholarWhittaker, E. T. (1915). On the functions which are represented by the expansions of the interpolation-theory. Proc. R. Soc. (Edinburgh), 35, 181–194.Google Scholar