approximating Fourier integrals with discrete Fourier transforms

Suppose we have a continuous functionMathworldPlanetmath f:ν for which we want to numerically compute the continuous Fourier transformMathworldPlanetmath:


Assume that either the function f is supported inside the compact rectangle C=[a1,b1]××[aν,bν], or that the Fourier integral is well approximated by truncating the domain to C.

We develop an approximation to f^ based on the discrete Fourier transformMathworldPlanetmath (which can be computed efficiently using the fast Fourier transform algorithmMathworldPlanetmath), and analyze the error in making this approximation.


Performing the linear substitution


we find that

= Vol(C)e-2πiξa0101g(t)e-2πi((b1-a1)ξ1t1++(bν-aν)ξνtν)𝑑t1𝑑tν
= Vol(C)e-2πiξag^((b1-a1)ξ1,,(bν-aν)ξν),



and g^ denotes the Fourier transform of g on the unit cube [0,1]ν.

Let u denote the vector with componentsPlanetmathPlanetmath u(k1,,kν)=g(k1/N,,kν/N), for kj=0,,N-1. The discrete Fourier transform of u is


and approximates Nνg^(l) since it is a Riemann sum (step size 1/N) for the Fourier integral.

Therefore, for lj=0,,N-1, we have the approximation:


Analysing the error

Assume that g can be represented by a pointwise-convergent11 Since the discrete Fourier transform requires sampling of points, 𝐋2 convergence of the Fourier seriesMathworldPlanetmath 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:




The Fourier coefficient of g is g^(l)=g,El, and in contrast u^(l)=Nνg,EkN, where:


is a positive semi-definite inner product.

We have the exact formula:


and we wish to know what error is introduced if we were to replace g^(l)=g,El by the discrete version of the inner productMathworldPlanetmath g,ElN=u^(l)/Nν.

Expand g,ElN as:


Since Ek,ElN is 1 if kjlj(modN) for all j, and is 0 otherwise, the discrete inner product reduces to:


In other words, the approximation entails replacing the true Fourier coefficient g^(l) with the same coefficient plus other Fourier coefficients g,El+kN corresponding to higher frequencies, in multiplesMathworldPlanetmath of N. The magnitude of the approximation error for f^ thus depends on how fast the partial sums of the Fourier coefficients g,Ek 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