# approximating Fourier integrals with discrete Fourier transforms

Suppose we have a continuous function $f\colon\mathbb{R}^{\nu}\to\mathbb{C}$ for which we want to numerically compute the continuous Fourier transform:

 $\hat{f}(\xi)=\int_{\mathbb{R}^{\nu}}f(x)\,e^{-2\pi i\xi\cdot x}\,dx\,,\quad\xi% \in\mathbb{R}^{\nu}\,.$

Assume that either the function $f$ is supported inside the compact rectangle $C=[a_{1},b_{1}]\times\cdots\times[a_{\nu},b_{\nu}]$, or that the Fourier integral is well approximated by truncating the domain to $C$.

We develop an approximation to $\hat{f}$ based on the discrete Fourier transform (which can be computed efficiently using the fast Fourier transform algorithm), and analyze the error in making this approximation.

## Derivation

Performing the linear substitution

 $t_{j}=\frac{x-a_{j}}{b_{j}-a_{j}}\,,\quad j=1,\ldots,\nu\,,$

we find that

 $\displaystyle\int_{C}f(x)\,e^{-2\pi i\xi\cdot x}\,dx$ $\displaystyle=$ $\displaystyle\operatorname{Vol}(C)\,e^{-2\pi i\xi\cdot a}\int_{0}^{1}\cdots% \int_{0}^{1}g(t)\,e^{-2\pi i\bigl{(}(b_{1}-a_{1})\xi_{1}t_{1}+\cdots+(b_{\nu}-% a_{\nu})\xi_{\nu}t_{\nu}\bigr{)}}\,dt_{1}\cdots dt_{\nu}$ $\displaystyle=$ $\displaystyle\operatorname{Vol}(C)\,e^{-2\pi i\xi\cdot a}\,\hat{g}\bigl{(}(b_{% 1}-a_{1})\xi_{1},\ldots,(b_{\nu}-a_{\nu})\xi_{\nu}\bigr{)}\,,$

where

 $g(t_{1},\ldots,t_{\nu})=f(a_{1}+(b_{1}-a_{1})t_{1},\ldots,a_{\nu}+(b_{\nu}-a_{% \nu})t_{\nu})\,,\quad t_{j}\in[0,1]\,,$

and $\hat{g}$ denotes the Fourier transform of $g$ on the unit cube $[0,1]^{\nu}$.

Let $u$ denote the vector with components $u(k_{1},\ldots,k_{\nu})=g(k_{1}/N,\ldots,k_{\nu}/N)$, for $k_{j}=0,\ldots,N-1$. The discrete Fourier transform of $u$ is

 $\hat{u}(l)=\sum_{k\in\{0,\ldots,N-1\}^{\nu}}u(k)\,e^{-2\pi ik\cdot l/N}\,,% \quad l=\{0,\ldots,N-1\}^{\nu}\,,$

and approximates $N^{\nu}\hat{g}(l)$ since it is a Riemann sum (step size $1/N$) for the Fourier integral.

Therefore, for $l_{j}=0,\ldots,N-1$, we have the approximation:

 $\hat{f}\left(\frac{l_{1}}{b_{1}-a_{1}},\ldots,\frac{l_{\nu}}{b_{\nu}-a_{\nu}}% \right)\approx\frac{\operatorname{Vol}(C)}{N^{\nu}}\,e^{-2\pi i\left(\frac{a_{% 1}l_{1}}{b_{1}-a_{1}}+\cdots+\frac{a_{\nu}l_{\nu}}{b_{\nu}-a_{\nu}}\right)}\,% \hat{u}(l)\,.$

## Analysing the error

Assume that $g$ can be represented by a pointwise-convergent11 Since the discrete Fourier transform requires sampling of points, $\mathbf{L}^{2}$ convergence of the Fourier series is not sufficient. Also, the Fourier series may only be conditionally convergent. If there are difficulties in assuring its convergence, Fejér summation can be used instead in this analysis. Fourier series:

 $g(t)=\sum_{k\in\mathbb{Z}^{\nu}}\langle{g},{E_{k}}\rangle\,E_{k}(t)\,,$

where

 $E_{k}(t)=e^{2\pi ik\cdot t}\,,\quad\langle{\alpha},{\beta}\rangle=\int_{[0,1]^% {\nu}}\alpha(t)\,\overline{\beta(t)}\,dt\,.$

The Fourier coefficient of $g$ is $\hat{g}(l)=\langle{g},{E_{l}}\rangle$, and in contrast $\hat{u}(l)=N^{\nu}\,\langle{g},{E_{k}}\rangle_{N}$, where:

 $\langle{\alpha},{\beta}\rangle_{N}=\frac{1}{N^{\nu}}\sum_{k\in\{0,\ldots,N-1\}% ^{\nu}}\alpha(k/N)\,\overline{\beta(k/N)}$

We have the exact formula:

 $\hat{f}\left(\frac{l_{1}}{b_{1}-a_{1}},\ldots,\frac{l_{\nu}}{b_{\nu}-a_{\nu}}% \right)=\operatorname{Vol}(C)\,e^{-2\pi i\left(\frac{a_{1}l_{1}}{b_{1}-a_{1}}+% \cdots+\frac{a_{\nu}l_{\nu}}{b_{\nu}-a_{\nu}}\right)}\,\hat{g}(l)\,;$

and we wish to know what error is introduced if we were to replace $\hat{g}(l)=\langle{g},{E_{l}}\rangle$ by the discrete version of the inner product $\langle{g},{E_{l}}\rangle_{N}=\hat{u}(l)/N^{\nu}$.

Expand $\langle{g},{E_{l}}\rangle_{N}$ as:

 $\langle{g},{E_{l}}\rangle_{N}=\biggl{\langle}{\sum_{k\in\mathbb{Z}^{\nu}}% \langle{g},{E_{k}}\rangle E_{k}}\,,{E_{l}}\biggr{\rangle}_{N}=\sum_{k\in% \mathbb{Z}^{\nu}}\langle{g},{E_{k}}\rangle\langle{E_{k}},{E_{l}}\rangle_{N}\,.$

Since $\langle{E_{k}},{E_{l}}\rangle_{N}$ is $1$ if $k_{j}\equiv l_{j}\pmod{N}$ for all $j$, and is $0$ otherwise, the discrete inner product reduces to:

 $\langle{g},{E_{l}}\rangle_{N}=\sum_{k\in\mathbb{Z}^{\nu}}\langle{g},{E_{l+kN}}% \rangle=\langle{g},{E_{l}}\rangle+\sum_{k\in\mathbb{Z}^{\nu}\setminus\{0\}}% \langle{g},{E_{l+kN}}\rangle\,.$

In other words, the approximation entails replacing the true Fourier coefficient $\hat{g}(l)$ with the same coefficient plus other Fourier coefficients $\langle{g},{E_{l+kN}}\rangle$ corresponding to higher frequencies, in multiples of $N$. The magnitude of the approximation error for $\hat{f}$ thus depends on how fast the partial sums of the Fourier coefficients $\langle{g},{E_{k}}\rangle$ decay to zero.

Title approximating Fourier integrals with discrete Fourier transforms ApproximatingFourierIntegralsWithDiscreteFourierTransforms 2013-03-22 16:28:23 2013-03-22 16:28:23 stevecheng (10074) stevecheng (10074) 9 stevecheng (10074) Derivation msc 42B10 msc 65T50 msc 42A38 DiscreteTimeFourierTransformInRelationWithItsContinousTimeFourierTransfrom