Discrete Fourier Transform in 2D

A two-dimensional Discrete Fourier Transform can be used to find a periodic function that goes through a two-dimensional set of data points. Consider a $N\times M$ grid of equally spaced data points which take the values $f_{uv}$ at position $\vec{r} = u\Delta x\hat{x} + v\Delta y\hat{y}$. We seek a two-dimensional periodic function $f(x,y)$ that passes through all of the points. This function can be expressed as a Fourier series,

$$f(x,y) = \sum\limits_{h=h^*}^{h^*+N-1}\sum\limits_{k=k^*}^{k^*+M-1}F_{hk}\exp \left(i2\pi \left(\frac{hx}{N\Delta x}+\frac{ky}{M\Delta y}\right)\right).$$

There are $N\times M$ points, and $N\times M$ exponential terms are needed to fit the data points. There are $N$ values of $h$ and $M$ values of $k$ in the sum, $h = h^*,h^*+1,h^*+2,\cdots,\,h^*+N-1$; $k = k^*,k^*+1,k^*+2,\cdots,\,k^*+M-1$. Here $h^*$ and $k^*$ can be any integers, so there are infinitely many periodic functions that will pass through all of the data points but the smoothest function $f(x,y)$, is obtained for $h^*=\text{Int}(-N/2+1)$, $k^*=\text{Int}(-M/2+1)$, where $\text{Int}(x)$ rounds down to the nearest integer. This choice corresponds to using only reciprocal lattice vectors in the first Brillouin zone.

To determine the values of $F_{hk}$, the data points are substituted into expression for the Fourier series. At the data points, $x=u\Delta x$ and $y=k\Delta y$.

$$f_{uv} = \sum\limits_{h=h^*}^{h^*+N-1}\sum\limits_{k=k^*}^{k^*+M-1}F_{hk}\exp \left(i2\pi\left(\frac{hn}{N}+\frac{kv}{M}\right)\right).$$

Multiply by $\exp \left(-i2\pi\left(\frac{h'u}{N}+\frac{k'v}{M}\right)\right)$ and sum over $u$ and $v$.

$$\sum\limits_{u=0}^{N-1}\sum\limits_{v=0}^{M-1}f_{uv}\exp \left(-i2\pi\left(\frac{h'u}{N}+\frac{k'v}{M}\right)\right) = \sum\limits_{u=0}^{N-1}\sum\limits_{v=0}^{M-1}\sum\limits_{h=h^*}^{h^*+N-1}\sum\limits_{k=k^*}^{k^*+M-1}F_{hk}\exp \left(i2\pi\left(\frac{(h-h')n}{N}+\frac{(k-k')v}{M}\right)\right).$$

In the sum on the right side, the sums over $u$ and $v$ will be zero unless $h=h'$ and $k=k'$. When $h=h'$ and $k=k'$, the right side evaluates to $NMF_{hk}$. This yields an expression for the Fourier coefficients,

$$F_{hk} = \frac{1}{NM} \sum\limits_{u=0}^{N-1}\sum\limits_{v=0}^{M-1}f_{uv}\exp\left(-i2\pi\left( hu/N+kv/M\right)\right).$$

This equation is called the Discrete Fourier Transform of the data series $f_{uv}$. In the form below, $f_{uv}$ can be input as a matrix. This data is plotted as red points as a function of $u$ and $v$. When the button is pushed, the Fourier coefficients for are calculated using a discrete Fourier transform and the correponding continuous function is plotted as the blue surface. Fits with other values of $h^*$ and $k^*$ can be displayed by inputting integer values for $h^*$ and $k^*$ and pressing the button.

$f_{uv}$
$F_{hk}$