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-convergent¹¹ 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)}

is a positive semi-definite inner product.

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
Canonical name	ApproximatingFourierIntegralsWithDiscreteFourierTransforms
Date of creation	2013-03-22 16:28:23
Last modified on	2013-03-22 16:28:23
Owner	stevecheng (10074)
Last modified by	stevecheng (10074)
Numerical id	9
Author	stevecheng (10074)
Entry type	Derivation
Classification	msc 42B10
Classification	msc 65T50
Classification	msc 42A38
Related topic	DiscreteTimeFourierTransformInRelationWithItsContinousTimeFourierTransfrom