approximating Fourier integrals with discrete Fourier transforms

Suppose we have a continuous function $f:{ℝ}^{\nu }\to ℂ$for which we want to numericallycompute the continuous Fourier transform:

$$\widehat{f}(\xi )={\int }_{{ℝ}^{\nu }}f(x)e^{-2\pi i\xi \cdot x}𝑑x,\xi \in {ℝ}^{\nu }.$$

Assume that either the function $f$ is supportedinside the compact rectangle$C=[a_1,b_1]\times \mathrm{\cdots }\times [a_{\nu },b_{\nu }]$,or that the Fourier integral is well approximatedby truncating the domain to $C$.

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

Derivation

Performing the linear substitution

$$t_j=\frac{x-a_j}{b_j-a_j},j=1,\mathrm{\dots },\nu ,$$

we find that

${\displaystyle {\int }_C}f(x)e^{-2\pi i\xi \cdot x}𝑑x$

$=$$\mathrm{Vol}(C)e^{-2\pi i\xi \cdot a}{\displaystyle {\int }_0^1}\mathrm{\cdots }{\displaystyle {\int }_0^1}g(t)e^{-2\pi i\left((b_1-a_1){\xi }_1{t}_1+\mathrm{\cdots }+(b_{\nu }-a_{\nu }){\xi }_{\nu }{t}_{\nu }\right)}𝑑t_1\mathrm{\cdots }𝑑t_{\nu }$

$=$$\mathrm{Vol}(C)e^{-2\pi i\xi \cdot a}\widehat{g}((b_1-a_1){\xi }_1,\mathrm{\dots },(b_{\nu }-a_{\nu }){\xi }_{\nu }),$

where

$$g(t_1,\mathrm{\dots },t_{\nu })=f(a_1+(b_1-a_1)t_1,\mathrm{\dots },a_{\nu }+(b_{\nu }-a_{\nu })t_{\nu }),t_j\in [0,1],$$

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

Let $u$ denote the vector with components$u(k_1,\mathrm{\dots },k_{\nu })=g(k_1/N,\mathrm{\dots },k_{\nu }/N)$, for $k_j=0,\mathrm{\dots },N-1$.The discrete Fourier transformof $u$ is

$$\widehat{u}(l)=\sum _{k\in {\{0,\mathrm{\dots },N-1\}}^{\nu }}u(k)e^{-2\pi ik\cdot l/N},l={\{0,\mathrm{\dots },N-1\}}^{\nu },$$

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

Therefore, for $l_j=0,\mathrm{\dots },N-1$,we have the approximation:

$$\widehat{f}(\frac{l_1}{b_1-a_1},\mathrm{\dots },\frac{l_{\nu }}{b_{\nu }-a_{\nu }})\approx \frac{\mathrm{Vol}(C)}{N^{\nu }}{e}^{-2\pi i\left(\frac{a_1{l}_1}{b_1-a_1}+\mathrm{\cdots }+\frac{a_{\nu }{l}_{\nu }}{b_{\nu }-a_{\nu }}\right)}\widehat{u}(l).$$

Analysing the error

Assume that $g$ can be represented by a pointwise-convergentFourier series:

$$g(t)=\sum _{k\in {\mathbb{Z}}^{\nu }}⟨g,E_k⟩E_k(t),$$

where

$$E_k(t)=e^{2\pi ik\cdot t},⟨\alpha ,\beta ⟩={\int }_{{[0,1]}^{\nu }}\alpha (t)\overline{\beta (t)}𝑑t.$$

The Fourier coefficient of $g$ is$\widehat{g}(l)=⟨g,E_l⟩$, and in contrast$\widehat{u}(l)=N^{\nu }{⟨g,E_k⟩}_N$, where:

$${⟨\alpha ,\beta ⟩}_N=\frac{1}{N^{\nu }}\sum _{k\in {\{0,\mathrm{\dots },N-1\}}^{\nu }}\alpha (k/N)\overline{\beta (k/N)}$$

is a positive semi-definite inner product.

We have the exact formula:

$$\widehat{f}(\frac{l_1}{b_1-a_1},\mathrm{\dots },\frac{l_{\nu }}{b_{\nu }-a_{\nu }})=\mathrm{Vol}(C)e^{-2\pi i\left(\frac{a_1{l}_1}{b_1-a_1}+\mathrm{\cdots }+\frac{a_{\nu }{l}_{\nu }}{b_{\nu }-a_{\nu }}\right)}\widehat{g}(l);$$

and we wish to know what error is introducedif we were to replace $\widehat{g}(l)=⟨g,E_l⟩$by the discrete version of the inner product ${⟨g,E_l⟩}_N=\widehat{u}(l)/N^{\nu }$.

Expand ${⟨g,E_l⟩}_N$ as:

$${⟨g,E_l⟩}_N={⟨\sum _{k\in {\mathbb{Z}}^{\nu }}⟨g,E_k⟩E_k,E_l⟩}_N=\sum _{k\in {\mathbb{Z}}^{\nu }}⟨g,E_k⟩{⟨E_k,E_l⟩}_N.$$

Since ${⟨E_k,E_l⟩}_N$ is $1$ if $k_j\equiv l_j(modN)$ for all $j$,and is $0$ otherwise,the discrete inner product reduces to:

$${⟨g,E_l⟩}_N=\sum _{k\in {\mathbb{Z}}^{\nu }}⟨g,E_{l+kN}⟩=⟨g,E_l⟩+\sum _{k\in {\mathbb{Z}}^{\nu }\setminus \{0\}}⟨g,E_{l+kN}⟩.$$

In other words, the approximation entails replacingthe true Fourier coefficient $\widehat{g}(l)$with the same coefficientplus other Fourier coefficients $⟨g,E_{l+kN}⟩$corresponding to higherfrequencies, in multiples of $N$.The magnitude of the approximation errorfor $\widehat{f}$thus depends on how fast the partial sumsof the Fourier coefficients $⟨g,E_k⟩$ decay to zero.