Discretization of the Fourier transformation

Bricogne, G.

doi:10.1107/97809553602060000551

International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 47-48 | 1 | 2 |

Section 1.3.2.7.3. Discretization of the Fourier transformation

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.2.7.3. Discretization of the Fourier transformation

| top | pdf |

Let $[\varphi^{0} \in {\scr E}({\bb R}^{n})]$ be such that $[\Phi^{0} = {\scr F}[\varphi^{0}]]$ has compact support ( $[\varphi^{0}]$ is said to be band-limited). Then $[\varphi = R_{\bf A} * \varphi^{0}]$ is $[\Lambda_{\bf A}]$ -periodic, and $[\Phi = {\scr F}[\varphi] = (1/|\det {\bf A}|) R_{\bf A}^{*} \times \Phi^{0}]$ is such that only a finite number of points $[\lambda_{\bf A}^{*}]$ of $[\Lambda_{\bf A}^{*}]$ have a non-zero Fourier coefficient $[\Phi^{0} (\lambda_{\bf A}^{*})]$ attached to them. We may therefore find a decimation $[\Lambda_{\bf B}^{*} = {\bf D}^{T} \Lambda_{\bf A}^{*}]$ of $[\Lambda_{\bf A}^{*}]$ such that the distinct translates of Supp $[\Phi^{0}]$ by vectors of $[\Lambda_{\bf B}^{*}]$ do not intersect.

The distribution Φ can be uniquely recovered from $[R_{\bf B}^{*} * \Phi]$ by the procedure of Section 1.3.2.7.1, and we may write: $[\eqalign{R_{\bf B}^{*} * \Phi &= {1 \over |\det {\bf A}|} R_{\bf B}^{*} * (R_{\bf A}^{*} \times \Phi^{0})\cr &= {1 \over |\det {\bf A}|} R_{\bf A}^{*} \times (R_{\bf B}^{*} * \Phi^{0})\cr &= {1 \over |\det {\bf A}|} R_{\bf B}^{*} * [T_{{\bf A}/{\bf B}}^{*} \times (R_{\bf B}^{*} * \Phi^{0})]\hbox{;}}]$ these rearrangements being legitimate because $[\Phi^{0}]$ and $[T_{{\bf A}/{\bf B}}^{*}]$ have compact supports which are intersection-free under the action of $[\Lambda_{\bf B}^{*}]$ . By virtue of its $[\Lambda_{\bf B}^{*}]$ -periodicity, this distribution is entirely characterized by its `motif' $[\tilde{\Phi}]$ with respect to $[\Lambda_{\bf B}^{*}]$ : $[\tilde{\Phi} = {1 \over |\det {\bf A}|} T_{{\bf A}/{\bf B}}^{*} \times (R_{\bf B}^{*} * \Phi^{0}).]$

Similarly, φ may be uniquely recovered by Shannon interpolation from the distribution sampling its values at the nodes of $[\Lambda_{\bf B} = {\bf D}^{-1} \Lambda_{\bf A} (\Lambda_{\bf B}]$ is a subdivision of $[\Lambda_{\bf B}]$ ). By virtue of its $[\Lambda_{\bf A}]$ -periodicity, this distribution is completely characterized by its motif: $[\tilde{\varphi} = T_{{\bf B}/{\bf A}} \times \varphi = T_{{\bf B}/{\bf A}} \times (R_{\bf A}^{*} * \varphi^{0}).]$

Let $[{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}]$ and $[{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , and define the two sets of coefficients $[\!\!\matrix{(1)& \tilde{\varphi} ({\boldell}) \hfill&= \varphi ({\boldell} + \boldlambda_{\bf A})\hfill&\hbox{for any } \boldlambda_{\bf A} \in \Lambda_{\bf A}\hfill&\cr &&&(\hbox{all choices of } \boldlambda_{\bf A} \hbox{ give the same } \tilde{\varphi}),\hfill&\cr (2)&\tilde{\Phi} ({\boldell}^{*}) \hfill&= \Phi^{0} ({\boldell}^{*} + \boldlambda_{\bf B}^{*})\hfill &\hbox{for the unique } \boldlambda_{\bf B}^{*} \hbox{ (if it exists)}\hfill&\cr &&&\hbox{such that } {\boldell}^{*} + \boldlambda_{\bf B}^{*} \in \hbox{Supp } \Phi^{0},\hfill&\cr &&= 0\hfill&\hbox{if no such } \boldlambda_{\bf B}^{*} \hbox{ exists}.\hfill}]$ Define the two distributions $[\omega = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}}} \tilde{\varphi} ({\boldell}) \delta_{({\boldell})}]$ and $[\Omega = {\textstyle\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}}} \tilde{\Phi} ({\boldell}^{*}) \delta_{({\boldell}^{*})}.]$ The relation between ω and Ω has two equivalent forms: $[\displaylines{\quad (\hbox{i})\hfill \quad R_{\bf A} * \omega = {\scr F}[R_{\bf B}^{*} * \Omega] \hfill\cr \quad (\hbox{ii})\hfill \bar{\scr F}[R_{\bf A} * \omega] = R_{\bf B}^{*} * \Omega.\quad\;\;\;\hfill}]$

By (i), $[R_{\bf A} * \omega = |\det {\bf B}| R_{\bf B} \times {\scr F}[\Omega]]$ . Both sides are weighted lattice distributions concentrated at the nodes of $[\Lambda_{\bf B}]$ , and equating the weights at $[\boldlambda_{\bf B} = \boldell + \boldlambda_{\bf A}]$ gives $[\tilde{\varphi} ({\boldell}) = {1 \over |\det {\bf D}|} {\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}}} \tilde{\Phi} ({\boldell}^{*}) \exp [-2\pi i {\boldell}^{*} \cdot ({\boldell} + \boldlambda_{\bf A})].]$ Since $[\boldell^{*} \in \Lambda_{\bf A}^{*}]$ , $[\boldell^{*} \cdot \boldlambda_{\bf A}]$ is an integer, hence $[\tilde{\varphi} ({\boldell}) = {1 \over |\det {\bf D}|} {\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}}} \tilde{\Phi} ({\boldell}^{*}) \exp (-2\pi i {\boldell}^{*} \cdot {\boldell}).]$

By (ii), we have $[{1 \over |\det {\bf A}|} R_{\bf B}^{*} * [T_{{\bf A}/{\bf B}}^{*} \times (R_{\bf B}^{*} * \Phi^{0})] = {1 \over |\det {\bf A}|} \bar{\scr F}[R_{\bf A} * \omega].]$ Both sides are weighted lattice distributions concentrated at the nodes of $[\Lambda_{\bf B}^{*}]$ , and equating the weights at $[{\boldlambda}_{\bf A}^{*} = \boldell^{*} + {\boldlambda}_{\bf B}^{*}]$ gives $[\tilde{\Phi} ({\boldell}^{*}) = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}}} \tilde{\varphi} ({\boldell}) \exp [+2\pi i {\boldell} \cdot ({\boldell}^{*} + {\boldlambda}_{\bf B}^{*})].]$ Since $[\boldell \in \Lambda_{\bf B}]$ , $[\boldell \cdot {\boldlambda}^{*}_{\bf B}]$ is an integer, hence $[\tilde{\Phi} ({\boldell}^{*}) = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}}} \tilde{\varphi} ({\boldell}) \exp (+2\pi i {\boldell} \cdot {\boldell}^{*}).]$

Now the decimation/subdivision relations between $[\Lambda_{\bf A}]$ and $[\Lambda_{\bf B}]$ may be written: $[{\bf A} = {\bf DB} = {\bf BN},]$ so that $[\eqalign{{\boldell} &= {\bf B}{\bf \scr k}\qquad\qquad\hbox{for } {\bf \scr k}\in {\bb Z}^{n}\cr {\boldell}^{*} &= ({\bf A}^{-1})^{T} {\scr k}^{*}\quad \hbox{ for } {\bf \scr k}^{*} \in {\bb Z}^{n}}]$ with $[({\bf A}^{-1})^{T} = ({\bf B}^{-1})^{T} ({\bf N}^{-1})^{T}]$ , hence finally $[{\boldell}^{*} \cdot {\boldell} = {\boldell} \cdot {\boldell}^{*} = {\scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k}).]$

Denoting $[\tilde{\varphi} ({\bf B{\scr k}})]$ by $[\psi ({\scr k})]$ and $[\tilde{\Phi}[({\bf A}^{-1})^{T} {\scr k}^{*}]]$ by $[\Psi ({\scr k}^{*})]$ , the relation between ω and Ω may be written in the equivalent form $[\displaylines{(\hbox{i})\quad\hfill \psi ({\bf \scr k}) = {1 \over |\det {\bf N}|} {\sum\limits_{{\bf \scr k}^{*} \in {\bb Z}^{n}/{\bf N}^{T}{\bb Z}^{n}}} \Psi ({\bf \scr k}^{*}) \exp [-2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] \hfill\cr (\hbox{ii})\hfill \Psi ({\bf \scr k}^{*}) = {\sum\limits_{{\scr k}\in {\bb Z}^{n}/{\bf N}{\bb Z}^{\rm n}}} \psi ({\bf \scr k}) \exp [+2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})], \quad\;\qquad\hfill}]$ where the summations are now over finite residual lattices in standard form.

Equations (i) and (ii) describe two mutually inverse linear transformations $[{\scr F}({\bf N})]$ and $[\bar{\scr F}({\bf N})]$ between two vector spaces $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ of dimension $[|\det {\bf N}|]$ . $[{\scr F}({\bf N})]$ [respectively $[\bar{\scr F}({\bf N})]$ ] is the discrete Fourier (respectively inverse Fourier) transform associated to matrix N.

The vector spaces $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ may be viewed from two different standpoints:

(1) as vector spaces of weighted residual-lattice distributions, of the form $[\alpha ({\bf x}) T_{{\bf B}/{\bf A}}]$ and $[\beta ({\bf x}) T_{{\bf A}/{\bf B}}^{*}]$ ; the canonical basis of $[W_{\bf N}]$ (respectively $[W_{\bf N}^{*}]$ ) then consists of the $[\delta_{({\scr k})}]$ for $[{\scr k}\in {\bb Z}^{n}/{\bf N}{\bb Z}^{n}]$ [respectively $[\delta_{({\scr k}^{*})}]$ for $[{\scr k}^{*} \in {\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}]$ ];
(2) as vector spaces of weight vectors for the $[|\det {\bf N}|\ \delta]$ -functions involved in the expression for $[T_{{\bf B}/{\bf A}}]$ (respectively $[T_{{\bf A}/{\bf B}}^{*}]$ ); the canonical basis of $[W_{\bf N}]$ (respectively $[W_{\bf N}^{*}]$ ) consists of weight vectors $[{\bf u}_{{\scr k}}]$ (respectively $[{\bf v}_{{\scr k}^{*}}]$ ) giving weight 1 to element $[{\scr k}]$ (respectively $[{\scr k}^{*}]$ ) and 0 to the others.

These two spaces are said to be `isomorphic' (a relation denoted ≅), the isomorphism being given by the one-to-one correspondence: $[\eqalign{\omega &= {\textstyle\sum\limits_{{\bf \scr k}}} \psi ({\bf \scr k}) \delta_{({\bf \scr k})} \qquad \leftrightarrow \quad \psi = {\textstyle\sum\limits_{{\bf \scr k}}} \psi ({\scr k}) {\bf u}_{{\bf \scr k}}\cr \Omega &= {\textstyle\sum\limits_{{\bf \scr k}^{*}}} \Psi ({\bf \scr k}^{*}) \delta_{({\bf \scr k}^{*})} \quad\; \leftrightarrow \quad \Psi = {\textstyle\sum\limits_{{\bf \scr k}^{*}}} \Psi ({\bf \scr k}^{*}) {\bf v}_{{\bf \scr k}^{*}}.}]$

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 $[W_{\bf N}]$ (respectively $[W_{\bf N}^{*}]$ ) as the vector space of complex-valued functions over the finite residual lattice $[\Lambda_{\bf B}/\Lambda_{\bf A}]$ (respectively $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ ) and write: $[\eqalign{W_{\bf N} &\cong L(\Lambda_{\bf B}/\Lambda_{\bf A}) \cong L({\bb Z}^{n}/{\bf N}{\bb Z}^{n}) \cr W_{\bf N}^{*} &\cong L(\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}) \cong L({\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n})}]$ since a vector such as ψ is in fact the function $[{\scr k} \;\longmapsto\; \psi ({\scr k})]$ .

The two spaces $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ may be equipped with the following Hermitian inner products: $[\eqalign{(\varphi, \psi)_{W} &= {\textstyle\sum\limits_{{\bf \scr k}}} \overline{\varphi ({\bf \scr k})} \psi ({\bf \scr k}) \cr (\Phi, \Psi)_{W^{*}} &= {\textstyle\sum\limits_{{\bf \scr k}}} \overline{\Phi ({\bf \scr k}^{*})} \Psi ({\bf \scr k}^{*}),}]$ which makes each of them into a Hilbert space. The canonical bases $[\{{\bf u}_{{\scr k}} | {\scr k}\in {\bb Z}^{n}/{\bf N} {\bb Z}^{n}\}]$ and $[\{{\bf v}_{{\scr k}^{*}} | {\scr k}^{*} \in {\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}\}]$ and $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ are orthonormal for their respective product.

References

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 47-48