approximating Fourier integrals with discrete Fourier transforms
We develop an approximation to 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.
Performing the linear substitution
we find that
and denotes the Fourier transform of on the unit cube .
Let denote the vector with components , for . The discrete Fourier transform of is
and approximates since it is a Riemann sum (step size ) for the Fourier integral.
Therefore, for , we have the approximation:
Analysing the error
Assume that can be represented by a pointwise-convergent11 Since the discrete Fourier transform requires sampling of points, 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:
The Fourier coefficient of is , and in contrast , where:
We have the exact formula:
and we wish to know what error is introduced if we were to replace by the discrete version of the inner product .
Since is if for all , and is otherwise, the discrete inner product reduces to:
In other words, the approximation entails replacing the true Fourier coefficient with the same coefficient plus other Fourier coefficients corresponding to higher frequencies, in multiples of . The magnitude of the approximation error for thus depends on how fast the partial sums of the Fourier coefficients decay to zero.
|Title||approximating Fourier integrals with discrete Fourier transforms|
|Date of creation||2013-03-22 16:28:23|
|Last modified on||2013-03-22 16:28:23|
|Last modified by||stevecheng (10074)|